Purpose

The purpose of this assignment is for you to:

• Increase your proficiency in C programming, your dexterity with dynamic memory allocation and

your understanding of data structures, through programming a search algorithm over Graphs.

• Gain experience with applications of graphs and graph algorithms to solving games, one form of

artificial intelligence.

Assignment description

In this programming assignment you’ll be expected to build a solver for the 2048 game. The game has

been described by the Wall Street Journal as “almost like Candy Crush for math geeks”. You can play the

game compiling the code given to you using the keyboard, or using this web implementation

http://2048game.com/.

The 2048 game

2048 is played on a 4×4 grid, with numbered tiles that slide smoothly when a player moves them using

the four arrow keys. Every turn, a new tile will randomly appear in an empty spot on the board with a

value of either 2 or 4. Tiles slide as far as possible in the chosen direction until they are stopped by either

another tile or the edge of the grid. If two tiles of the same number collide while moving, they will merge

into a tile with the total value of the two tiles that collided. The resulting tile cannot merge with another

tile again in the same move.

Figure 1: A possible configurations of the game 4×4 grid

A scoreboard on the upper-right keeps track of the user’s score. The user’s score starts at zero, and is

incremented whenever two tiles combine, by the value of the new tile.

The game is won when a tile with a value of 2048 appears on the board, hence the name of the game.

After reaching the 2048 tile, players can continue to play (beyond the 2048 tile) to reach higher

scores. In this assignment, your solver should continue playing after reaching tile 2048. When the player

has no legal moves (there are no empty spaces and no adjacent tiles with the same value), the game ends.

GraphSearch(Graph,start,maxDepth)

1 node ← start2 explored ← empty Array

3 frontier ← priority Queue Containing node Only

4 while frontier 6= empty

5 do

6 node ← frontier.pop()

7 explored.add(node)

8 if node.depth < maxDepth

9 then

10 for each action

11 do

12 newNode ← applyAction(node)

13 if newNode.board 6= node.board

14 then

15 frontier.add(n)

16 propagateBackScoreToFirstAction(n)

17

18 else

19 delete newNode

20

21 freeMemory(explored)

22 bestAction ← select best action breaking ties randomly

23 return bestAction

Figure 2: Online Graph variant of Dijkstra

The Algorithm

Each possible configuration of the 2048 4×4 grid is called a state. The 2048 Graph G = hV,Ei is implicitly

defined. The vertex set V is defined as all the possible 4×4 configurations (states), and the edges E

connecting two vertexes are defined by the legal movements (right, left, up, down).

Your task is to find the path leading to the higest score, i.e. leading to the most rewarding vertex (state).

A path is a sequence of movements. You are going to use a variant of Dijkstra to explore the most

rewarding path first, up to a maximum depth D.

Every time the game asks you for a movement (action), you should explore all possible paths up to depth

D. Once you finished generating all the paths, you should return the first action only of the path leading

to the highest score vertex. This action will be then executed by the game engine.

You might have multiple paths with the same maximum score. If more than one action (left,right,up or

down) begins paths with the same maximum score, you’ll have to break ties randomly.

Make sure you manage the memory well. Everytime you finish running the algorithm, you have to free

all the nodes from the memory, otherwise you are going to run out of memory fairly fast.

When you applyAction you have to create a new node, that points to the parent, updates the board with

the action chosen, updates the priority of the node with the new score, and updates any other auxiliary

data in the node.You are going to need some auxiliary data structures to update the scores of the first 4 applicable actions.

The function propagateBackScoreToFirstAction takes the score of the newly generated node, and

propagates back the score to the first action of the path.

This propagation can be either Maximeze or Average :

• If you Maximize, you have to make sure that the first action is updated to reflect the maximum

score of any of its children up to depth D.

• If you Average, you have to make sure that the first action is updated to reflect the average score

taking into account all its children up to depth D.

Deliverables, evaluation and delivery rules

Deliverable 1 – Solver source code

You are expected to hand in the source code for your solver, written in C. Obviously, your source code is

expected to compile and execute flawlessly using the following makefile command: make generating an

executable called 2048. Remember to compile using the optimization flag gcc -O3 for doing your

experiments, it will run twice faster than compiling with the debugging flag gcc -g. For the submission,

please submit your makefile with gcc -g option, as our scripts need this flag for testing.

Your implementation should achive scores higher than 5000 points.

Base Code

You are given a base code. You can compile the code and play with the keyboard. The default solver

chooses an action randomly. You are going to have to program your solver in the file ai.c. Look at the file

2048.c to know which function is called to select an action to execute.

You are given the structure of a node, and also a priority queue implementation. Look into the utils.* files

to know about the functions you can call to apply actions.

You are free to change any file.

Input

You can play the game with the keyboard by executing ./2048

In order to execute your solver use the following command:

./2048 ai <max/avg <depth

Where <max/avg is either max or avg, to select the 2 options for propagationg scores, and <depth is

an integer number indicating the depth of your search.

for example:

./2048 ai avg 6

Will run average updates up to depth 6.

If you append the option “slow” at the end, it will slow the ai so you can see it playing

./2048 ai avg 6 slow

OutputYour solver will print into an output.txt file the following information:

1. Max Depth

2. Number of generated nodes.

3. Number of expanded nodes.

4. Number of expanded nodes per second.

5. Total Search Time, in seconds.

6. Maximum value in the board.

7. Score

For example, the output of your solver ./2048 ai avg 6 could be:

MaxDepth = 8

Generated = 499,911

Expanded = 253,079

Time = 7.05 seconds

Expanded/Second = 35,906,612 maxtile

= 2048 Score=14,000

These numbers are made up. We don’t expect you to expand 35 million nodes per second. A node is

expanded if it was popped out from the priority queue, and a node is generated if it was created using

the applyAction function.

Deliverable 2 – Experimentation

Besides handing in the solver source code, you’re required to provide a table with the mean score and

deviation, mean max tile and deviation, and total execution time for each type of propagation (max/avg)

you implement and each max depth from 0,..,6.

In order to test your solver, you have to average over multiple runs because 2048 has a random

component: tiles can appear in different locations after each move. A sample of 10 runs is enough.

For each propagation type, plot a figure where the x axis is the depth, and y is the mean score.

Explain your results using your figures and tables. Which max depth works best? Is it better to propagate

max or avg?

Sale!