🎮 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/

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.

Heuristic AI

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)

1. 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

1. Remove Tiles: Reward for removing tiles

def heuristic_removed_tiles(board, newboard):
	return (count_tiles(board) - count_tiles(newboard))

1. Same Move Penalty: Penalty for not changing board

• 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

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
• MAX_DEPTH: 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.