request description
In this programming request 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.
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 request, 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.
The Algorithm
Each possible configuration of the 2048 4x4 grid is called a state. The 2048 Graph G = (V, E) 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>
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
Output
Your solver will print into an output.txt file the following information:
Max Depth
Number of generated nodes.
Number of expanded nodes.
Number of expanded nodes per second.
Total Search Time, in seconds.
Maximum value in the board.
Score
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?