Investigación matemática de Pokémon

Question

En el juego competitivo de Pokémon, dos jugadores eligen un equipo de seis Pokémon de los 718 disponibles. Estos se eligen de forma independiente, es decir, el jugador $A$ no conoce al jugador $B$ La elección de los Pokémon. Algunos servidores online permiten a los jugadores ver el equipo del rival antes del combate, lo que permite al jugador cambiar el orden de sus Pokémon. (Sólo importa el primero, ya que es el que se enviará primero al combate. Después, los jugadores pueden cambiar entre los seis elegidos libremente, como se explica a continuación). A cada Pokémon se le asignan cuatro movimientos de una lista de movimientos que pueden o no ser únicos para ese Pokémon. Actualmente hay 609 movimientos en la lista de movimientos. A cada movimiento se le asigna un tipo determinado, y puede ser más o menos efectivo contra Pokémon de ciertos tipos. Sin embargo, un Pokémon puede tener más de un tipo. En general, la efectividad de los movimientos viene dada por $0.5\times$ , $1\times$ y $2\times$ . Sin embargo, hay excepciones a esta regla. Ferrothorn, un Pokémon de tipo dual de acero y hierba, tomará $4\times$ daño contra movimientos de fuego, ya que sus dos tipos son débiles contra el fuego. Todos los movimientos tienen una cierta probabilidad de que funcione.

Además, hay movimientos con otros efectos además del daño directo. Por ejemplo, un movimiento puede aumentar el ataque propio, disminuir el del rival o añadir una deficiencia de estado en el Pokémon del rival, como por ejemplo hacer que se duerma. Esto hará que el Pokémon no pueda moverse con una probabilidad relativamente alta. Si es capaz de moverse, el estado de "dormido" se levanta. Además, cada Pokémon tiene una "Naturaleza" que aumenta una estadística (fuera de Ataque, Defensa, Ataque Especial, Defensa Especial, Velocidad), mientras que disminuye otra. Aunque ya no es necesario para mi argumento, se podría profundizar aún más con cosas como los IV y los EV de cada Pokémon, que también afectan a sus estadísticas.

Un jugador ha ganado cuando todos los Pokémon de su rival están fuera de juego. Un jugador puede cambiar el Pokémon activo libremente. (Es decir, las "batallas" son 1v1, pero los Pokémon pueden cambiarse libremente).

¿Ha habido alguna investigación matemática seria hacia el juego competitivo de Pokémon? En particular, ¿se ha demostrado que siempre hay una estrategia mejor? ¿Y el número de "posiciones" posibles? Si siempre hay una estrategia mejor, ¿se puede evaluar la probabilidad de que un equipo gane al otro, dado el mejor juego de ambos lados? (Como se hace hoy con los motores de ajedrez, dada una determinada posición).

EDIT: En aras de la simplicidad, creo que es una buena idea considerar dos posiciones iguales cuando

1) Ambas posiciones tienen equipos idénticos en términos de Pokémon. (Se omiten las naturalezas, los IVs, los EVs y las estadísticas.) Como tal, se puede crear una correspondencia uno a uno entre el conjunto de $12$ Pokémon en posición $A$ y el $12$ en posición $B$ por el mapeo $a_A \mapsto a_B$ , donde $a_A$ es Pokémon $a$ en posición $A$ .

2) $a_A$ y $a_B$ tienen los mismos movimientos para todos $a\in A, B$ .

Answer 1

¿Se ha producido una grave investigación ? Probablemente no. ¿Ha habido esfuerzos de modelización? Casi con toda seguridad, y probablemente oscilen entre lo completamente chapucero y lo algo sofisticado.

En el fondo, el juego es finito; hay dos jugadores y un conjunto grande pero finito de estrategias. Como tal, la existencia de un equilibrio de estrategia mixta está garantizada. Este es el resultado de Nash, y es en realidad una interesante aplicación del teorema de punto fijo de Brouwer.

Dicho esto, el reto no está realmente en las matemáticas; si se puede establecer el juego, es bastante probable que se pueda resolver utilizando algún enfoque de programación lineal. El reto está en modelar el resultado, capturar la dinámica y, hasta cierto punto (probablemente pequeño), manejar las pocas fuentes de incertidumbre intrínseca (es decir, la incertidumbre generada por la aleatoriedad, como la posibilidad de acertar).

Sin embargo, esto es irrelevante, ya que el tamaño del espacio de acción es tan grande que es básicamente insostenible. Las soluciones de LP sufren la maldición de la dimensionalidad: cuantas más acciones haya en el espacio de acción discreto, más cosas tendrá que mirar el algoritmo y, por tanto, más tiempo tardará en resolverlas.

Por ello, la mayoría de las herramientas que se utilizan se basan intrínsecamente en Monte Carlo: las simulaciones se ejecutan una y otra vez, con nuevas semillas aleatorias, y la probabilidad de ganar se mide estadísticamente.

Estos métodos de Monte Carlo también tienen sus inconvenientes. Ciertas acciones del jugador, como cambiar su Blastoise por su Pikachu, son decisiones deterministas. Pero ya hemos visto que el espacio de acciones es demasiado grande para prescribir el determinismo en muchos casos. Manejar esto en la práctica se vuelve difícil. Podrías tratar esto como una acción aleatoria con alguna probabilidad (aunque en el mundo real no es aleatoria en absoluto), y aumentar tu número de ejecuciones de Monte Carlo, o podrías aplicar alguna heurística, como "cambiar a Blastoise si el tipo de enemigo es fuego y mi pokemon actual está por debajo de la mitad de la salud". Sin embargo, escribir estas heurísticas se basa en la suposición de que tus puntos de ruptura son casi óptimos, y rara vez está claro que ese sea el caso.

En consecuencia, juegos como Pokemon son interesantes porque las soluciones óptimas son difíciles de encontrar. Si hubiera 10 pokemon y 20 habilidades, no sería tan divertido. La complejidad matemática, si tuviera que apostar, es probablemente mayor que la del ajedrez, debido simplemente al tamaño del espacio de acción y a la dinámica más rica de los resultados medibles. Esta es una de las razones por las que el juego y la comunidad siguen siendo activos: la gente encuentra nuevas ideas y nuevos conceptos que explorar.

Además, la empresa que hace el juego sigue haciendo nuevas versiones. Eso ayuda.

---

Una nota final: uno de los retos en el modelado matemático de la dinámica del juego es que las reglas de combate son muy fáciles de implementar programáticamente, pero algo más difíciles de describir limpiamente de forma matemática. Por ejemplo, un ataque puede hacer 10 de daño al principio, y luego 5 de daño por ronda durante 4 rondas. Otros ataques podrían tener enfriamientos, y así sucesivamente. Esto es fácil de implementar en el código, pero más difícil de escribir una ecuación feliz. Como tal, es un poco más desafiante hacer cosas como tratar de identificar los gradientes, etc., de forma analítica, aunque también podría hacerse de forma programada. También sería una aplicación interesante para la diferenciación automática.

Answer 2

Creo que vale la pena señalar que incluso quitando la mayor parte de la complejidad del juego sigue quedando un problema bastante difícil.

El juego más sencillo del que se puede decir que tiene algún parecido con Pokemon es el de piedra-papel-tijera (RPS). (Imagina, por ejemplo, que sólo hay tres Pokemon -llamémoslos arbitrariamente Squirtle, Charmander y Bulbasaur- y que Squirtle siempre gana a Charmander, Charmander siempre gana a Bulbasaur y Bulbasaur siempre gana a Squirtle).

Ya no está claro qué significa aquí "la mejor estrategia". Hay una única Equilibrio de Nash dado al jugar aleatoriamente con Squirtle, Charmander o Bulbasaur con una probabilidad exacta $\frac{1}{3}$ cada uno, pero en general el hecho de que exista un equilibrio de Nash, incluso un único equilibrio de Nash, no significa que sea la estrategia a la que la gente se incline en la práctica.

De hecho, existe una escena de los torneos profesionales de RPS y en esos torneos nadie juega al equilibrio de Nash porque nadie puede generar elecciones aleatorias con probabilidad $\frac{1}{3}$ En cambio, todo el mundo está jugando una estrategia de equilibrio que no es de Nash, y si quieres jugar para ganar (no sólo ganar $\frac{1}{3}$ de las veces, que es lo mejor que se puede esperar jugando al equilibrio de Nash), jugará en cambio con estrategias que le vayan bien contra las estrategias típicas que se encontrará. Dos ejemplos:

• Los jugadores novatos tienden a abrir con roca, y a recurrir a ella cuando están enfadados o pierden, así que contra esos jugadores deberías jugar con papel.
• Los jugadores novatos de RPS tienden a evitar repetir sus jugadas con demasiada frecuencia, por lo que si un jugador novato ha jugado a la piedra dos veces, debes esperar que probablemente juegue a las tijeras o al papel a continuación.

Incluso hay un Escenario del concurso de programación RPS donde la gente diseña algoritmos para jugar juegos repetidos de RPS contra otros algoritmos, y nadie juega el equilibrio de Nash en estos juegos a menos que sea absolutamente necesario. La idea es tratar de predecir lo que el algoritmo contrario va a hacer a continuación, mientras intentas evitar que tu oponente prediga lo que tú harás a continuación. Iocaína en polvo es un buen ejemplo del tipo de cosas que hacen estos algoritmos.

Por lo tanto, incluso la cuestión tan simple de averiguar la "mejor estrategia" en RPS está en cierto sentido abierta, y la gente puede dedicar mucho tiempo tanto a averiguar buenas estrategias para jugar contra otras personas como buenos algoritmos para jugar contra otros algoritmos. Creo que es seguro decir que Pokemon es estrictamente más complicado que RPS, lo suficiente como para que incluso este nivel de análisis sea probablemente imposible.

Editar: También vale la pena señalar que otra forma en que Pokemon difiere de un juego como el ajedrez es que es información imperfecta El objetivo del juego es: no sabes todo sobre los Pokémon de tu oponente (conjuntos de movimientos, distribución de EV, objetos de retención, etc.) aunque sepas cuáles son. Esto significa que ambos jugadores deberían intentar predecir estas variables ocultas sobre los Pokémon del otro, al tiempo que intentan engañar al otro jugador para que haga predicciones incorrectas. Tengo entendido que una estrategia común para hacer esto es usar Pokemon que tienen conjuntos de movimientos viables muy diferentes y tratar de engañar a tu oponente para que piense que estás jugando un conjunto de movimientos cuando en realidad estás jugando otro. En este sentido, Pokemon se parece más al póker que al ajedrez.

Answer 3

Máquina técnica es probablemente lo más parecido que se puede conseguir. Se trata de una IA bastante sofisticada. Utiliza un algoritmo expectminimax. Además, si no recuerdo mal, utiliza datos históricos de servidores de simulación de batallas para hacer suposiciones sobre las composiciones de los equipos y los conjuntos de movimientos.