"2048" en unas pocas semanas marca 5 años, lo que significa que es hora de escribir algo dedicado a este maravilloso juego.
El tema de un juego independiente de inteligencia artificial en un rompecabezas es especialmente informativo. Hay una variedad de formas de implementarlo y hoy analizaremos una relativamente fácil. A saber, le enseñaremos a la mente de la computadora a recolectar grados de dos usando el método Monte Carlo.
Este artículo fue escrito con el apoyo de EDISON Software, una compañía que desarrolla aplicaciones móviles y proporciona servicios de prueba de software .
La inspiración para este trabajo fue una discusión sobre stackoverflow, donde
los tipos inteligentes sugirieron formas efectivas de un juego de computadora . Aparentemente, la mejor manera es el método minimax con recorte alfa-beta y en un par de días la próxima publicación se dedicará a ello.
Método de casino sugerido por el usuario de stackoverflow
Ronenz como parte de la discusión anterior. La siguiente sección completa es una traducción de su publicación.
Método Monte Carlo
Me interesó la idea de IA para este juego, en el que
no hay inteligencia codificada (es decir, no hay heurística, puntuación, etc.). La IA debería "conocer" solo las reglas del juego y "entender" el juego. Esto lo distingue de la mayoría de la IA (como en este hilo), porque el juego es, de hecho, la fuerza bruta controlada por la función de puntuación, lo que refleja la comprensión humana del juego.
Algoritmo AI
Encontré un algoritmo de juego simple pero sorprendentemente bueno: para determinar el próximo movimiento para un estado dado del campo, la IA juega el juego en RAM, haciendo
movimientos aleatorios hasta que el juego termina en derrota. Esto se hace varias veces, y se rastrea el puntaje final. Luego, el puntaje final promedio se calcula teniendo en cuenta el curso inicial. El movimiento inicial que mostró el resultado promedio más alto se selecciona como el movimiento ya elegido.
Con 100 carreras por cada turno inicial, la IA llega a la casilla 2048 en el 80% de los casos y la ficha 4096 en el 50% de los casos. Cuando se usan 10,000 corridas, se obtienen 2048 en el 100% de los casos, 70% para 4096 y aproximadamente 1% para 8192.
Ver en acciónEl mejor resultado logrado se muestra en la captura de pantalla:
Un hecho interesante para este algoritmo es que, aunque se espera que los juegos con movimientos ejecutados aleatoriamente sean bastante malos, sin embargo, elegir el mejor movimiento (o menos malo, si lo desea) conduce a una jugabilidad muy buena: un juego típico de IA de Monte Carlo puede anotar 70,000 puntos por 3000 movimientos, pero los juegos con un juego arbitrario en la memoria desde cualquier posición dan un promedio de 340 puntos adicionales por aproximadamente 40 movimientos adicionales antes de perder. (Puede verificar esto usted mismo iniciando la IA y abriendo la consola de depuración).
Este gráfico ilustra este concepto: la línea azul muestra el puntaje del juego después de cada movimiento. La línea roja muestra el
mejor resultado del algoritmo, haciendo movimientos arbitrarios desde esta posición hasta el final del juego. De hecho, los valores rojos "tiran" hacia arriba de los azules, ya que son las mejores oraciones del algoritmo. Curiosamente, la línea roja está ligeramente por encima de la línea azul en cada punto, pero la línea azul reduce la brecha cada vez más.
Me resulta bastante sorprendente que el algoritmo no anticipe necesariamente una buena jugabilidad y, sin embargo, elija los movimientos que lo producen (un buen proceso).
Más tarde descubrí que este método se puede clasificar como
un algoritmo de búsqueda de árbol de Monte Carlo .
Implementación y enlaces
Primero, creé una versión de JavaScript que se puede
ver en acción aquí . Esta versión puede ejecutar 100 ejecuciones en un tiempo razonable. Abre la consola para más información. (
fuente )
Más tarde, para jugar, utilicé la infraestructura altamente optimizada de @nneonneo e implementé mi versión en C ++. Esta versión permite hasta 100,000 carreras por turno e incluso 1,000,000 si está listo para esperar. Instrucciones de montaje incluidas. Todo funciona en la consola, y también tiene un control remoto para la reproducción en la versión web. (
fuente )
Resultados
Sorprendentemente, un aumento en el número de carreras no mejora fundamentalmente la jugabilidad. Parece que esta estrategia tiene un límite de 80,000 puntos con un mosaico de 4096 y todos los resultados más pequeños están muy cerca de alcanzar el mosaico 8192. Un aumento en el número de carreras de 100 a 100,000 aumenta las posibilidades de alcanzar este límite (del 5% al 40%), pero no lo supera
Realizar 10,000 carreras con un aumento temporal de hasta 1,000,000 cerca de las posiciones críticas hizo posible superar esta barrera en menos del 1% de los casos con el número máximo de puntos anotados 129892 y fichas 8192.
Mejoras y optimizaciones
Después de implementar este algoritmo, probé muchas mejoras, incluido el uso de calificaciones mínimas o máximas o una combinación de valores mínimos, máximos y promedio. También traté de usar la profundidad: en lugar de intentar completar K carreras por turno, probé K movimientos por lista de movimientos de una longitud determinada (por ejemplo, "arriba, arriba, izquierda") y elegí el primer movimiento de la lista de movimientos con la mejor victoria.
Más tarde, implementé un árbol de puntuación que tenía en cuenta la probabilidad condicional de que él pudiera completar un movimiento después de una lista dada de movimientos.
Sin embargo, ninguna de estas ideas mostró una ventaja real sobre una primera idea simple. Dejé el código comentado para estas ideas en la fuente de C ++.
Agregué el mecanismo de Búsqueda profunda, que aumentó temporalmente el número de ejecuciones a 1,000,000 cuando cualquiera de las ejecuciones logró accidentalmente alcanzar el siguiente mosaico más alto. Esto condujo a una mejora en el rendimiento del tiempo.
Me interesaría saber si alguien tiene alguna otra idea de mejora que respalde la independencia de AI del área temática.
Opciones y clones 2048
Por diversión, también implementé la IA como un marcador, conectándolo a los controles del juego. Esto te permite trabajar tanto con el juego original como con muchas de sus variaciones.
Esto es posible debido a la naturaleza independiente del dominio de AI. Algunas de las opciones son bastante originales, como un clon hexagonal.
2048.xlsm
La propia aplicación Excel se
puede descargar de Google .
Se puede hacer clic en la imagen; se abrirá una imagen a tamaño completo.
Brevemente sobre la interfaz y la funcionalidad de la aplicación.
Para comenzar a jugar, debes hacer clic en el botón "
Usuario: iniciar juego ". Cuando presiona este botón nuevamente, la inscripción cambia de "
Usuario: iniciar el juego " a "
Usuario: finalizar el juego " y viceversa, es decir, en cualquier momento puede detener el juego y luego volver a iniciarlo. Cuando el juego se detiene, puedes cambiar manualmente la alineación en el campo, mejorando o empeorando tu posición para probar o verificar algunas ideas.
Durante el juego en sí, puedes hacer movimientos de dos maneras:
- Teclado: simplemente presionando las teclas "arriba", "abajo", "izquierda", "derecha".
- Con el mouse: haciendo clic en las celdas con flechas grandes que indican la dirección deseada.
El botón "
Nuevo campo " borra el campo de juego y coloca aleatoriamente el "dos" y el "cuatro" en él.
Lo más interesante es que se implementó el método Monte Carlo, exactamente en la forma en que fue propuesto por el tipo con stackoverflow. En cada posición, la computadora en la memoria pasa por ramas aleatorias para cada primer movimiento ("arriba", "abajo", "izquierda", "derecha") hasta que conduce a una pérdida. Estadísticamente, la dirección más favorable se resalta en rojo en una tabla especial a continuación. Puedes usarlo como una pista si ves que tu propio juego está parado y necesitas salvarte de alguna manera. ;)
Encima de la tabla hay casillas de verificación con opciones de análisis. Por el momento, solo se ha decidido Monte Carlo, el resto se agregará en los próximos días (como resultado, habrá más harastas con la actualización de la aplicación de Excel y las explicaciones de la teoría).
También hay una
IA: botón de
juego . Al hacer clic en él, el asistente de computadora hará un movimiento de acuerdo con el método Monte Carlo o algún otro que esté seleccionado en el grupo de conmutadores (minimax y red neuronal funcionarán en esta lista un poco más adelante).
Todos los artículos de la serie AI y 2048.