Escreva um programa que gere uma sequência vencedora de jogadas para a variante determinística do jogo 2048. A sequência deve estar na forma de uma sequência de números 0-3, com 0: para cima, 1: para a direita, 2: para baixo, 3: esquerda. Por exemplo, a cadeia "1132" significa direita direita esquerda para baixo. O programa vencedor é o código-fonte mais curto que chega a 2048!

As regras para 2048 determinístico: O jogo é jogado em uma grade 4x4 contendo inicialmente 1 peça, no canto superior esquerdo. Cada movimento consiste no comando "esquerda", "direita", "para cima" ou "para baixo". O comando à esquerda desliza todos os blocos da grade para a esquerda e combina e soma como blocos a partir da esquerda. Da mesma forma, o comando desliza lado a lado para a direita e combina a partir da direita.

Cada bloco só pode participar de uma combinação por jogada.

Após uma movimentação, um novo bloco 2 é criado na primeira coluna da esquerda com um espaço disponível, no primeiro espaço disponível na parte superior dessa coluna.

Por exemplo, a sequência "direita direita esquerda para baixo" leva aos estados

2___
____
____
____

2__2
____
____
____


2__4
____
____
____


24__
2___
____
____


2___
____
____
44__

O comando à direita aplicado à linha _ 2 2 2 resulta em _ _ 2 4 O comando à direita aplicado à linha 2 2 2 2 resulta em _ _ 4 4

Esta pergunta foi inspirada em http://jmfork.github.io/2048/

Python, 740 caracteres (665 caracteres compactados)

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

(Mistura guias com espaços para recuo para salvar alguns bytes)

Eu devo ter gostado muito de jogar golfe, porque se eu apenas comprimir o código acima, a base-64 o codifica, e execsão apenas 665 caracteres. O seguinte é exatamente equivalente ao acima, nenhuma solução codificada ou qualquer coisa:

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')

Resposta :

Demora ~ 47 segundos (17 segundos sem ser destruído) para encontrar a sequência de 1111 movimentos:

222123023221312012023222222222122120321101231231012312310122311332222212323021030232122232322321232210120232312332203213202123321231233202312331211112323122311331231232231223212322202122133211133222101222231222230223202123321231233202321222222212322120233202312031212322322123223222222212212232322222221221223222222222132223323122232220023212231223231313202232221231233212133231232021221133231232322321232023232232213322321321232320212312332123131333212223231011211332221232322222013023123321131333212223231231222323223123123231222222023221231222021223231223212322202122133211133222101222231222230223202123321231233202321222222212322120233202312031212322322132232322331223023032331223231313323222323321231232312332322233222222213222132132032323322323212132321223201322132323303202122332023123322032220313212320212332123123320213132122111123121323213121021231223233213210312313021313321323223232321212222123323322202302333121220203232323232121232123212321232123232

Com a seguinte posição final do tabuleiro e mova-se:

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

Curiosidades: a solução tem 309 bytes com gzip e 418 bytes se gzipped e codificado em base64. Portanto, seria um programa mais curto decodificar e imprimi-lo, mas isso não é nada divertido .

Explicação :

Aqui está uma pasta da versão não destruída que imprime o quadro após cada movimento, muito divertido de assistir!

É uma IA de força bruta muito simples. Ele atribui um EV para cada posição do quadro:

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

Ele faz uma pesquisa profunda quatro movimentos à frente e escolhe o caminho que leva ao VE mais alto em quatro movimentos. A função ev a incentiva a limpar o tabuleiro e a manter as peças de maior valor no canto, o que acaba sendo ótimo. É o suficiente para chegar lá!

Se você modificar a função EV para colocar um valor mais alto em outros pontos da placa, algo como:

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

Essa função chega até:

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

16k :

Eureka! Com um cabeçote de 5 etapas em vez de um 4 e os seguintes pesos:

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

Quase chega a 32k, terminando em:

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

A sequência está aqui .

32k :

Sim, senhoras e senhores, atingimos a marca de 32k. A função EV, em vez de multiplicar quadrados por uma constante, eleva cada quadrado aos seguintes poderes e os adiciona. xsignifica que o quadrado não está envolvido:

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

Ainda soma todos os valores uma vez e adiciona 256 para cada quadrado vazio. Lookahead tinha 4 até 32k, e depois aumentou para 5, mas não parece fazer muito. Placa final:

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

Pasta da sequência de 24.625 movimentos .