¿Cuál es el algoritmo óptimo para el juego 2048

algorithm logic artificial-intelligence 2048


Recientemente me topé con el juego 2048 . Combinas fichas similares moviéndolas en cualquiera de las cuatro direcciones para hacer fichas "más grandes". Después de cada movimiento, aparece una nueva ficha en una posición vacía aleatoria con un valor de 2 o 4 . El juego termina cuando todas las casillas están llenas y no hay movimientos que puedan fusionar fichas, o se crea una ficha con un valor de 2048 .

Uno,necesito seguir una estrategia bien definida para alcanzar la meta.Así que pensé en escribir un programa para ello.

Mi algoritmo actual:

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

Lo que estoy haciendo es en cualquier momento, intentaré fusionar los mosaicos con los valores 2 y 4 , es decir, trataré de tener 2 y 4 mosaicos, lo mínimo posible. Si lo intento de esta manera, todos los otros mosaicos se fusionan automáticamente y la estrategia parece buena.

Pero cuando uso este algoritmo,sólo consigo unos 4000 puntos antes de que termine el juego.El máximo de puntos AFAIK es ligeramente superior a 20.000 puntos,lo que es mucho mayor que mi puntuación actual.¿Hay algún algoritmo mejor que el anterior?





Answer 1 nneonneo


Desarrollé una IA de 2048 usando la optimización de waitimax , en lugar de la búsqueda de minimax utilizada por el algoritmo de @ ovolve. La IA simplemente realiza la maximización sobre todos los movimientos posibles, seguida de la expectativa sobre todos los engendros de fichas posibles (ponderado por la probabilidad de las fichas, es decir, 10% para un 4 y 90% para un 2). Hasta donde yo sé, no es posible podar la optimización de waitimax (excepto para eliminar ramas que son extremadamente improbables), por lo que el algoritmo utilizado es una búsqueda de fuerza bruta cuidadosamente optimizada.

Performance

La IA en su configuración predeterminada (profundidad de búsqueda máxima de 8) tarda entre 10 ms y 200 ms para ejecutar un movimiento, dependiendo de la complejidad de la posición del tablero. En las pruebas, la IA logra una velocidad de movimiento promedio de 5-10 movimientos por segundo en el transcurso de un juego completo. Si la profundidad de búsqueda se limita 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 IA,corrí la IA 100 veces (conectada al juego del navegador por control remoto).Para cada ficha,aquí están las proporciones de los juegos en los que esa ficha se logró al menos una vez:

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

El puntaje mínimo en todas las carreras fue de 124024; el puntaje máximo alcanzado fue 794076. El puntaje promedio es 387222. La IA nunca falló en obtener el mosaico de 2048 (por lo que nunca perdió el juego ni una sola vez en 100 juegos); De hecho, ¡logró el mosaico 8192 al menos una vez en cada carrera!

Aquí está la captura de pantalla de la mejor carrera:

32768 tile, score 794076

Este juego tomó 27830 movimientos en 96 minutos,o un promedio de 4.8 movimientos por segundo.

Implementation

Mi enfoque codifica todo el tablero (16 entradas)como un único entero de 64 bits (donde los azulejos son los nibbles,es decir,trozos de 4 bits).En una máquina de 64 bits,esto permite que todo el tablero se pase en un solo registro de máquina.

Las operaciones de desplazamiento 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" calculada previamente 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 fila [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 en la tabla.Las tablas contienen puntuaciones heurísticas calculadas en todas las filas y columnas posibles,y la puntuación resultante para una tabla es simplemente la suma de los valores de la tabla en cada fila y columna.

Esta representación en el tablero,junto con el enfoque de búsqueda en la mesa para el movimiento y la puntuación,permite a la IA buscar un gran número 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 portátil de mediados de 2011).

La búsqueda expectimax en sí misma se codifica como una búsqueda recursiva que alterna entre los pasos de "expectativa" (probar todas las ubicaciones y valores posibles de baldosas y ponderar sus puntajes optimizados por la probabilidad de cada posibilidad), y los pasos de "maximización" (probar todos los movimientos posibles y seleccionando el que tenga la mejor puntuación). La búsqueda de árbol finaliza cuando ve una posición vista previamente (usando una tabla de transposición ), cuando alcanza un límite de profundidad predefinido o cuando alcanza un estado de tablero que es altamente improbable (por ejemplo, se alcanzó al obtener 6 "4" fichas en una fila desde la posición inicial). La profundidad de búsqueda típica es de 4-8 movimientos.

Heuristics

Se utilizan varias heurísticas para dirigir el algoritmo de optimización hacia posiciones favorables. La elección precisa de heurística tiene un gran efecto en el rendimiento del algoritmo. Las diversas heurísticas se ponderan y se combinan en una puntuación posicional, que determina cuán "buena" es una posición de tablero determinada. La búsqueda de optimización tendrá como objetivo maximizar el puntaje promedio de todas las posibles posiciones en el tablero. La puntuación real, como se muestra en el juego, no se utiliza para calcular la puntuación del tablero, ya que está demasiado ponderada a favor de fusionar fichas (cuando la fusión demorada podría producir un gran beneficio).

Inicialmente,usé dos heurísticas muy simples,concediendo "bonificaciones" por los cuadrados abiertos y por tener grandes valores en el borde.Estos heurísticos funcionaron bastante bien,frecuentemente alcanzando 16384 pero nunca llegando 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 el puntaje, pero las filas no monótonas de números grandes dañan sustancialmente el puntaje. 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 empujar el algoritmo hacia tableros monotónicos (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 "metaoptimización" (usando un algoritmo llamado CMA-ES ), donde los pesos mismos se ajustaron para obtener el puntaje promedio más alto posible.

El efecto de estos cambios es extremadamente significativo.El algoritmo pasó de lograr el azulejo de 16384 alrededor del 13% de las veces a lograrlo en más del 90% de las veces,y el algoritmo comenzó a lograr 32768 en 13 de las veces (mientras que la antigua heurística nunca produjo ni una sola vez un azulejo de 32768).

Creo que todavía se puede mejorar la heurística.Este algoritmo definitivamente no es aún "óptimo",pero siento que se está acercando bastante.


El hecho de que la IA consiga el azulejo 32768 en más de un tercio de sus juegos es un gran hito;me sorprendería saber si algún jugador humano ha conseguido 32768 en el juego oficial (es decir,sin usar herramientas como "savestates" o "undo").Creo que el azulejo 65536 está al alcance de la mano!

Puedes probar la IA por ti mismo. El código está disponible en https://github.com/nneonneo/2048-ai .




Answer 2 ovolve


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 ganancia del 90% corriendo en javascript en el navegador de mi portátil dados unos 100 milisegundos de tiempo de pensamiento por movimiento,así que aunque no es perfecto (¡todavía!)funciona bastante bien.

Dado que el juego es un espacio de estado discreto, información perfecta, juego por turnos como el ajedrez y las damas, utilicé los mismos métodos que han demostrado que funcionan en esos juegos, a saber, la búsqueda minimax con poda alfa-beta . Como ya hay mucha información sobre ese algoritmo, hablaré sobre las dos heurísticas principales que uso en la función de evaluación estática y que formalizan muchas de las intuiciones que otras personas han expresado aquí.

Monotonicity

Esta heurística trata de asegurar que los valores de los azulejos estén todos aumentando o disminuyendo tanto en la dirección de la izquierda como en la de arriba.Esta heurística por sí sola captura la intuición que muchos otros han mencionado,que los azulejos de mayor valor deben ser agrupados en una esquina.Normalmente evitará que los azulejos más pequeños queden huérfanos y mantendrá el tablero muy organizado,con los azulejos más pequeños cayendo en cascada y llenándose en los más grandes.

Aquí hay una captura de pantalla de una red perfectamente monótona.La obtuve ejecutando el algoritmo con la función de evaluación configurada para ignorar los otros heurísticos y sólo considerar la monotonicidad.

A perfectly monotonic 2048 board

Smoothness

La heurística anterior por sí sola tiende a crear estructuras en las que los azulejos adyacentes están disminuyendo de valor,pero por supuesto para fusionarse,los azulejos adyacentes deben tener el mismo valor.Por lo tanto,la heurística de la suavidad sólo mide la diferencia de valor entre las baldosas vecinas,tratando de minimizar este conteo.

Un comentarista en Hacker News dio una interesante formalización 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 este excelente tenedor de parodia .

A perfectly smooth 2048 board

Azulejos gratis

Y por último,hay una penalización por tener pocas fichas libres,ya que las opciones se pueden agotar rápidamente cuando el tablero de juego se vuelve demasiado estrecho.

¡Y eso es todo! Buscar en el espacio del juego mientras se optimizan estos criterios produce un rendimiento notablemente bueno.Una ventaja de usar un enfoque generalizado como este en lugar de una estrategia de movimiento explícitamente codificada es que el algoritmo puede encontrar a menudo soluciones interesantes e inesperadas.Si lo ves correr,a menudo hará movimientos sorprendentes pero efectivos,como cambiar repentinamente contra qué pared o esquina se está construyendo.

Edit:

Aquí hay una demostración del poder de este enfoque.Destapé los valores de los azulejos (así que siguió adelante después de llegar a 2048)y aquí está el mejor resultado después de ocho pruebas.

4096

Sí,eso es un 4096 junto a un 2048.=)Eso significa que logró la elusiva baldosa de 2048 tres veces en el mismo tablero.




Answer 3 Ronenz


Me interesó la idea de una IA para este juego que no contenga inteligencia codificada (es decir, no heurística, funciones de puntuación, etc.). La IA debe "conocer" 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 próximo movimiento para un tablero dado, la IA juega el juego en la memoria usando movimientos aleatorios hasta que el juego termina. Esto se hace varias veces mientras se realiza un seguimiento de la puntuación final del juego. Luego se calcula el puntaje final promedio por movimiento inicial . El movimiento inicial con el puntaje final promedio más alto se elige como el siguiente movimiento.

Con sólo 100 carreras (es decir,en juegos de memoria)por movimiento,la IA logra la ficha 2048 el 80% de las veces y la ficha 4096 el 50% de las veces.Usando 10000 ejecuciones se consigue la ficha de 2048 al 100%,el 70% para la ficha de 4096,y alrededor del 1% para la ficha de 8192.

Véalo en acción

La mejor puntuación obtenida se muestra aquí:

best score

Un hecho interesante de este algoritmo es que,aunque los juegos de azar son,como es lógico,bastante malos,la elección del mejor (o menos malo)movimiento conduce a un juego muy bueno:Un típico juego de IA puede alcanzar los 70000 puntos y durar 3000 movimientos,sin embargo los juegos aleatorios en memoria desde cualquier posición dan un promedio de 340 puntos adicionales en unos 40 movimientos extra antes de morir.(Puedes ver esto por ti mismo ejecutando la IA y abriendo la consola de depuración).

Este gráfico ilustra este punto: la línea azul muestra el puntaje del tablero después de cada movimiento. La línea roja muestra la mejor puntuación final del juego aleatorio del algoritmo 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, sin embargo, la línea azul continúa aumentando más y más.

scoring graph

Encuentro bastante sorprendente que el algoritmo no necesite prever un buen juego para elegir los movimientos que lo producen.

Al buscar más tarde, encontré que este algoritmo podría clasificarse como un algoritmo de búsqueda de árbol Pure Monte Carlo .

Aplicació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 tiempo decente. Abre la consola para obtener información adicional. ( fuente )

Más tarde, para jugar un poco más, utilicé la infraestructura altamente optimizada de @nneonneo e implementé mi versión en C ++. Esta versión permite hasta 100000 carreras por movimiento e incluso 1000000 si tienes paciencia. Instrucciones de construcción proporcionadas. Se ejecuta en la consola y también tiene un control remoto para reproducir la versión web. ( fuente )

Results

Sorprendentemente, aumentar el número de carreras no mejora drásticamente el juego. Parece que hay un límite para esta estrategia en alrededor de 80000 puntos con el mosaico 4096 y todos los más pequeños, muy cerca del logro del mosaico 8192. Aumentar el número de carreras de 100 a 100000 aumenta las probabilidades de llegar a este límite de puntuación (del 5% al ​​40%) pero no romperlo.

Corriendo 10.000 carreras con un aumento temporal a 10.000 cerca de las posiciones críticas lograron romper esta barrera menos del 1% de las veces logrando un puntaje máximo de 129892 y el azulejo 8192.

Improvements

Después de implementar este algoritmo probé muchas mejoras, incluido el uso de las puntuaciones mínimas o máximas, o una combinación de mín., Máx. Y prom. También intenté usar la profundidad: en lugar de intentar K carreras por movimiento, probé K movimientos por lista de movimientos de una longitud determinada ("arriba, arriba, izquierda", por ejemplo) y seleccioné 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 una jugada después de una lista de movimientos dada.

Sin embargo,ninguna de estas ideas mostraron ninguna ventaja real sobre la simple primera idea.Dejé el código de estas ideas comentadas en el código C++.

Añadí un mecanismo de "Búsqueda Profunda" que aumentó el número de ejecuciones temporalmente a 1000000 cuando cualquiera de las ejecuciones lograba alcanzar accidentalmente el siguiente azulejo más alto.Esto ofrecía una mejora de tiempo.

Me interesaría saber si alguien tiene otras ideas de mejora que mantengan la independencia del dominio de la IA.

2048 Variantes y clones

Solo por diversión, también implementé la IA como un marcador , enganchá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.




Answer 4 Daren


EDITAR: este es un algoritmo ingenuo, que modela el proceso de pensamiento consciente humano, y obtiene resultados muy débiles en comparación con la IA que busca todas las posibilidades, ya que solo mira un mosaico por delante. Fue presentado temprano en la línea de tiempo de respuesta.

¡He refinado el algoritmo y he vencido al juego! Puede fallar debido a la simple mala suerte cerca del final (te ves obligado a moverte hacia abajo,lo que nunca debes hacer,y aparece un azulejo donde debería estar tu más alto.Intenta mantener la fila superior llena,para que al moverte a la izquierda no se rompa el patrón),pero básicamente acabas teniendo una parte fija y una parte móvil con la que jugar.Este es tu objetivo:

Ready to finish

Este es el modelo que elegí por defecto.

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

La esquina elegida es arbitraria,básicamente no se pulsa una tecla (el movimiento prohibido),y si lo hace,se vuelve a pulsar lo contrario y se intenta arreglarlo.Para los futuros azulejos el modelo siempre espera que el siguiente azulejo aleatorio sea un 2 y aparezca en el lado opuesto al modelo actual (mientras que la primera fila está incompleta,en la esquina inferior derecha,una vez completada la primera fila,en la esquina inferior izquierda).

Aquí va el algoritmo.Alrededor del 80% gana (parece que siempre es posible ganar con técnicas de IA más "profesionales",aunque no estoy seguro de esto.)

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

Algunos consejos sobre los pasos que faltan.Aquí:model change

El modelo ha cambiado debido a la suerte de estar más cerca del modelo esperado.El modelo que la IA está tratando de lograr es

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

Y la cadena para llegar allí se ha convertido:

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

Los O representan espacios prohibidos ...

Así que presionará a la derecha,luego a la derecha de nuevo,y luego (a la derecha o arriba dependiendo de donde se haya creado el 4)entonces procederá a completar la cadena hasta que llegue:

Chain completed

Así que ahora el modelo y la cadena han vuelto a:

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

El segundo puntero,ha tenido mala suerte y su lugar principal ha sido ocupado.Es probable que falle,pero aún puede lograrlo:

Enter image description here

Aquí está el modelo y la cadena:

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

Cuando logra llegar a los 128 gana una fila entera se gana de nuevo:

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x



Answer 5 Nicola Pezzotti


Copio aquí el contenido de una publicación en mi blog


La solución que propongo es muy simple y fácil de implementar.Aunque,ha alcanzado la puntuación de 131040.Se presentan varios puntos de referencia de las prestaciones del algoritmo.

Score

Algorithm

Algoritmo de puntuación heurística

El supuesto en el que se basa mi algoritmo es bastante simple:si se quiere conseguir una puntuación más alta,el tablero debe mantenerse lo más ordenado posible.En particular,la configuración óptima viene dada por un orden decreciente lineal y monótono de los valores de los azulejos.Esta intuición te dará también el límite superior para un valor de azulejo:sdonde n es el número de azulejos en el tablero.

(Existe la posibilidad de alcanzar el azulejo 131072 si el azulejo 4 se genera al azar en lugar del azulejo 2 cuando sea necesario)

En las siguientes imágenes se muestran dos posibles formas de organizar el tablero:

enter image description here

Para imponer la ordenación de las fichas en un orden decreciente monótono, la puntuación se calcula como la suma de los valores linealizados en el tablero multiplicado por los valores de una secuencia geométrica con una relación común r <1.

s

s

Se podrían evaluar varios caminos lineales a la vez,la puntuación final será la máxima puntuación de cualquier camino.

Regla de decisión

La regla de decisión implementada no es muy inteligente,el código en Python se presenta aquí:

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

Una implementación de la minmax o la Expectiminimax seguramente mejorará el algoritmo.Obviamente una regla de decisión más sofisticada ralentizará el algoritmo y requerirá algún tiempo para ser implementada.Intentaré una implementación del minmax en un futuro próximo.(manténgase en sintonía)

Benchmark

  • T1-121 pruebas-8 caminos diferentes-r=0.125
  • T2-122 pruebas-8 caminos diferentes-r=0.25
  • T3-132 pruebas-8 caminos diferentes-r=0.5
  • T4-211 pruebas-2 caminos diferentes-r=0.125
  • T5-274 pruebas-2 caminos diferentes-r=0,25
  • T6-211 pruebas-2 caminos diferentes-r=0.5

enter image description here enter image description here enter image description here enter image description here

En el caso del T2,cuatro pruebas de cada diez generan el azulejo 4096 con una puntuación media des42000

Code

El código se puede encontrar en GiHub en el siguiente enlace: https://github.com/Nicola17/term2048-AI Está basado en term2048 y está escrito en Python. Implementaré una versión más eficiente en C ++ lo antes posible.