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/
In the second lab for the module "Artificial Intelligence 1" we developed a simple as well as a sophisticated AI agent to remote control the 2048 game running in the browser.
By using simple rules/heuristics we created a simple agent that could beat a randomly playing agent. These are the things we noticed which help us to get a higher score in the game.
- 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 have included all these aspects in our heuristics to score the board. (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] ]) value = 0 for row in range(0, 4): for column in range(0, 4): value += (board[row][column] * rewardBoard[row][column]) return value
- Remove Tiles: Reward for removing tiles
def heuristic_removed_tiles(board, newboard): return (count_tiles(board) - count_tiles(newboard))
- Same Move Penalty: Penalty for not changing board
|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.
By creating an agent based on the expectimax algorithm we reached the 2048 tile 100% of the time. With our expectimax implementation, we reused our snake shape heuristic.
def score_toplevel_move(move, board, depth): """ Entry Point to score the first move. """ global UP, DOWN, LEFT, RIGHT global move_args 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) countZeros = 0 childrenResults =  for boardWithNewTile in newboards: # Best Move best = 0 for i in range(len(move_args)): result = score_toplevel_move(i, boardWithNewTile, depth - 1) if result > best: best = result childrenResults.append(best) if best == 0: countZeros += 1 nodeScore = 0 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
if countFreeTiles <= 4 then 3, else 2
- Tried Threading, but no performance gain
- MAX: 146,348.00
- AVG: 85,671.20
By calculating the future possibilities and the scores, we were able to achieve excellent results.
We had a lot of fun working on this lab. By far the most difficult part was finding a good method to calculate the score of a given board.