¿Cuál es el algoritmo óptimo para el juego 2048?
Introducción
2048 es un emocionante juego de cambio de fichas, donde movemos fichas para combinarlas, con el objetivo de valores de fichas cada vez más grandes.
en este tutorial, vamos a investigar un algoritmo para jugar 2048, uno que ayudará a decidir los mejores movimientos a hacer en cada paso para obtener la mejor puntuación.
Cómo jugar 2048
Un juego de 2048 se juega en un tablero de 4×4., Cada posición en el tablero puede estar vacía o puede contener una ficha, y cada ficha tendrá un número en ella.
cuando comencemos, el tablero tendrá dos fichas en ubicaciones aleatorias, cada una de las cuales tiene un «2» o un «4» – cada una tiene una probabilidad independiente del 10% de ser un «4», o de lo contrario a es un «2».
Los movimientos se realizan desplazando todas las fichas hacia un borde: hacia arriba, hacia abajo, hacia la izquierda o hacia la derecha., Al hacer esto, todas las fichas con el mismo valor que son adyacentes entre sí y se mueven juntas se fusionarán y terminarán con una nueva ficha igual a la suma de las dos anteriores:
después de que hayamos hecho un movimiento, se colocará una nueva ficha en el tablero. Esto se coloca en una ubicación aleatoria, y será un » 2 «o un» 4 «de la misma manera que las fichas iniciales:» 2 «el 90% del tiempo y» 4 » El 10% del tiempo.
el juego continúa hasta que no hay más movimientos posibles.
en general, el objetivo del juego es alcanzar una sola ficha con un valor de «2048»., Sin embargo, el juego no se detiene aquí, y podemos seguir jugando hasta donde sea posible, apuntando a la ficha más grande posible. En teoría, este es un azulejo con el valor «131,072».
explicación del problema
resolver este juego es un problema interesante porque tiene un componente Aleatorio. Es imposible predecir correctamente no solo dónde se colocará cada nueva ficha, sino si será un «2» o un «4».
como tal, es imposible tener un algoritmo que resuelva correctamente el rompecabezas cada vez., Lo mejor que podemos hacer es determinar cuál es probablemente la mejor jugada en cada etapa y jugar el juego de probabilidad.
en cualquier momento, solo hay cuatro movimientos posibles que podemos hacer. A veces, algunos de estos movimientos no tienen ningún impacto en el tablero y por lo tanto no vale la pena hacer – por ejemplo, en el tablero de arriba un movimiento de «abajo» no tendrá ningún impacto, ya que todas las fichas ya están en el borde inferior.
el desafío es entonces determinar cuál de estos cuatro movimientos va a ser el que tenga el mejor resultado a largo plazo.,
nuestro algoritmo se basa en el algoritmo Expectimax, que es en sí mismo una variación del algoritmo Minimax, pero donde las posibles rutas a través de nuestro árbol se ponderan por la probabilidad de que ocurran.
esencialmente, tratamos el juego como un juego de dos jugadores:
- El Jugador uno-el jugador humano – puede cambiar el tablero en una de cuatro direcciones
- El Jugador dos – el jugador de la computadora – puede colocar una ficha en una ubicación vacía en el tablero
basado en esto, podemos generar un árbol de resultados de cada movimiento, ponderado por la probabilidad de que cada movimiento suceda., Esto puede darnos los detalles necesarios para determinar qué movimiento humano es probable que dé el mejor resultado.
3.1. Diagrama de flujo del juego
el flujo general de cómo funciona el juego:
podemos ver inmediatamente el aspecto aleatorio del juego en el proceso «agregar azulejo Aleatorio», tanto en el hecho de que estamos encontrando un cuadrado Aleatorio para agregar el azulejo, y estamos seleccionando un valor aleatorio para el azulejo.
nuestro desafío es entonces decidir qué hacer en el paso» determinar el siguiente movimiento». Este es nuestro algoritmo para jugar el juego.,
el desbordamiento general de esto parece engañosamente simple:
todo lo que necesitamos hacer es simular cada uno de los movimientos posibles, determinar cuál da el mejor resultado y luego usarlo.
así que ahora hemos reducido nuestro algoritmo para simular cualquier movimiento dado y generar alguna puntuación para el resultado.
Este es un proceso de dos partes. El primer pase es para ver si el movimiento es posible, y si no, abortar temprano con una puntuación de «0»., Si el movimiento es posible, entonces pasaremos al algoritmo real donde determinaremos qué tan bueno es un movimiento:
3.2. Determinar el siguiente movimiento
la parte clave de nuestro algoritmo hasta ahora es simular un movimiento, y la parte clave de eso es cómo generamos una puntuación para cada posible movimiento. Aquí es donde entra en juego Nuestro algoritmo Expectimax.
simularemos cada movimiento posible de ambos jugadores durante varios pasos, y veremos cuál de ellos da el mejor resultado. Para el jugador humano, esto significa cada uno de los movimientos» arriba»,» abajo»,» izquierda «y» derecha».,
para el jugador de la computadora, esto significa colocar un «2» o un «4» en cada ubicación vacía posible:
Este algoritmo es recursivo, con cada paso recursivo deteniéndose solo si es una cierta profundidad del movimiento real en el juego real.,ul>
- simular cada movimiento humano posible
- Para cada uno de estos
- simular cada movimiento humano posible
- Para cada uno de estos
- Recurse de nuevo en el algoritmo
- devuelva la puntuación calculada a partir de este movimiento humano
- agregue la puntuación calculada a partir de este movimiento del equipo, ponderada por una probabilidad de que este movimiento ocurra
Cuando hemos terminado esto, sumamos todas las puntuaciones calculadas, y esta es la puntuación final para el movimiento que queremos hacer desde el tablero de juego actual., Debido a que hacemos esto cuatro veces, una por cada posible movimiento desde el tablero de juego actual, terminamos con cuatro puntuaciones, y la más alta de esas es la jugada a realizar.
3.3. Puntuación de una posición en el tablero
en este punto, lo único que queda por hacer es calcular una puntuación para un tablero. Esta no es la misma puntuación que utiliza el juego, pero debe tener en cuenta lo buena que es una posición desde la que seguir jugando.
hay un gran número de maneras que esto se puede lograr mediante la adición de varios factores junto con ponderaciones apropiadas., Por ejemplo:
- Number of empty locations
- Number of possible merges – i.e., number of times the same number is in two adjacent locations
- the largest value in any location
- suma de todas las ubicaciones
- Monotonicity of the board – esto es lo bien que está estructurada la placa, de modo que los valores de ubicación aumentan en una sola dirección.
pseudocódigo
ahora que sabemos cómo va a funcionar el algoritmo, ¿cómo se ve esto? Exploremos algunos pseudocódigos que describen el algoritmo con más detalle.,
no estamos interesados en el juego real del juego, solo en el algoritmo para determinar los movimientos, así que empecemos por ahí:
como antes, esto nos lleva al punto en el que estamos simulando cada uno de los movimientos posibles desde el tablero inicial y devolviendo el que puntúa mejor. Esto nos deja con la necesidad de generar puntuaciones para los tableros recién simulados.
hemos añadido un límite de profundidad para que podamos detener el procesamiento después de un tiempo., Debido a que estamos trabajando con un algoritmo recursivo, necesitamos una forma de detenerlo de lo contrario, potencialmente se ejecutará para siempre:
esto nos da nuestra recursión, simulando cada posible movimiento humano y de computadora para un cierto número de pasos y decidiendo qué movimientos humanos dan el mejor resultado posible.
lo único que queda es elaborar una puntuación final para cualquier posición en el tablero. No hay un algoritmo perfecto para esto, y diferentes factores darán diferentes resultados.,
la Optimización del Rendimiento
hasta el momento tenemos un algoritmo que intentará resolver el juego, pero no es tan eficiente como podría ser. Debido a la naturaleza aleatoria del juego, es imposible tener un solucionador perfectamente optimizado: siempre habrá algún nivel de repetición simplemente debido a la naturaleza del proceso.
al menos podemos hacer nuestro mejor esfuerzo para reducir el trabajo que no necesitamos hacer.,
ya estamos haciendo un poco de optimización en el algoritmo anterior al no procesar ningún movimiento que no tenga ningún impacto en el juego. Sin embargo, hay otras formas en las que podemos reducir el trabajo que debemos hacer, como rastrear la probabilidad acumulada de movimientos y detenernos cuando eso se vuelve demasiado bajo. Esto tiene el riesgo de eliminar la solución perfecta, pero si la probabilidad es tan baja, entonces es casi seguro que no sucederá de todos modos.
También podemos determinar dinámicamente el límite de profundidad con el que trabajar., Nuestro pseudocódigo anterior tiene un límite rígido de 3, pero podríamos calcularlo dinámicamente en función de la forma del tablero al comienzo de nuestros cálculos, por ejemplo, ajustándolo al número de cuadrados vacíos o al número de fichas distintas en el tablero. Esto significaría que atravesamos menos movimientos desde tableros que tienen menos posibilidades de expansión.
Además, debido a que es posible volver a visitar las mismas posiciones del tablero varias veces, podemos recordarlas y almacenar en caché la puntuación de esas posiciones en lugar de volver a computarlas cada vez., Potencialmente podemos generar todas las posiciones posibles del tablero antes de tiempo, pero hay un gran número de ellas – 281,474,976,710,656 diferentes posiciones posibles del tablero usando fichas hasta 2048 – por lo que esto probablemente no sea factible.
sin embargo, la optimización más importante que podemos hacer es ajustar el algoritmo para generar las puntuaciones del tablero. Esto funciona para decidir qué tan bueno es el tablero para continuar jugando y los factores y ponderaciones que usamos para esto están directamente relacionados con qué tan bien se juega nuestro algoritmo.,
Conclusión
2048 es un muy interesante juego para intentar resolver. No hay una manera perfecta de resolverlo, pero podemos escribir heurísticas que buscarán las mejores rutas posibles a través del juego.
los mismos principios generales funcionan para cualquier juego de dos jugadores – por ejemplo, el ajedrez-donde no se puede predecir lo que el otro jugador hará con ningún grado de certeza.
¿Por qué no intentar escribir una implementación de esto y ver qué tan bien funciona?