A few weeks ago, I wrote a Python implementation of 2048. Since then, I've been working on a simple AI to play the game for me. The code uses expectimax search to evaluate each move, and chooses the move that maximizes the search as the next move to execute.
Similar to what others have suggested, the evaluation function examines monotonicity along a "snake path"; I also penalize boards that don't keep the largest tile at the snake path's terminal.
The AI can get to 2048 (and even 4096 occasionally), but not further. One of the things I've had difficulty with is tuning the evaluation function, and looking at what to try next. I have taken a look at awarding bonuses for zero tiles (for example,
z is the number of zeros and
s is the total sum of the tiles on the board; zeros become more valuable deeper into the game) but haven't had much luck improving things. Rather, I feel like I'm guessing at what to do next to improve the heuristic (or I'll look at a board that defied my human strategy, and try and write something to mirror this), and am curious what someone else might suggest.
The code for the game and the AI can be found here. You can run
aiplay with a
Below is the relevant AI code:
from game import * import math def aimove(b): """ Returns a list of possible moves ("left", "right", "up", "down") and each corresponding fitness """ def fitness(b): """ Returns the heuristic value of b Snake refers to the "snake line pattern" (http://tinyurl.com/l9bstk6) Here we only evaluate one direction; we award more points if high valued tiles occur along this path. We penalize the board for not having the highest valued tile in the lower left corner """ if Game.over(b): return -float("inf") snake =  for i, col in enumerate(zip(*b)): snake.extend(reversed(col) if i % 2 == 0 else col) m = max(snake) return sum(x/10**n for n, x in enumerate(snake)) - \ math.pow((b != m)*abs(b - m), 2) def search(b, d, move=False): """ Performs expectimax search on a given configuration to specified depth (d). Algorithm details: - if the AI needs to move, make each child move, recurse, return the maximum fitness value - if it is not the AI's turn, form all possible child spawns, and return their weighted average as that node's evaluation """ if d == 0 or (move and Game.over(b)): return fitness(b) alpha = fitness(b) if move: for _, child in Game.actions(b): return max(alpha, search(child, d-1)) else: alpha = 0 zeros = [(i,j) for i,j in itertools.product(range(4), range(4)) if b[i][j] == 0] for i, j in zeros: c1 = [[x for x in row] for row in b] c2 = [[x for x in row] for row in b] c1[i][j] = 2 c2[i][j] = 4 alpha += .9*search(c1, d-1, True)/len(zeros) + \ .1*search(c2, d-1, True)/len(zeros) return alpha return [(action, search(child, 5)) for action ,child in Game.actions(b)] def aiplay(game): """ Runs a game instance playing the move determined by aimove. """ b = game.b while True: print(Game.string(b) + "\n") action = max(aimove(b), key = lambda x: x) if action == "left" : b = Game.left(b) if action == "right": b = Game.right(b) if action == "up" : b = Game.up(b) if action == "down" : b = Game.down(b) b = Game.spawn(b, 1) if Game.over(b): m = max(x for row in b for x in row) print("game over...best was %s" %m) print(Game.string(b)) break