This project is a recreation of the game 2048 with additional functionality to be solved using AI search algorithms. The highlight of this project is the Expectiminimax algorithm which successfully solves 2048 and consistently reaches tiles with values of 4096 and even 8192!
Table of Contents:
- About the Application
- How Is AI Used to Solve 2048
- Analytics and Data For 2048
- Preparing and Using the Application
- Resources
Best Game:
2048 is a game where the player attempts to slide tiles together in order to create a tile with a value of 2048. You can play the official 2048 game at https://play2048.co/.
The game starts with a 4x4 board. A random 2 or 4 tile will spawn randomly on the board, twice. The chance of a 2 tile spawning is 90% while the chance for a 4 tile is 10%. The player then has the option to shift all tiles on the board in one of the 4 cardinal directions. If two tiles of the same value are next to each other in the direction of a shift, they will combine together into a tile twice either of the original values. This new tile's value will then be added to the score. If the tiles or their locations on the board change, a new 2 or 4 tiles will spawn in based on the prior chances. This process of shifting and spawning repeats until the board can no longer be altered.
The goal of the game is to get the 2048 tile, but the game can and will continue beyond that point. The player can obtain tiles with values of 4096, 8192, 16384, 3276, 65536, and 131072 (the maximum theoretical tile).
Before playing 2048, make sure you have all of the requirements met and have started the application.
Once the game is running you will see two markers for your "Best Score" and "Current Score". On the right side of the application, you will see 5 "Game Mode" buttons and 4 "Control" buttons. The functions of each as as follows:
- Each of the "Game Mode" buttons sets the player into each mode, resets the current score to 0, and resets the board.
- Manual Play [Default Mode] - This mode emulates the traditional 2048 game. The player can shift the tiles using either WASD or their arrow keys.
- Random Play - This mode shifts the tiles in a random direction based on python's built in randomizer.
- Expectiminimax (EMM) - This shifts the tiles in the best direction based on the decision of the Expectiminimax algorithm.
- Monte Carlo Tree Search (MCTS) - This mode shifts the tiles in the best direction based on the decision of the Monte Carlo Tree Search algorithm.
- MCTS x EMM (MCTSxEMM)- This shifts the tiles in the best direction based on a combination of both the Expectiminimax and Monte Carlo Tree Search algorithms.
- Each of the "Control" buttons alters application.
- Unlimit/Limit Speed - (Unlimit Speed) Drops the built in limiter holding back the speed of the program. (Limit Speed) slows down the program so it does not blitz by.
- Pause/Go - (Pause) stops the board from changing no matter what mode. (Go) continues the game and allows board changes.
- Reset - This restarts the board so that it is blank asides from the two random initial tile, and it resets the current score to 0.
- Quit - This stops the application entirely.
In order to solve 2048, AI search algorithms were implemented. Each of these algorithms, given the current board, return the next best move as determined by its search/test. Every move in automatically played as its decided by the algorithm. While Monte Carlo Tree Search is still a work in progress, Expectiminimax has been shown to be very effective as it achieves 2048 most of the time, 4096 very often, and 8192 relativity often. All algorithms below use the same heuristic, Snake Heuristic 3, to score a board on its current state.
Expectiminimax is a variation of Minimax that incorporates randomness, which is essential for games like 2048 due to the random spawning of tiles. In standard Minimax, two agents are involved: a Max player and a Min player. In EMM, the Max player (the Shifter) remains, but the Min player is replaced by the Avg Player (the Game), which models randomness by averaging over all possible outcomes.
EMM begins at the player’s turn with a specified search depth. The algorithm simulates shifting the board in all four directions and recursively evaluates the resulting states. The best move chosen is the direction with the highest score. When the search depth reaches zero, the board is evaluated using the heuristic. If it is the Shifter's turn, EMM simulates all four possible shifts, recursively evaluates each resulting board with one less depth and the turn set to the Game, and returns the maximum score among them. If it is the Game’s turn, EMM simulates the random spawning of a tile (2 or 4) in every empty cell. Each resulting board is recursively evaluated with one less depth and the turn set to the Shifter. The average score of all these outcomes is then returned.
Set Parameters:
- Depth: 8
Monte Carlo Tree Search operates in 4 phases: Selection, Expansion, Simulation, and Backpropagation. It is also given two input parameters, the # of iteration and expansion depth. MCTS operates over the same tree, starting at the root, for each of its iterations. For each iteration, it is as follows.
- Selection - MCTS selects the next best child node based off of which one has the highest UCB1 score.
- Expansion - A new node is branched off of the selected node.
- Simulation - A # of random moves are simulated on the game board based off of the expansion depth.
- Backpropagation - The final board is evaluated using the heuristic, the score is added to the node, and then the score is propagated back up through all of its parents.
The UCB1 score is meant to show which node should be searched next based on a balance between the given node's reward, its visits, and its parent visits. The C variable is meant to adjust the formula to correct it. The
Set Parameters:
- C: 1.4
- Iterations: 1500
- Expansion Depth: 30
This algorithm functions the same as MCTS except for the moves made during the Simulation. Rather than being random, each move made is the "best move" determined by Expectiminimax.
Set Parameters:
- MCTS C: 1.4
- MCTS Iterations: 50
- MCTS Expansion Depth: 30
- EMM Depth: 5
In order to generate a heuristic score for the 4x4 boards, each value in the board is multiplied by its corresponding value in the heuristic board, and then those values are summed together. The "snake heuristic" has been shown to be very effective as it facilitates merging and rewards higher pieces effectively. Through multiple test, I have found that Snake Heuristic 3 is the best on average. My lowering the value when the snake changes rows, I have decreased the rate at which smaller tiles get stuck in the corners.
Snake Heuristic 1:
| 32768 | 16384 | 8192 | 4096 |
| 256 | 512 | 1024 | 2048 |
| 128 | 64 | 32 | 16 |
| 1 | 2 | 4 | 8 |
Snake Heuristic 2:
| 1073741824 | 268435456 | 67108864 | 16777216 |
| 65536 | 262144 | 1048576 | 4194304 |
| 16384 | 4096 | 1024 | 256 |
| 1 | 4 | 16 | 64 |
Snake Heuristic 3: BEST
| 4096 | 2048 | 1024 | 512 |
| 64 | 128 | 256 | 512 |
| 64 | 32 | 16 | 8 |
| 1 | 2 | 4 | 8 |
Snake Heuristic 4:
| 16777216 | 4194304 | 1048576 | 262144 |
| 4096 | 16384 | 65536 | 262144 |
| 4096 | 1024 | 256 | 64 |
| 1 | 4 | 16 | 64 |
The analytics for different AI algorithms are below. As of now, since MCTS doesn't work, it has been omitted.
Below is the analytics for EMM. The data was collected by running EMM 100 times each for depths of 1 to 8. Overall, a higher depth leads to a better score and higher tile. Depth of 6 stands out to since it actually scores worse than Depth of 5. This could be purely randomness, or it could be because the tile spanning at that depth is being counter productive... but this is doubtful since a depth of 8 did better than a depth of 7. There are large score, tile, and time jumps between (2, 3), (4, 5), & (6, 7). The score/tile jump happens because adding a new tile only changes the board by +2 or +4 points, which is then averaged out, so overall, the heuristic is mostly unchanged. Shifting on the other hand can drastically change a board's score, so that is why going from an even to an odd depth makes such a difference. The time increase happens because the shift operations is more expensive (slower) than the tile spawning. Depth of 7 is the 1st to show a relevant time jump.
- Python 3+ (64-bit recommended)
- To check your Python version, run
python --versionorpython3 --version. - To check your Python architecture, run
python -c "import platform; print(platform.architecture())". - Downloads can be found at https://www.python.org/downloads/.
- To check your Python version, run
- PyGame
- To install PyGame into your system's Python, run
pip install pygame.
- To install PyGame into your system's Python, run
- MinGW
- If you opted for a 64-bit version of Python, you must have a 64-bit version of MinGW installed.
- Downloads can be found at https://www.mingw-w64.org/downloads/.
- If you opted for a 32-bit version of Python, you must have a 32-bit version of MinGW installed, but this has not been tested.
- Downloads can be found at https://www.winlibs.com/.
- If you opted for a 64-bit version of Python, you must have a 64-bit version of MinGW installed.
- You must be in either the top level or /code directory.
- If you are in the top directory, run
python code/ui.pyorpython3 code/ui.py. - If you are in the /code directory, run
python ui.pyorpython3 ui.py. - If you are using an IDE that handles Python, click the play button to run the ui.py file.
Below are some of the resources/links I used when developing this application.
- https://www.geeksforgeeks.org/dsa/expectimax-algorithm-in-game-theory/
- https://www.geeksforgeeks.org/artificial-intelligence/expectimax-search-algorithm-in-ai/
- https://youtu.be/0fOLkZJ-Q6I?si=IS6iU51pobOUEFQW
- https://github.com/mschrandt/2048
- https://cs229.stanford.edu/proj2016/report/NieHouAn-AIPlays2048-report.pdf
- https://www.baeldung.com/cs/2048-algorithm
- https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048
- https://github.com/nneonneo/2048-ai