PDF de programación - Algoritmos eficientes para la resolución del juego 2048

„2048 Solution‟: Algoritmos eficientes para la

resolución del juego 2048

Beltracchi Rodrigo Oscar, Dahl Juan Ricardo, Rizzalli Ayelén Analía.

Universidad Nacional del Centro de la Provincia de Buenos Aires



fue desarrollado como proyecto

Resumen. “2048 Solution”
final
correspondiente a una materia de una carrera de Informática dictada en el
segundo año de la misma. La materia aborda conceptos de análisis y diseño de
algoritmos, en especial técnicas algorítmicas para resolver problemas de
mediana escala. El objetivo de este proyecto fue implementar soluciones
eficientes para el juego “2048”, haciendo énfasis en la aplicación de técnicas de
diseño, analizando los comportamientos para cada solución, la complejidad
temporal de los algoritmos implementados y el análisis empírico del tiempo de
ejecución para cada una soluciones propuestas.
“2048 Solution” ha sido abordado desde las técnicas de “Backtracking”,
“Búsquedas Heurísticas” y “Branch and bound”. Se implementó una interfaz
gráfica que permite una visualización similar a la disponible para los
dispositivos móviles, que permite ejecutar los distintos algoritmos y alcanzar
resultados hasta la potencia de dos ´8192´, así como brindar al usuario la
posibilidad de resolver el juego por su cuenta.

1 Introducción

El juego 2048 fue creado por un joven italiano llamado Gabriele Cirulli, quien se
inspiró en dos juegos ya existentes: 1024! y Threes . El objetivo del juego es llegar a
la potencia de dos más grande posible (2048 o incluso mayor). Para ello, se dispone
de un tablero de 4x4 en el que se pueden realizar como máximo cuatro movimientos
posibles (derecha, izquierda, arriba, abajo). Dependiendo el movimiento, si dos
casillas son adyacentes e iguales, se combinarán en una única baldosa con su
respectiva suma. Cabe aclarar que, en los movimientos ´derecha´ e ízquierda´ se
juntarán solo las casillas adyacentes respecto de las filas del tablero y, en los
movimientos arriba y abajo harán lo propio con respecto a las columnas.

Además, cada vez que se realice un nuevo movimiento, y el tablero ya esté
modificado con las colisiones correspondientes, aparece una ficha en una posición
aleatoria, cuyo valor puede ser de 2 o 4. Se ubicará en cualquiera de los espacios
libres del tablero y pasa a formar parte del mismo, pudiendo ser usada para futuras
colisiones.

El juego finaliza de forma afortunada cuando una casilla contiene el valor 2048 -
de ahí surge su nombre- pero puede continuar en busca de una potencia mayor. No
obstante, si un jugador queda sin algún movimiento legal (es decir, ya no quedan

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-761149 espacios vacíos y no existen baldosas adyacentes con el mismo valor), el juego
termina.

A pesar de su fácil formulación es un problema duro de resolver. Como muchas
soluciones para juegos, esta no es trivial por las distintas estrategias que se pueden
plantear para su solución, pudiendo transformarse en un problema intratable. Es
importante destacar que uno de los principales objetivos de la materia incluye aplicar
buenas prácticas de programación aplicando técnicas de diseño, ejercitando en
algunos casos con la resolución de distintos tipos de juegos, usando un enfoque
metodológico de desarrollo no solo en los juegos sino en distintas aplicaciones
tradicionales.

En las siguientes secciones se profundizará acerca de las características del juego,
describiendo el desafío computacional que implica, haciendo un análisis
detallado de los algoritmos implementados, para luego abordar con el diseño e
implementación del proyecto, las soluciones encontradas y las conclusiones que se
desprenden de su realización. El Anexo A contiene un diagrama de interacción entre
clases/métodos más relevantes de la implementación y el Anexo B contiene el código
de los algoritmos principales para resolver el juego.

2 Diseño de la solución. Descripción y Análisis de los Algoritmos

Como se mencionó anteriormente, el objetivo de este trabajo fue implementar
distintos algoritmos basados en técnicas de diseño de algoritmos para la solución del
“2048”. Para llegar al diseño es necesario definir lo que significa el espacio de
búsqueda particular para este juego. Luego, se hace un análisis exhaustivo de las
distintas estrategias dentro del marco de
la
implementación. A continuación se detallan cada una de ellas.

técnicas utilizadas para

las

2.1 El espacio de búsqueda

Un aspecto común estudiado en cada una de las técnicas implementadas es la
organización de los datos de forma tal que sea posible lograr disponer todos los
escenarios del juego en una única estructura. Luego, cada algoritmo tendrá la tarea de
realizar un recorrido eficiente en busca de la solución. De este modo, el espacio de
búsqueda se describió como un árbol cuya raíz es el tablero inicial. Cada nodo del
árbol posee como máximo cuatro hijos (movimientos posibles). Desarrollando cada
uno de los nodos con sus respectivos hijos se genera un árbol que contiene todas las
combinaciones posibles del juego. La Figura 1 ilustra este espacio de forma parcial.

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-761150 Fig.1. Espacio parcial de búsqueda para „2048‟


Un ejemplo para el árbol es un nodo que se genera a partir de la ejecución de un



movimiento hacia arriba, como muestra la figura 2.



Fig.2. Métodos del movimiento “arriba”.



EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-761151 2.2. Backtracking

„Backtracking‟ o „vuelta atrás‟ es una técnica usada para resolver problemas cuya
solución involucra el recorrido de un gran espacio de búsqueda [5] que esta
determinado por el pseudo-código de la figura 3. La idea es, sistemáticamente, ir
explorando y eliminando posibilidades. El espacio de búsqueda en este tipo de
circunstancias se modela en forma de árbol evitando así, posibles repeticiones y
ciclos. Determinar si un nodo es solución, diseñar una poda acorde y determinar los
hijos de cada estado son los aspectos a definir antes de utilizar dicho algoritmo. En
general, la solución puede expresarse como una tupla (x1, x2,…, xn), donde los xi son
elegidos de un conjunto finito Si.

La poda es una función que permite averiguar si una secuencia de decisiones, la

solución actual en curso, cumple las restricciones propias del problema.

Por último, determinar correctamente los hijos de cada estado es una forma
sistemática y organizada de generar y recorrer el espacio de búsqueda. Para adaptar el
problema a dicha estrategia, es necesario definir correctamente las características
mencionadas anteriormente.

En una primera instancia, la tupla (x1, x2,…, xn) que comprende la solución del
problema está compuesta por cada tablero que nos conlleva al resultado esperado con
su respectivo orden.

En lo que respecta a la función hijos, está dada siempre por cuatro nodos -sin
incluir la poda- los cuales son los escenarios posibles luego de aplicar alguno de los
movimientos permitidos (derecha, izquierda, arriba, abajo). Los mismos se perciben
fácilmente una vez que se diseñó el espacio de búsqueda [4][7].

Habitualmente, cuando se usa la técnica de “Bactracking” es importante identificar
cada uno de los hijos pero, sin importar el orden en el cual van a ser ejecutados en
tiempo de ejecución. En otras palabras, no existen prioridades entre ellos e incluso,
este caso pareciera pertenecer a este tipo de problemas. Sin embargo, luego de
estudiar minuciosamente algunas tácticas para ganar el juego, se observó que la
búsqueda del algoritmo puede mejorar o empeorar de acuerdo a la disposición de los
hijos.

Una estrategia de las recién mencionadas para resolver el juego consiste en
elegir una esquina tratando en todo momento de tener el número de mayor potencia en
el rincón elegido. Se eligió el rincón superior izquierdo, por lo que los hijos se
generan de la siguiente forma: izquierda, arriba, abajo, derecha. Repitiendo estos
pasos se provoca la llamada “escalera” en la que cada casilla contiene una potencia
menor de modo que al “chocar” las más pequeñas, en una secuencia de pasos aumenta
la potencia mayor. Así, se debe evitar movimientos que “desordenen” dicha
disposición. En este caso mover hacia abajo pondría en riesgo la partida por lo que se
lo colocó en última instancia en la lista de movimientos. A su vez, la poda que
caracteriza esta implementación es determinada estrictamente solo por las reglas del
juego. Específicamente la poda se define por si es factible o no realizar el movimiento
en cuestión.

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-761152

Fig.3. Pseudo-código de generación del espacio de búsqueda.



Esta técnica reduce el espacio de búsqueda mediante la implementación de la
heurística A que evalúa los tableros generados en cada nodo, permitiendo realizar una
mejor elección de la jugada a seguir y evitando también la generación de nodos sin
cambio.

Este algoritmo para darle un valor a la jugada se basó en una estrategia que consiste
en ponderar