2048 AI - Best Heuristics
The game 2048 was developed by Gabriele Cirulli. It’s based on 1024 by Veewo Studio and conceptually similar to Threes by Asher Vollmer. Read his story of the making & rip-offs in game development here: http://asherv.com/threes/threemails/
For the “Artificial Intelligence 1” lab, we built two AI agents — one simple, one sophisticated — to play 2048 in the browser. Our best agent scored 146,348.00.
Heuristic AI
We started with a rule-based agent that could already beat a random player. Here’s what we noticed helps achieve a higher score:
- When many tiles are on the board, the chance that you can’t move any more is greatly increased; thus, one goal is to have the board as empty as possible.
- If tiles of big value are at the corner of the board, they don’t block the merging of the “smaller” tiles.
- A move bringing two tiles with the same value next to each other is preferable over a move that won’t give you this advantage.
We baked all of these observations into our board-scoring heuristics (higher is better):
- Snake Shape: Enforce layout by multiplying weights to tiles
def heuristic_tile_layout(board):
rewardBoard = numpy.array([
[2**15, 2**14, 2**13, 2**12],
[2**8, 2**9, 2**10, 2**11],
[2**7, 2**6, 2**5, 2**4],
[2**0, 2**1, 2**2, 2**3]
])
return numpy.multiply(rewardBoard,board).sum()- Remove Tiles: Reward for removing tiles
- Same Move Penalty: Penalty for not changing board
| Type | Configuration | Score |
|---|---|---|
| Heuristic | Snake Shape + Same Move Penalty + Remove Tiles | 10,136.00 |
| Heuristic | Snake Shape + Same Move Penalty + Remove Tiles | 6,588.00 |
| Heuristic | Snake Shape + Same Move Penalty + Remove Tiles | 4,684.00 |
| Heuristic | Snake Shape + Same Move Penalty + Remove Tiles | 4,316.00 |
| Heuristic | Snake Shape + Same Move Penalty + Remove Tiles | 3,696.00 |
| Heuristic | Snake Shape + Same Move Penalty + Remove Tiles | 3,340.00 |
| Heuristic | Snake Shape + Same Move Penalty + Remove Tiles | 3,060.00 |
| Heuristic | Snake Shape + Same Move Penalty + Remove Tiles | 1,684.00 |
| Heuristic | Snake Shape + Same Move Penalty + Remove Tiles | 1,100.00 |
| Heuristic | Snake Shape + Same Move Penalty + Remove Tiles | 832.00 |
- MAX: 10,136.00
- AVG: 3,943.60
With these heuristics, we were able to achieve an average of 3’943 points and a high score of 10’136 points.
Search AI
Using the expectimax algorithm with our snake shape heuristic, we reached the 2048 tile 100% of the time.
def score_toplevel_move(move, board, depth):
"""
Entry Point to score the first move.
"""
global UP, DOWN, LEFT, RIGHT
global move_args
countZeros = 0
nodeScore = 0
childrenResults = []
newboard = execute_move(move, board)
# Stop recursion
if board_equals(board, newboard):
return 0
if depth == 0:
return ha.evaluate_board(board, newboard)
newboards = get_all_possible_boards(newboard)
for boardWithNewTile in newboards:
result = [score_toplevel_move(i, board, maxDepth) for i in range(len(move_args))]
bestmove = result.index(max(result))
childrenResults.append(best)
countChildren = len(childrenResults) - countZeros
if countChildren == 0:
return 0
for node in childrenResults:
nodeScore += node / countChildren
return nodeScore
Other things we did:
- Calculates score + probability for possible boards per move
- Only placing 2s as opponent to speed up computation
- MAX_DEPTH:
if countFreeTiles <= 4 then 3, else 2 - Tried Threading, but no performance gain
| Type | Configuration | Score |
|---|---|---|
| Search | Snake Shape | 146,348.00 |
| Search | Snake Shape | 128,984.00 |
| Search | Snake Shape | 124,112.00 |
| Search | Snake Shape | 79,812.00 |
| Search | Snake Shape | 76,732.00 |
| Search | Snake Shape | 72,036.00 |
| Search | Snake Shape | 67,124.00 |
| Search | Snake Shape | 58,720.00 |
| Search | Snake Shape | 52,272.00 |
| Search | Snake Shape | 50,572.00 |
- MAX: 146,348.00
- AVG: 85,671.20
By looking ahead at future possibilities and scoring them, the search agent dramatically outperformed the heuristic-only approach.
This was one of the most fun labs we worked on. The hardest part? Finding a good method to score a given board.