Solve a deterministic version of 2048 using the fewest bytes

Question

Write a program that generates a winning sequence of moves to the deterministic variant of the game 2048. The sequence should be in the form of a string of numbers 0-3, with 0: up, 1: right, 2: down, 3: left. For example, the string "1132" means right right left down. The winning program is the shortest source code that gets to 2048!

The rules to deterministic 2048: The game is played on a 4x4 grid initially containing 1 tile, in the upper left-hand corner. Each move consists of the command "left", "right", "up" or "down". The command left slides all the tiles on the grid to the left, then combines and sums like tiles starting from the left. Likewise, the command right slides tiles to the right, then combines starting from the right.

Each tile can only participate in one combination per move.

After a move, a new 2 tile is created in the first column from the left with an available space, in the first available space from the top in that column.

For example, the sequence "right right left down" leads to the states

2___
____
____
____

2__2
____
____
____


2__4
____
____
____


24__
2___
____
____


2___
____
____
44__

The command right applied to the row _ 2 2 2 results in _ _ 2 4 The command right applied to the row 2 2 2 2 results in _ _ 4 4

This question inspired by http://jmfork.github.io/2048/

Answer 1

Python, 740 characters (665 characters compressed)

Code:

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

(Mixes tabs with spaces for indentation to save a few bytes)

I must have sucked at golfing it because if I just compress the above code, base-64 encode it, and exec it, it's only 665 characters. The following is exactly equivalent to the above, no hard-coded solution or anything:

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

Answer:

Takes ~47 seconds (17 seconds ungolfed) to find the 1111-move sequence:

2221230232213120120232222222221221203211012312310123123101223113322222123230210302321222323223212322101202323123322032132021233212312332023123312111123231223113312312322312232123222021221332111332221012222312222302232021233212312332023212222222123221202332023120312123223221232232222222122122323222222212212232222222221322233231222322200232122312232313132022322212312332121332312320212211332312323223212320232322322133223213212323202123123321231313332122232310112113322212323222220130231233211313332122232312312223232231231232312222220232212312220212232312232123222021221332111332221012222312222302232021233212312332023212222222123221202332023120312123223221322323223312230230323312232313133232223233212312323123323222332222222132221321320323233223232121323212232013221323233032021223320231233220322203132123202123321231233202131321221111231213232131210212312232332132103123130213133213232213321323212332332212222123323322202302333121220222323232113123323221223032131201123212133123131222323313133313300123231332011222221223232331313313112312113230231121232332122323232321312323213212232313212323211330231231012

With the following final board position and move:

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

Trivia: the solution is 309 bytes gzipped and 418 bytes if gzipped and base64-encoded. Thus it would be a shorter program to just decode that and print it out, but that is no fun at all.

Explanation:

Here's a pastebin of the ungolfed version which prints out the board after each move, very fun to watch!

It's a very simple brute-force AI. It assigns an EV for each board position:

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

It does a depth-first search four moves ahead and picks the path that leads to the highest EV in four moves. The ev function encourages it to clean up the board and to keep the highest-valued pieces in the corner, which ends up being pretty optimal. It's enough to get it there!

If you modify the EV function to place a higher value on other board spots, something like:

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

That function gets it as far as:

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

16k:

Eureka! With a 5-step lookahead instead of a 4, and the following weights:

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

It almost almost gets 32k, ending on:

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

The sequence is here.

32k:

Yes ladies and gentlemen, we have hit the 32k mark. The EV function, instead of multiplying squares by a constant, raises each square to the following powers and adds them. x means the square isn't involved:

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

It still sums all the values once and adds 256 for each empty square. Lookahead was 4 all the way up to 32k, and then it bumped up to 5, but it doesn't really seem to do much. End board:

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

Pastebin of the 24,625-move sequence.