Cómo encontrar el equipo pokemon óptimo

Question

Pokémon es un juego en el que 2 jugadores seleccionan cada uno 6 Pokémon (un equipo) al comienzo del juego sin conocer el equipo del otro jugador. Cada Pokémon tiene uno o dos tipos. Cada tipo es débil, neutral o fuerte frente a cualquier otro tipo. Esto significa que cada enfrentamiento de 2 Pokémon tendrá un ganador o un empate. Esto también significa que cualquier equipo puede clasificarse contra cualquier otro equipo en función del número de enfrentamientos ganadores que tenga.

Quiero escribir un programa que pueda encontrar el equipo Pokémon óptimo entre un conjunto de 70 Pokémon proporcionados. Un equipo se considera óptimo si tiene el mayor número de enfrentamientos ganadores contra cualquier otro equipo. Básicamente, quiero calcular qué equipo tendrá la mayor cantidad de enfrentamientos favorables si tuvieras que luchar contra todos los demás equipos posibles.

¿Qué algoritmo sería mejor para hacer esto? No es factible calcular emparejamientos para todos los equipos posibles. ¿Puedo hacer algún tipo de búsqueda A * con suficiente poda para que sea computacionalmente factible?

Answer 1

Después de mi comentario inicial (donde sugiero que podría no ser suficiente información) creo que se me ocurrió una idea.

Comience con el conjunto completo de Pokémon. Para cada tipo posible, identifica el recuento de Pokémon que son fuertes contra ese tipo. Para esto, terminarás con un List<(pokemonId, types, List<weakAgainst>)>.

Minimiza List<weakAgainst>.Count()y del posible conjunto de pokemonIds, selecciona uno al azar. Sin saber nada más además del tipo, este pokemon es tan bueno como cualquier otro con el mismo recuento de debilidades (este es el punto de mi comentario original).

De la lista de debilidades que tiene este Pokémon seleccionado, selecciona un Pokémon de tu lista que sea fuerte contra la debilidad, minimizando nuevamente la cantidad de debilidades. Es probable que más de uno coincida con este criterio, nuevamente, seleccione uno al azar.

Sigue repitiendo este patrón hasta que obtengas el 6 en tu equipo. Este es, estadísticamente hablando, uno de los mejores equipos que puedes reunir.

Para todas las combinaciones que puede encontrar aquí, algunos equipos tendrán menos debilidades, ya que estamos "al azar" caminando por un árbol de posibilidades. Esto suena mucho como un algoritmo de poda minimax , donde cada selección de Pokémon (minimizando tus debilidades) puede encontrarse con oponentes potenciales que maximizarán tus puntos débiles.

Simplificado, ensamblado:

input: allPokemon: list<pokemonId, weakAgainst, strongAgainst>

var: teamWeakAgainst: []
var: teamStrongAgainst: []
var: selectedTeam: []

while (size(selectedTeam) < 6)
  goodMatches <- allPokemon.max(p -> size(p.strongAgainst.intersect(teamWeakAgainst)))
  goodMatches <- goodMatches.min(p -> size(p.weakAgainst))
  goodMatches <- goodMatches.max(p -> size(p.strongAgainst))

  selectedPokemon <- goodMatches.random()

  teamWeakAgainst -= selectedPokemon.strongAgainst
  teamWeakAgainst += selectedPokemon.weakAgainst # not counting previously selected pokemon because the current one adds another "weakness", even if it was already accounted for

  selectedTeam += selectedPokemon

output: selectedTeam

A partir de este algoritmo, no es obvio dónde está la parte "máxima". Estamos minimizando nuestras pérdidas (debilidades) pero estamos considerando todos los posibles equipos oponentes por igual, por lo que no hay una maximización real de las opciones del oponente. Para obtener un conjunto de ideas, consulte a continuación.

Tenga en cuenta que este algoritmo le dará un conjunto de "equipos" que son igualmente buenos en el sentido de que tendrán la misma cantidad de debilidades minimizadas y fortalezas maximizadas contra otros equipos posibles. Pero incluso si los Pokémon son diferentes, los números serán los mismos, solo de diferentes tipos.

Para un enfoque más complejo, es posible que desee considerar qué tan frecuentes son algunos Pokémon (es posible que no necesite optimizar contra un tipo mítico súper raro, sino más bien los tipos muy comunes disponibles en el juego), qué tan probable es que ciertos Pokémon puedan tener ataques mejores / más rápidos, cuál es la probabilidad de batallas IV, con qué frecuencia un entrenador puede cambiar de Pokémon en la batalla, etc. complejo que en lugar de un algoritmo de búsqueda, un enfoque de simulación (¿Monte Carlo?) podría ser más simple para construir equipos a partir de pruebas estadísticas.