Assignment 2 Solving the 2048 Game: online

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 4x4 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 4x4 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 4x4 grid is called a state. The 2048 Graph G = hV,Ei is implicitly
defined. The vertex set V is defined as all the possible 4x4 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?