algorithm - tom - ¿Cuál es el algoritmo ciego óptimo para el juego, 2048?

que es el juego 2048

Question

El juego 2048 ha explotado en popularidad desde su lanzamiento en febrero de 2014. Para obtener una descripción del juego y una discusión de los algoritmos óptimos, consulte ¿Cuál es el algoritmo óptimo para el juego 2048? . Aquí está el código fuente .

Un algoritmo ciego para 2048 es uno que no puede ver el tablero; la única respuesta que recibe el algoritmo es si se produjo o no un intento de deslizamiento (podemos suponer que un bloqueo bloqueado produce un pitido audible). Un algoritmo ciego es prácticamente útil para comenzar en 2048 sin tener que prestar al juego toda su atención.

Aquí está mi pregunta específica : ¿hay un algoritmo ciego para 2048 que sea mejor que un puntaje promedio de 3500 en 10 ^ 6 intentos? (solo publica una respuesta que hayas validado)

Este es el rendimiento del algoritmo LADDER, que puede anotarse como (LD * RD *) * (+ U). Es decir, uno gira sobre "izquierda, abajo repetidamente hasta que se bloquea, derecha, abajo se repite hasta que se bloquea" y presiona hacia arriba si la izquierda, derecha y abajo están bloqueadas, lo que ocurre si la fila superior está completamente vacía y la parte inferior Las filas están completamente llenas. Llamo a este algoritmo LADDER por las letras LDDR, y porque me imagino bajando escaleras como Mario en Donkey Kong. La motivación para el algoritmo es mantener un gradiente creciente desde la parte superior a la parte inferior de la placa, similar a muchos de los algoritmos no ciegos.

Aquí hay un histograma para 10 ^ 6 intentos de LADDER coloreado por azulejo superior en la tabla final con un ancho de contenedor 32 y una media de 3478.1. Generé estos datos simulando el juego y el algoritmo en Python, usando la probabilidad .9 de que cada nueva casilla es un 2, como en el juego original. No puedes ver los juegos 1024 en esta escala vertical, pero están distribuidos de forma dispersa entre 8000 y 16000. La estructura fractal se relaciona con el número de ocurrencias del azulejo superior, el segundo desde el azulejo superior, y así sucesivamente. En comparación, la combinación aleatoria de botones dio una media de aproximadamente 800 en 10 ^ 4 ensayos.

Answer 1

Lo más importante en el juego de 2048 es concentrar los números altos a lo largo de las fronteras y no en el medio. Por lo tanto, una estrategia muy buena es colocar todo lo que esté en el fondo el mayor tiempo posible. Su algoritmo LADDER hace esto, pero me gustaría concentrarme más en el lado izquierdo y no cambiar completamente al lado derecho. Este es el algoritmo en pseudo código:

while(true)
    {
    if (down)
        continue;
    elseif(left)
        continue;
    elseif (right)
        continue;
    else
        {
        up;
        down; //if forced to go up; go back down immediately
        }
    }

Usando su convención esto sería:

((D*L)*R)U

en palabras: baja todo lo que puedas; si tu no puedes; ve a la izquierda; si no puedes ir a la izquierda; ve a la derecha. Rara vez tendrás que subir.

Como no tendré tiempo en poco tiempo para implementar esto para usarlo 10⁶ veces; Espero que alguien más pueda dar la estadística correcta para esto, pero supongo que esto superará su algoritmo LADDER.