Solución:
Desarrollé una IA 2048 usando expectativa optimización, en lugar de la búsqueda minimax utilizada por el algoritmo de @ ovolve. La IA simplemente realiza la maximización de todos los movimientos posibles, seguida de la expectativa sobre todos los posibles engendros de mosaicos (ponderado por la probabilidad de los mosaicos, es decir, 10% para un 4 y 90% para un 2). Hasta donde yo sé, no es posible podar la optimización de hopeimax (excepto para eliminar ramas que son extremadamente improbables), por lo que el algoritmo utilizado es una búsqueda de fuerza bruta cuidadosamente optimizada.
Rendimiento
La IA en su configuración predeterminada (profundidad máxima de búsqueda de 8) tarda entre 10 ms y 200 ms en ejecutar un movimiento, dependiendo de la complejidad de la posición del tablero. En las pruebas, la IA logra una tasa de movimiento promedio de 5 a 10 movimientos por segundo durante el transcurso de un juego completo. Si la profundidad de búsqueda está limitada a 6 movimientos, la IA puede ejecutar fácilmente más de 20 movimientos por segundo, lo que lo convierte en una observación interesante.
Para evaluar el rendimiento de la puntuación de la IA, ejecuté la IA 100 veces (conectado al juego de navegador a través del control remoto). Para cada mosaico, estas son las proporciones de juegos en los que ese mosaico se logró al menos una vez:
2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%
La puntuación mínima en todas las carreras fue 124024; la puntuación máxima alcanzada fue 794076. La puntuación media es 387222. La IA nunca falló en obtener la ficha 2048 (por lo que nunca perdió el juego ni una sola vez en 100 juegos); de hecho, logró el 8192 ¡Mosaico al menos una vez en cada ejecución!
Aquí está la captura de pantalla de la mejor ejecución:
Este juego tomó 27830 movimientos en 96 minutos, o un promedio de 4.8 movimientos por segundo.
Implementación
Mi enfoque codifica toda la placa (16 entradas) como un único entero de 64 bits (donde los mosaicos son los nybbles, es decir, fragmentos de 4 bits). En una máquina de 64 bits, esto permite pasar toda la placa en un solo registro de máquina.
Las operaciones de cambio de bits se utilizan para extraer filas y columnas individuales. Una sola fila o columna es una cantidad de 16 bits, por lo que una tabla de tamaño 65536 puede codificar transformaciones que operan en una sola fila o columna. Por ejemplo, los movimientos se implementan como 4 búsquedas en una “tabla de efectos de movimiento” precalculada que describe cómo cada movimiento afecta a una sola fila o columna (por ejemplo, la tabla “mover a la derecha” contiene la entrada “1122 -> 0023” que describe cómo hilera [2,2,4,4] se convierte en la fila [0,0,4,8] cuando se mueve hacia la derecha).
La puntuación también se realiza mediante la búsqueda de tablas. Las tablas contienen puntuaciones heurísticas calculadas en todas las filas / columnas posibles, y la puntuación resultante para un tablero es simplemente la suma de los valores de la tabla en cada fila y columna.
Esta representación del tablero, junto con el enfoque de búsqueda de tablas para el movimiento y la puntuación, permite a la IA buscar una gran cantidad de estados de juego en un corto período de tiempo (más de 10,000,000 de estados de juego por segundo en un núcleo de mi computadora portátil de mediados de 2011).
La búsqueda de hopeimax en sí está codificada como una búsqueda recursiva que alterna entre pasos de “expectativa” (probar todas las ubicaciones y valores posibles de generación de mosaicos, y ponderar sus puntuaciones optimizadas por la probabilidad de cada posibilidad) y pasos de “maximización” (probar todos los movimientos posibles y seleccionando el que tenga la mejor puntuación). La búsqueda del árbol termina cuando ve una posición vista anteriormente (usando una tabla de transposición), cuando alcanza un límite de profundidad predefinido o cuando alcanza un estado de tablero que es muy poco probable (por ejemplo, se alcanzó al obtener 6 fichas de “4” en fila desde la posición inicial). La profundidad de búsqueda típica es de 4-8 movimientos.
Heurísticas
Se utilizan varias heurísticas para dirigir el algoritmo de optimización hacia posiciones favorables. La elección precisa de la heurística tiene un efecto enorme en el rendimiento del algoritmo. Las diversas heurísticas se ponderan y combinan en una puntuación posicional, que determina qué tan “buena” es una posición determinada en el tablero. La búsqueda de optimización tendrá como objetivo maximizar la puntuación media de todas las posiciones posibles en el tablero. La puntuación real, como se muestra en el juego, es no se utiliza para calcular la puntuación del tablero, ya que está demasiado ponderado a favor de la fusión de fichas (cuando la fusión demorada podría producir un gran beneficio).
Inicialmente, utilicé dos heurísticas muy simples, otorgando “bonificaciones” por cuadrados abiertos y por tener valores grandes en el borde. Estas heurísticas funcionaron bastante bien, con frecuencia lograron 16384 pero nunca llegaron a 32768.
Petr Morávek (@xificurk) tomó mi IA y agregó dos nuevas heurísticas. La primera heurística fue una penalización por tener filas y columnas no monótonas que aumentaron a medida que aumentaban los rangos, asegurando que las filas no monótonas de números pequeños no afectarían fuertemente la puntuación, pero las filas no monótonas de números grandes dañaron sustancialmente la puntuación. La segunda heurística contó el número de posibles fusiones (valores iguales adyacentes) además de los espacios abiertos. Estas dos heurísticas sirvieron para impulsar el algoritmo hacia tableros monótonos (que son más fáciles de fusionar) y hacia posiciones de tablero con muchas fusiones (alentándolo a alinear fusiones donde sea posible para un mayor efecto).
Además, Petr también optimizó los pesos heurísticos usando una estrategia de “meta-optimización” (usando un algoritmo llamado CMA-ES), donde los pesos mismos se ajustaron para obtener la puntuación promedio más alta posible.
El efecto de estos cambios es extremadamente significativo. El algoritmo pasó de lograr el mosaico 16384 alrededor del 13% del tiempo a lograrlo en más del 90% del tiempo, y el algoritmo comenzó a lograr 32768 en 1/3 del tiempo (mientras que las heurísticas antiguas nunca produjeron un mosaico 32768) .
Creo que todavía hay margen de mejora en la heurística. Este algoritmo definitivamente no es todavía “óptimo”, pero siento que se está acercando bastante.
Que la IA alcance el mosaico 32768 en más de un tercio de sus juegos es un gran hito; Me sorprenderá saber si algún jugador humano ha logrado 32768 en el juego oficial (es decir, sin usar herramientas como guardar estados o deshacer). ¡Creo que el azulejo 65536 está al alcance!
Puedes probar la IA por ti mismo. El código está disponible en https://github.com/nneonneo/2048-ai.
Soy el autor del programa de IA que otros han mencionado en este hilo. Puede ver la IA en acción o leer la fuente.
Actualmente, el programa alcanza una tasa de ganancias del 90% ejecutándose en javascript en el navegador de mi computadora portátil con aproximadamente 100 milisegundos de tiempo de pensamiento por movimiento, por lo que aunque no es perfecto (¡todavía!), Funciona bastante bien.
Dado que el juego es un espacio de estado discreto, información perfecta, un juego por turnos como el ajedrez y las damas, utilicé los mismos métodos que se ha demostrado que funcionan en esos juegos, a saber, búsqueda minimax con poda alfa-beta. Dado que ya hay mucha información sobre ese algoritmo, solo hablaré sobre las dos heurísticas principales que utilizo en el static función de evaluación y que formalizan muchas de las intuiciones que aquí han expresado otras personas.
Monotonicidad
Esta heurística intenta garantizar que los valores de los mosaicos aumenten o disminuyan a lo largo de las direcciones izquierda / derecha y arriba / abajo. Esta heurística por sí sola captura la intuición que muchos otros han mencionado, de que los mosaicos de mayor valor deben agruparse en una esquina. Por lo general, evitará que los mosaicos de menor valor se queden huérfanos y mantendrá el tablero muy organizado, con mosaicos más pequeños en cascada y llenando los mosaicos más grandes.
Aquí hay una captura de pantalla de una cuadrícula perfectamente monótona. Obtuve esto ejecutando el algoritmo con la función eval configurada para ignorar las otras heurísticas y solo considerar la monotonicidad.
Suavidad
La heurística anterior por sí sola tiende a crear estructuras en las que los mosaicos adyacentes están disminuyendo en valor, pero, por supuesto, para fusionarse, los mosaicos adyacentes deben tener el mismo valor. Por lo tanto, la heurística de suavidad solo mide la diferencia de valor entre mosaicos vecinos, tratando de minimizar este recuento.
Un comentarista de Hacker News dio una formalización interesante de esta idea en términos de teoría de grafos.
Aquí hay una captura de pantalla de una cuadrícula perfectamente suave, cortesía de esta excelente bifurcación de parodia.
Azulejos gratis
Y finalmente, hay una penalización por tener muy pocas fichas libres, ya que las opciones pueden agotarse rápidamente cuando el tablero de juego se vuelve demasiado pequeño.
¡Y eso es! Buscar en el espacio del juego mientras se optimizan estos criterios produce un rendimiento notablemente bueno. Una ventaja de utilizar un enfoque generalizado como este en lugar de una estrategia de movimiento codificada explícitamente es que el algoritmo a menudo puede encontrar soluciones interesantes e inesperadas. Si lo ves correr, a menudo hará movimientos sorprendentes pero efectivos, como cambiar repentinamente la pared o esquina contra la que se está construyendo.
Editar:
Aquí hay una demostración del poder de este enfoque. Destapé los valores de los mosaicos (por lo que continuó después de llegar a 2048) y aquí está el mejor resultado después de ocho intentos.
Sí, es un 4096 junto con un 2048. =) Eso significa que logró la elusiva ficha de 2048 tres veces en el mismo tablero.
Me interesé en la idea de una IA para este juego que contiene sin inteligencia codificada (es decir, sin heurísticas, funciones de puntuación, etc.). La IA debería “saber” solo las reglas del juego, y “descubrir” el juego. Esto contrasta con la mayoría de las IA (como las de este hilo) donde el juego es esencialmente fuerza bruta dirigida por una función de puntuación que representa la comprensión humana del juego.
Algoritmo de IA
Encontré un algoritmo de juego simple pero sorprendentemente bueno: para determinar el siguiente movimiento para un tablero dado, la IA juega el juego en la memoria usando movimientos aleatorios hasta que termine el juego. Esto se hace varias veces mientras se realiza un seguimiento del puntaje final del juego. Entonces el puntaje final promedio por movimiento inicial es calculado. El movimiento inicial con el puntaje final promedio más alto se elige como el siguiente movimiento.
Con solo 100 carreras (es decir, en juegos de memoria) por movimiento, la IA logra el mosaico 2048 el 80% de las veces y el mosaico 4096 el 50% de las veces. El uso de 10000 corridas obtiene el 100% del mosaico 2048, el 70% para el mosaico 4096 y aproximadamente el 1% para el mosaico 8192.
Míralo en acción
La mejor puntuación obtenida se muestra aquí:
Un dato interesante sobre este algoritmo es que, si bien el Los juegos de juego aleatorio son, como era de esperar, bastante malos, elegir el mejor (o el menos malo) movimiento conduce a un muy buen juego: un juego de IA típico puede alcanzar los 70000 puntos y los últimos 3000 movimientos, pero los juegos de juego aleatorio en la memoria desde cualquier posición dada rinde un promedio de 340 puntos adicionales en aproximadamente 40 movimientos adicionales antes de morir. (Puede ver esto por sí mismo ejecutando la IA y abriendo la consola de depuración).
Este gráfico ilustra este punto: La línea azul muestra la puntuación del tablero después de cada movimiento. La línea roja muestra el algoritmo mejor puntuación final del juego de carrera aleatoria desde esa posición. En esencia, los valores rojos están “tirando” de los valores azules hacia ellos, ya que son la mejor suposición del algoritmo. Es interesante ver que la línea roja está un poquito por encima de la línea azul en cada punto, pero la línea azul continúa aumentando cada vez más.
Me sorprende bastante que el algoritmo no necesite prever realmente un buen juego para elegir los movimientos que lo producen.
Buscando más tarde, encontré que este algoritmo podría clasificarse como un algoritmo de búsqueda de árbol de Monte Carlo puro.
Implementación y enlaces
Primero creé una versión de JavaScript que se puede ver en acción aquí. Esta versión puede ejecutar cientos de ejecuciones en un tiempo decente. Abra la consola para obtener información adicional. (fuente)
Más tarde, para jugar un poco más usé @nneonneo una infraestructura altamente optimizada e implementé mi versión en C ++. Esta versión permite hasta 100000 carreras por movimiento e incluso 1000000 si tienes paciencia. Se proporcionan instrucciones de construcción. Se ejecuta en la consola y también tiene un mando a distancia para reproducir la versión web. (fuente)
Resultados
Sorprendentemente, aumentar el número de carreras no mejora drásticamente el juego. Parece haber un límite para esta estrategia en alrededor de 80000 puntos con la ficha 4096 y todas las más pequeñas, muy cerca de lograr la ficha 8192. Aumentar el número de corridas de 100 a 100000 aumenta la impares de llegar a este límite de puntuación (del 5% al 40%) pero sin superarlo.
Ejecutar 10000 carreras con un aumento temporal a 1000000 cerca de posiciones críticas logró romper esta barrera en menos del 1% de las veces logrando una puntuación máxima de 129892 y el mosaico de 8192.
Mejoras
Después de implementar este algoritmo, probé muchas mejoras, incluido el uso de puntajes mínimos o máximos, o una combinación de mínimo, máximo y promedio. También intenté usar la profundidad: en lugar de intentar K carreras por movimiento, probé K movimientos por movimiento lista de una longitud determinada (“arriba, arriba, izquierda” por ejemplo) y seleccionando el primer movimiento de la lista de movimientos con mejor puntuación.
Más tarde implementé un árbol de puntuación que tenía en cuenta la probabilidad condicional de poder jugar un movimiento después de una lista de movimientos determinada.
Sin embargo, ninguna de estas ideas mostró una ventaja real sobre la primera idea simple. Dejé el código para estas ideas comentadas en el código C ++.
Agregué un mecanismo de “búsqueda profunda” que aumentó el número de ejecución temporalmente a 1000000 cuando alguna de las ejecuciones logró alcanzar accidentalmente el siguiente mosaico más alto. Esto ofreció una mejora de tiempo.
Me interesaría saber si alguien tiene otras ideas de mejora que mantengan la independencia de dominio de la IA.
2048 variantes y clones
Solo por diversión, también implementé la IA como un marcador, conectándome a los controles del juego. Esto permite que la IA funcione con el juego original y muchas de sus variantes.
Esto es posible debido a la naturaleza independiente del dominio de la IA. Algunas de las variantes son bastante distintas, como el clon hexagonal.
Si te apasiona la informática, tienes el poder dejar una sección acerca de qué le añadirías a esta reseña.