¿Por qué un auto puede jugar inhumanamente bien en Mario, pero no en Pokémon?

En previsión de nuestro torneo en el videojuego de la vieja escuela Game Overnight, decidimos hablar sobre los bots en los juegos de computadora.

Probablemente hayas escuchado que las capacidades de los bots modernos para juegos de computadora superan a las humanas. Dichos bots pueden estar codificados, reaccionando siempre por igual a los mismos conjuntos de datos de entrada. Otro enfoque para su desarrollo es que se les permite aprender y evolucionar . Se comportan de manera diferente en las mismas situaciones al tratar de encontrar soluciones óptimas a los problemas que enfrentan.



Aquí hay algunos ejemplos bien conocidos de tales bots:

• AlphaZero es un bot de ajedrez que, después de 24 horas de entrenamiento, se ha convertido en el mejor jugador de la Tierra.
• AlphaGo es el programa que venció a Lee Sedola y Ke Jie en Go.
• MarI / O es un bot para Super Mario que aprende solo, tratando de completar los niveles del juego lo más rápido posible.

Chess, go, Super Mario: juegos difíciles, los bots son combinaciones de algoritmos razonablemente seleccionadas, lleva mucho tiempo entrenarlos.

Este material está dedicado al análisis del bot MarI / O y la historia de por qué el enfoque utilizado para crear este bot no ayudará a escribir un programa que pueda jugar Pokemon bien.

¿Cuál es la diferencia entre Mario y Pokemon?

Hay tres diferencias clave entre los juegos de Mario y Pokemon que determinan el éxito potencial de los bots:

1. El número de goles.
2. Coeficiente de ramificación.
3. La contradicción entre la optimización global y local.

Compara juegos con estos factores en mente.

Numero de goles

Las máquinas aprenden optimizando una determinada función objetivo. Puede ser la maximización de la función de recompensa o la función de condición física (cuando se aprende con refuerzo y cuando se usan algoritmos genéticos ), se puede minimizar la función de pérdida (cuando se aprende con un maestro ). En cualquier caso, si hablamos de la aplicación del juego, estamos hablando del conjunto de la cantidad máxima de puntos posible.

Mario tiene un objetivo: llegar al final del nivel. En pocas palabras, cuanto más avance en el juego, mejor. Este indicador expresa una función objetivo única, y las capacidades del modelo pueden estimarse, simple y claramente, mediante un solo indicador.

Gol del juego Mario

Pokémon tiene muchos objetivos. Tratemos de averiguarlo. ¿Quizás el objetivo del juego es derrotar a los cuatro elite? Tal vez esta es la captura de todos los Pokémon? ¿O tal vez necesitas entrenar al equipo más fuerte? Es posible que el objetivo del juego sea una combinación de todos los objetivos anteriores o incluso algo completamente diferente. Es probable que, en realidad, si le preguntas a un jugador específico sobre esto, su objetivo se presente en forma de una combinación compleja de los muchos logros disponibles en el juego.


Objetivos del juego de Pokémon

Al analizar un juego, es necesario no solo determinar su objetivo final, sino también decidir cómo progresa el juego, cómo ciertas acciones afectan la función objetivo, empeorando o mejorando dependiendo de la gran variedad de opciones disponibles para el jugador en un momento determinado.

De hecho, la elección de una variante de acción en una determinada situación nos lleva al segundo indicador de comparación de juegos.

Relación de ramificación

El coeficiente de ramificación es, en términos simples, un indicador que indica el número de opciones de acción disponibles en cada paso del proceso del juego. En ajedrez, el coeficiente de ramificación promedio es 35. En go - 250. Si un bot intenta "mirar hacia el futuro", después de haber contado todos los movimientos que puede hacer en este momento, y luego todos los movimientos que puede hacer después de completar el movimiento actual. , y así sucesivamente, cada nivel significa un aumento serio en la complejidad de la tarea. Es decir, el número de opciones con este enfoque crece exponencialmente, expresado como una fórmula de la forma (coeficiente de ramificación) ^ (número de niveles).

En Mario, un personaje puede moverse hacia la izquierda o hacia la derecha, puede saltar y simplemente no puede hacer nada. La cantidad de opciones que el bot necesita para evaluar es pequeña. Cuanto más bajo sea el coeficiente de ramificación, más lejos podrá mirar el bot en el futuro, gastando recursos informáticos aceptables en esto.

Opciones de Mario

Pokemon tiene un mundo de juegos abierto. Esto significa que en cada momento en particular el jugador tiene muchas opciones de acción. Además, una simple enumeración de las direcciones del posible movimiento de un personaje en este caso no es adecuada para calcular el coeficiente de ramificación. En cambio, ciertas acciones juegan un papel importante en el mundo del juego. ¿Será la próxima acción una pelea, una conversación con un personaje del juego, una transición a otra área del mapa? Además, el número de opciones, a medida que avanzas en el juego, está creciendo.


Presentación simplificada de acciones de personajes en Pokémon

Para crear un bot que pueda determinar qué secuencia de decisiones se deben tomar en tal situación, este bot debe tener en cuenta sus objetivos a corto y largo plazo, lo que nos lleva a la próxima dimensión de comparar juegos de Mario y Pokemon.

La contradicción entre la optimización global y local.

La optimización local y global puede considerarse tanto espacial como temporalmente. Los objetivos a corto plazo y un área pequeña que rodea al personaje del juego están relacionados con la optimización local. Los objetivos a largo plazo y los fragmentos relativamente grandes del espacio del juego (algo así como una "ciudad" o todo el mundo del juego) se relacionan con la optimización global.

Si, en Pokémon, desglosas cada movimiento en sus partes constituyentes, esto ayudará a presentar el problema que el bot, que consiste en fragmentos muy pequeños, tiene que resolver. La optimización local, que permite, por ejemplo, ir del punto A al punto B, no causará dificultades. Un problema mucho más complicado es la elección del punto B, la dirección del movimiento. Los algoritmos codiciosos no nos ayudarán aquí, ya que las soluciones óptimas a nivel local no necesariamente conducen a resultados óptimos a nivel mundial.


El problema de elegir el siguiente paso

Los mapas en Mario son pequeños y lineales. Los mapas en Pokémon son grandes, complejos y no lineales. Antes del jugador, a medida que avanzas en el juego y mientras persigue objetivos cada vez más importantes, constantemente surgen nuevas tareas. Y la tarea de organizar la conexión de optimizaciones locales con objetivos globales no es fácil. Al menos los modelos existentes aún no están listos para resolverlo.

Resumen

Desde el punto de vista de los bots, Pokémon no es un juego. Los bots son notables por su estrecha especialización, y un bot que ayude al jugador a moverse por el mapa será inútil si el jugador encuentra un personaje del juego con el que unirse a la batalla. Desde el punto de vista de los bots, moverse por el mapa y la batalla son tareas completamente diferentes.


Los bots son sistemas altamente especializados

Durante la batalla en cada paso tienes que elegir entre docenas de opciones. Debes decidir qué acción tomar, qué Pokémon tomar, debes entender cuándo usar varios elementos. Todo esto, en sí mismo, presenta desafíos complejos de optimización. Aquí está el material que explora el desafío de desarrollar un simulador de batalla en Pokémon. Este artículo está bien desarrollado, es bastante complicado, pero incluso allí no se considera el problema de los objetos, el factor más importante que afecta el resultado de la batalla.

Al final, podemos decir que debemos alegrarnos por el hecho de que podemos crear bots que jueguen nuestros juegos mejor que nosotros. Estos juegos son complejos desde un punto de vista matemático, pero sus objetivos se determinan fácilmente. Con el desarrollo de tecnologías de inteligencia artificial, la humanidad podrá crear máquinas que puedan resolver los problemas cada vez más importantes del mundo real. Lo harán estudiando estos problemas, que son tareas complejas de optimización. Pero por ahora, les puedo asegurar, hay tareas que resolvemos mejor que las máquinas, incluidos los juegos que muchos de nosotros jugamos en la infancia. Al menos este es el caso ahora.

Estimados lectores! Te invitamos a participar en el primer torneo de Rusia sobre videojuegos de la vieja escuela Game Overnight . El torneo tiene una parte clasificatoria y una verdadera batalla de lo mejor de lo mejor, que se llevará a cabo el 30 de noviembre en el Museo de máquinas tragamonedas soviéticas. Estamos esperando el torneo de 20 a 3 horas, bebidas de espuma Smart Admin, Dj Ogurets (Sergey Mezentsev) y el administrador de RUVDS Unpushible DJ lo ayudarán, y también probaremos nuevas hamburguesas de nieve Sub Zero de nuestros administradores. Entonces, como dicen, ¡bienvenido!