Usando inteligencia artificial para resolver el juego 2048 (código JAVA)

• Abril 7, 2014
• Vasilis Vryniotis
• . 6 comentarios

Por ahora la mayoría de ustedes ha escuchado / jugado el 2048 juego por Gabriele Cirulli. Es un juego de mesa simple pero altamente adictivo que requiere que combine los números de las celdas para alcanzar el número 2048. Como era de esperar, la dificultad del juego aumenta a medida que más celdas se llenan de valores altos. Personalmente, aunque pasé una buena cantidad de tiempo jugando, nunca pude llegar a 2048. Entonces, lo más natural es tratar de desarrollar un solucionador de IA en JAVA para vencer el juego de 2048. 🙂

En este artículo discutiré brevemente mi enfoque para construir el Solucionador de Inteligencia Artificial del Juego 2048, describiré las heurísticas que utilicé y proporcionaré el código completo que está escrito en JAVA. El código es de código abierto bajo licencia GPL v3 y puede descargarlo desde Github.

Desarrollando el juego 2048 en JAVA

El juego original está escrito en JavaScript, así que tuve que reescribirlo en JAVA desde cero. La idea principal del juego es que tienes una cuadrícula de 4 × 4 con valores enteros, todos los cuales son potencias de 2. Las celdas con valor cero se consideran vacías. En cada punto durante el juego puedes mover los valores hacia 4 direcciones arriba, abajo, derecha o izquierda. Cuando realiza un movimiento, todos los valores de la cuadrícula se mueven hacia esa dirección y se detienen cuando llegan a los bordes de la cuadrícula o cuando llegan a otra celda con un valor distinto de cero. Si esa celda anterior tiene el mismo valor, las dos celdas se fusionan en una celda con doble valor. Al final de cada movimiento se agrega un valor aleatorio en el tablero en una de las celdas vacías y su valor es 2 con 0.9 de probabilidad o 4 con 0.1 de probabilidad. El juego termina cuando el jugador logra crear una celda con valor 2048 (gana) o cuando no hay otros movimientos que hacer (perder).

En la implementación original del juego, el algoritmo move-merge es un poco complicado porque tiene en cuenta todas las direcciones. Se puede realizar una buena simplificación del algoritmo si fijamos la dirección hacia la cual podemos combinar las piezas y rotar el tablero en consecuencia para realizar el movimiento. Maurits van der Schee recientemente ha escrito un artículo al respecto que creo que vale la pena ver.

Todas las clases están documentadas con comentarios Javadoc. A continuación proporcionamos una descripción de alto nivel de la arquitectura de la implementación:

1. Clase de la Junta

La clase de tablero contiene el código principal del juego, que es responsable de mover las piezas, calcular el puntaje, validar si el juego se termina, etc.

2. ActionStatus y Direction Enum

ActionStatus y Direction son 2 enumeraciones esenciales que almacenan el resultado de un movimiento y su dirección en consecuencia.

3. Clase ConsoleGame

ConsoleGame es la clase principal que nos permite jugar y probar la precisión del AI Solver.

4. Clase AIsolver

El AIsolver es la clase principal del módulo de Inteligencia Artificial que es responsable de evaluar el siguiente mejor movimiento dado una Junta en particular.

Técnicas de inteligencia artificial: poda Minimax vs alfa-beta

Se han publicado varios enfoques para resolver automáticamente este juego. El más notable es el desarrollado por mate overlan. Para resolver el problema probé dos enfoques diferentes, utilizando el algoritmo Minimax y la poda Alpha-beta.

Algoritmo Minimax

El Minimax es un algoritmo recursivo que se puede usar para resolver juegos de suma cero de dos jugadores. En cada estado del juego asociamos un valor. El algoritmo Minimax busca a través del espacio de posibles estados de juego creando un árbol que se expande hasta que alcanza una profundidad predefinida particular. Una vez que se alcanzan esos estados de hoja, sus valores se usan para estimar los de los nodos intermedios.

La idea interesante de este algoritmo es que cada nivel representa el turno de uno de los dos jugadores. Para ganar, cada jugador debe seleccionar el movimiento que minimiza la recompensa máxima del oponente. Aquí hay una buena presentación en video del algoritmo minimax:

[Contenido incrustado]

A continuación puede ver el seudocódigo del algoritmo Minimax:

función minimax (nodo, profundidad, maximizingPlayer)
    if profundidad = 0 or nodo es un nodo terminal
        volvemos el valor heurístico del nodo
    if maximizingPlayer bestValue: = -∞
        para cada hijo del nodo val: = minimax (hijo, profundidad - 1, FALSO)) bestValue: = max (bestValue, val);
        volvemos mejor valor
    más
        bestValue: = + ∞
        para cada hijo del nodo val: = minimax (hijo, profundidad - 1, TRUE)) bestValue: = min (bestValue, val);
        volvemos mejor valor
(* Llamada inicial para maximizar jugador *)
minimax (origen, profundidad, VERDADERO)

Poda alfa-beta

El Algoritmo de poda alfa-beta es una expansión de minimax, que disminuye en gran medida (poda) el número de nodos que debemos evaluar / expandir. Para lograr esto, el algoritmo estima dos valores, el alfa y el beta. Si en un nodo dado la beta es menor que alfa, entonces se puede podar el resto de los subárboles. Aquí hay una buena presentación en video del algoritmo alphabeta:

[Contenido incrustado]

A continuación puede ver el pseudocódigo del algoritmo de poda alfa-beta:

función alphabeta (nodo, profundidad, α, β, maximizingPlayer)
    if profundidad = 0 or nodo es un nodo terminal
        volvemos el valor heurístico del nodo
    if maximizando el jugador
        para cada hijo del nodo α: = max (α, alphabeta (hijo, profundidad - 1, α, β, FALSO))
            if β ≤ α
                romper (* corte β *)
        volvemos α
    más
        para cada hijo del nodo β: = min (β, alfabeta (hijo, profundidad - 1, α, β, TRUE))
            if β ≤ α
                romper (* α corte *)
        volvemos β
(* Llamada inicial *)
alphabeta (origen, profundidad, -∞, + ∞, VERDADERO)

¿Cómo se usa la IA para resolver el Juego 2048?

Para utilizar los algoritmos anteriores, primero debemos identificar a los dos jugadores. El primer jugador es la persona que juega el juego. El segundo jugador es la computadora que inserta valores al azar en las celdas del tablero. Obviamente, el primer jugador intenta maximizar su puntaje y lograr la fusión 2048. Por otro lado, la computadora en el juego original no está programada específicamente para bloquear al usuario seleccionando el peor movimiento posible para él, sino que inserta aleatoriamente valores en las celdas vacías.

Entonces, ¿por qué usamos técnicas de IA que resuelven juegos de suma cero y que suponen específicamente que ambos jugadores seleccionan el mejor movimiento posible para ellos? La respuesta es simple; a pesar de que es solo el primer jugador que intenta maximizar su puntaje, las opciones de la computadora pueden bloquear el progreso y evitar que el usuario complete el juego. Al modelar el comportamiento de la computadora como un jugador ortológico no aleatorio, nos aseguramos de que nuestra elección sea sólida independientemente de lo que la computadora juegue.

La segunda parte importante es asignar valores a los estados del juego. Este problema es relativamente simple porque el juego en sí mismo nos da una puntuación. Desafortunadamente, tratar de maximizar la puntuación por sí solo no es un buen enfoque. Una razón para esto es que la posición de los valores y el número de celdas vacías son muy importantes para ganar el juego. Por ejemplo, si dispersamos los valores grandes en celdas remotas, sería muy difícil para nosotros combinarlos. Además, si no tenemos celdas vacías disponibles, corremos el riesgo de perder el juego en cualquier momento.

Por todas las razones anteriores, varias heurísticas han sido sugeridos como el Monoticity, la suavidad y los Free Tiles del tablero. La idea principal no es utilizar la puntuación sola para evaluar cada estado del juego, sino construir una puntuación compuesta heurística que incluya las puntuaciones mencionadas anteriormente.

Finalmente, debemos tener en cuenta que, aunque he desarrollado una implementación del algoritmo Minimax, la gran cantidad de estados posibles hace que el algoritmo sea muy lento y, por lo tanto, es necesaria la poda. Como resultado de la implementación de JAVA, uso la expansión del algoritmo de poda Alpha-beta. Además, a diferencia de otras implementaciones, no elimino agresivamente las opciones de la computadora usando reglas arbitrarias, sino que las tomo en cuenta para encontrar el mejor movimiento posible del jugador.

Desarrollar una función de puntuación heurística

Para ganar el juego, probé varias funciones heurísticas diferentes. El que encontré más útil es el siguiente:

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

La función anterior combina el puntaje real del tablero, el número de celdas / mosaicos vacíos y una métrica llamada puntaje de agrupamiento que discutiremos más adelante. Veamos cada componente con más detalle:

1. Puntuación real: Por razones obvias, cuando calculamos el valor de un tablero, debemos tener en cuenta su puntaje. Los tableros con puntajes más altos generalmente se prefieren en comparación con los tableros con puntajes más bajos.
2. Número de celdas vacías: Como mencionamos anteriormente, mantener pocas celdas vacías es importante para garantizar que no perdamos el juego en los próximos movimientos. Los estados de tablero con más celdas vacías generalmente se prefieren en comparación con otros con menos celdas. Se plantea una pregunta sobre cómo valoraríamos esas celdas vacías. En mi solución, los ponderé por el logaritmo de la puntuación real. Esto tiene el siguiente efecto: cuanto más bajo es el puntaje, menos importante es tener muchas celdas vacías (esto es porque al comienzo del juego combinar las celdas es bastante fácil). Cuanto más alto sea el puntaje, más importante es garantizar que tengamos celdas vacías en nuestro juego (Esto se debe a que al final del juego es más probable que pierda debido a la falta de celdas vacías.
3. Puntuación de agrupamiento: Usamos el puntaje de agrupamiento que mide cuán dispersos están los valores de nuestro tablero. Cuando las celdas con valores similares están cerca, son más fáciles de combinar, lo que significa que es más difícil perder el juego. En este caso, el puntaje de agrupamiento tiene un valor bajo. Si los valores del tablero están dispersos, entonces este puntaje obtiene un valor muy grande. Este puntaje se resta de los dos puntajes anteriores y actúa como una penalización que asegura que se preferirán los tableros agrupados.

En la última línea de la función nos aseguramos de que la puntuación no sea negativa. El puntaje debe ser estrictamente positivo si el puntaje del tablero es positivo y cero solo cuando el tablero del puntaje es cero. Las funciones max y min se construyen para que obtengamos este efecto.

Finalmente, debemos tener en cuenta que cuando el jugador alcanza un estado de juego terminal y no se permiten más movimientos, no usamos el puntaje anterior para estimar el valor del estado. Si el juego se gana, asignamos el valor entero más alto posible, mientras que si el juego se pierde, asignamos el valor no negativo más bajo (0 o 1 con una lógica similar a la del párrafo anterior).

Más sobre el puntaje de agrupamiento

Como dijimos anteriormente, el puntaje de agrupamiento mide qué tan dispersos están los valores del tablero y actúa como una penalización. Construí este puntaje de tal manera que incorpora consejos / reglas de los usuarios que "dominaron" el juego. La primera regla sugerida es que intente mantener cerradas las celdas con valores similares para combinarlas más fácilmente. La segunda regla es que las celdas de alto valor deben estar cerca una de la otra y no aparecer en el medio del tablero, sino en los lados o esquinas.

Veamos cómo se estima el puntaje de agrupamiento. Para cada celda del tablero, estimamos la suma de las diferencias absolutas de sus vecinos (excluyendo las celdas vacías) y tomamos la diferencia promedio. La razón por la que tomamos los promedios es para evitar contar más de una vez el efecto de dos celdas vecinas. El puntaje de agrupamiento total es la suma de todos esos promedios.

El puntaje de agrupamiento tiene los siguientes atributos:

1. Obtiene un valor alto cuando los valores del tablero están dispersos y un valor bajo cuando las celdas con valores similares están cerca una de la otra.
2. No sobrepasa el efecto de dos celdas vecinas.
3. Las celdas en los márgenes o esquinas tienen menos vecinos y, por lo tanto, puntajes más bajos. Como resultado, cuando los valores altos se colocan cerca de los márgenes o esquinas, tienen puntajes más pequeños y, por lo tanto, la penalización es menor.

La precisión del algoritmo.

Como se esperaba, la precisión (también conocida como el porcentaje de juegos ganados) del algoritmo depende en gran medida de la profundidad de búsqueda que usemos. Cuanto mayor sea la profundidad de la búsqueda, mayor será la precisión y más tiempo requerirá para ejecutarse. En mis pruebas, una búsqueda con profundidad 3 dura menos de 0.05 segundos, pero ofrece un 20% de posibilidades de ganar, una profundidad de 5 dura aproximadamente 1 segundo, pero ofrece un 40% de posibilidades de ganar y, finalmente, una profundidad de 7 dura 27-28 segundos y da alrededor del 70-80% de posibilidades de ganar.

Expansiones futuras

Para aquellos de ustedes que estén interesados ​​en mejorar el código, aquí hay algunas cosas que pueden considerar:

1. Mejora la velocidad: Mejorar la velocidad del algoritmo le permitirá usar una mayor profundidad y así obtener una mayor precisión.
2. Crear gráficos: Hay una buena razón por la cual la implementación de Gabriele Cirulli se hizo tan famosa. ¡Es bonito! No me molesté en desarrollar una GUI, sino que imprimí los resultados en la consola, lo que hace que el juego sea más difícil de seguir y jugar. Crear una buena GUI es imprescindible.
3. Sintonizar heurística: Como mencioné anteriormente, varios usuarios han sugerido diferentes heurísticas. Se puede experimentar con la forma en que se calculan los puntajes, los pesos y las características del tablero que se tienen en cuenta. Se supone que mi enfoque de medir la puntuación del clúster combina otras sugerencias, como la monotonicidad y la suavidad, pero todavía hay margen de mejora.
4. Afinando la profundidad: También se puede intentar ajustar / ajustar la profundidad de la búsqueda según el estado del juego. También puedes usar el Profundización iterativa búsqueda en profundidad algoritmo que se sabe que mejora el algoritmo de poda alfa-beta.

No olvides descargar el código JAVA de Github y experimentar. ¡Espero que hayas disfrutado esta publicación! Si lo hizo, tómese un momento para compartir el artículo en Facebook y Twitter. 🙂