代写一个带AI功能的2048游戏，要求能自动玩，并且平均能得到5000分以上的成绩。作业中给出了2048的高分AI参考算法。
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.
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.
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
For example, the output of your solver./2048 ai avg 6could be:
MaxDepth = 8
Generated = 499,911
Expanded = 253,079
Time = 7.05 seconds
Expanded/Second = 35,906,612
max tile = 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?
