Escriba un programa que genere una secuencia ganadora de movimientos a la variante determinista del juego 2048. La secuencia debe tener la forma de una cadena de números 0-3, con 0: arriba, 1: derecha, 2: abajo, 3: izquierda. Por ejemplo, la cadena "1132" significa derecha derecha izquierda abajo. ¡El programa ganador es el código fuente más corto que llega hasta 2048!

Las reglas para el determinista 2048: el juego se juega en una cuadrícula de 4x4 que inicialmente contiene 1 ficha, en la esquina superior izquierda. Cada movimiento consiste en el comando "izquierda", "derecha", "arriba" o "abajo". El comando de la izquierda desliza todos los mosaicos de la cuadrícula hacia la izquierda, luego combina y suma como mosaicos comenzando desde la izquierda. Del mismo modo, el comando de la derecha desliza los mosaicos a la derecha, luego combina a partir de la derecha.

Cada ficha solo puede participar en una combinación por movimiento.

Después de un movimiento, se crea un nuevo mosaico 2 en la primera columna desde la izquierda con un espacio disponible, en el primer espacio disponible desde la parte superior de esa columna.

Por ejemplo, la secuencia "derecha derecha izquierda abajo" conduce a los estados

2___
____
____
____

2__2
____
____
____


2__4
____
____
____


24__
2___
____
____


2___
____
____
44__

El comando derecho aplicado a la fila _ 2 2 2 da como resultado _ _ 2 4 El comando derecho aplicado a la fila 2 2 2 2 da como resultado _ _ 4 4

Esta pregunta inspirada en http://jmfork.github.io/2048/

Python, 740 caracteres (665 caracteres comprimidos)

Código :

R=range
G=lambda:[[0]*4for _ in R(4)]
J=[(0,4,1),(2,-1,-1),(1,4,1)]
H=[0,-1,1]
def M(P,d):
 C=G();g,z=[(0,-1),(1,0),(0,1),(-1,0)][d];Q=H[g];W=H[z]
 while 1:
    N=[r[:]for r in P]
    for x in R(*J[g]):
     for y in R(*J[z]):
        s=N[y][x];q,w=y-W,x-Q;d=N[q][w];a,b,c=(((0,s,d),(1,0,s+d))[s==d],(0,0,s or d))[s<1 or d<1];
        if 2-a-(C[y][x]+C[q][w]>0):N[y][x]=b;N[q][w]=c;C[q][w]+=a
    if N==P:break
    P=N
 return N
def F(N):
 for x in R(4):
    for y in R(4):
     if N[y][x]==0:N[y][x]=2;return N
def Z(P,i):
 X=[d for d in R(4)if M(P,d)!=P]
 return i==0and(sum((256,c)[c>0] for v in P for c in v)+P[3][3]*10+P[3][2]*9,-1)or max((Z(F(M(P,d)),i-1)[0],d)for d in X)if X else(-1,-1)
B=G()
B[0][0]=2
h=''
while B[3][3]!=2048:_,X=Z(B,4);h+=`X`;B=F(M(B,X))
print h

(Mezcla pestañas con espacios para sangría para guardar algunos bytes)

Debo haber sido un asco en el golf porque si solo comprimo el código anterior, la codificación base-64 y execsolo tiene 665 caracteres. Lo siguiente es exactamente equivalente a lo anterior, sin solución codificada ni nada:

exec"""eJxVUl1vozAQfMa/wn2qnRjJcNzpDnf7QKS2qlRE+1IUy2oJkARdwl2hbT5+/a0NiXqSZXYH78zY
u0/QFe2qJrewKbaLqoi1lmYSLf909IU2LX1iETfkHjSTIhIBFywUfoALo8AhhtyBlhYMDKnqJX1g
mah4TOgMbhlXK3F01WOJxF06It8mRldGPcKdXhn1jJ+jIXS3bjY1DWLipaA7HRvrprNuMkM8m+wH
a5N7LEMlj1rwcAaPDvR6SPXB6L1Rb2IHB/9Z7P1HVSH6ZvTOqEIsRAmMoZ8eHTt3op9WnOseoDLW
KAIUuR12FbjwKjAK2ZslDf3CZ7NBYzobWK8lj0dZWKhRCko1/p5CQWxpCpDFi64ufhMvg5TQrn7/
6Fqauie8Yal9wC9XjeyNvtzS5dQSjVogz7Kh+o9sjv1oLF0OunKc1YmjOXXrAvBpTx4aJCvaivUf
W8bC7z9EyXV5LY2r/XR9cGFpw08+zfQ3g2sSyCEMzeSXbTce2RZ7xubshg0yXDSI44RhfDaSWxs5
rTd9zYbRIomdHJLgQVwQkjVcXpJhLJJB7AJCGf2MX0QOc5aIiKv1FF7zV5WAFUtEzjn52zXtO13/
AwRvylc=""".decode('base64').decode('zip')

Respuesta :

Toma ~ 47 segundos (17 segundos sin golf) para encontrar la secuencia de 1111 movimientos:

2221230232213120120232222222221221203211012312310123123101223113322222123230210302321222323223212322101202323123322032132021233212312332023123312111123231223113312312322312232123222021221332111332221012222312222302232021233212312332023212222222123221202332023120312123223221232232222222122122323222222212212232222222221322233231222322200232122312232313132022322212312332121332312320212211332312323223212320232322322133223213212323202123123321231313332122232310112113322212323222220130231233211313332122232312312223232231231232312222220232212312220212232312232123222021221332111332221012222312222302232021233212312332023212222222123221202332023120312123223221322323223312230230323312232313133232223233212312323123323222332222222132221321320323233223232121323212232013221323233032021223320231233220322203132123202123321231233202131321221111231213232131210212312232332132103123130213133213232213321323212332332212222123323322202302333121220222323232113123323221223032131201123212133123131222323313133313300123231332011222221223232331313313112312113230231121232332122323232321312323213212232313212323211330231231012

Con la siguiente posición final del tablero y movimiento:

   4    2   16    4
   2    8  128    8
   2    .    . 1024
   .    .    . 1024
Best move: s, with EV=25654

Curiosidades: la solución es 309 bytes comprimidos y 418 bytes si comprimidos y codificados en base64. Por lo tanto, sería un programa más corto simplemente decodificarlo e imprimirlo, pero eso no es nada divertido .

Explicacion :

Aquí hay un pastebin de la versión sin golf que imprime el tablero después de cada movimiento, ¡muy divertido de ver!

Es una IA de fuerza bruta muy simple. Asigna un EV para cada posición del tablero:

ev =   256 * number of spaces 
     + sum_of_values 
     + 10 * board_bottom_right 
     +  9 * board_bottom_2nd_right

Realiza una búsqueda en profundidad cuatro movimientos hacia adelante y selecciona el camino que conduce al EV más alto en cuatro movimientos. La función ev lo alienta a limpiar el tablero y a mantener las piezas de mayor valor en la esquina, lo que termina siendo bastante óptimo. ¡Es suficiente para llegar allí!

Si modifica la función EV para colocar un valor más alto en otros puntos del tablero, algo como:

1  1  1  1
1  1  1  1
1  1  9 10
1  9 10 11 

Esa función llega tan lejos como:

   2    8    4    2
  16   32   64   16
  64  128  512 1024
   2  256 2048 8192

16k :

Eureka! Con una anticipación de 5 pasos en lugar de un 4, y los siguientes pesos:

1  1  4  4 
1  1  4 10
1  1 14 16
1 16 18 20 

Casi se pone 32k, terminando en:

   2  128    4     2
  64  256  512     4
   4  128 1024  4096
  16 2048 8192 16384

La secuencia está aquí .

32k :

Sí, damas y caballeros, hemos alcanzado la marca de 32k. La función EV, en lugar de multiplicar cuadrados por una constante, eleva cada cuadrado a las siguientes potencias y las agrega. xsignifica que el cuadrado no está involucrado:

x x x 3
x x x 4 
x x 5 6
x 6 7 8

Todavía suma todos los valores una vez y agrega 256 por cada cuadrado vacío. Lookahead tenía 4 hasta 32k, y luego aumentó hasta 5, pero realmente no parece hacer mucho. Junta final:

   2  128    8     2
  64  256  512     4
   4  128 1024  2048
  16 4096 8192 32768

Pastebin de la secuencia de 24,625 movimientos .