The first player is the person who plays the game. In order to use the above algorithms we must first identify the two players. Β := min(β, alphabeta(child, depth - 1, α, β, TRUE))Īlphabeta(origin, depth, -∞, +∞, TRUE) How AI is used to solve the Game 2048? Here is a nice video presentation of the minimax algorithm:įunction alphabeta(node, depth, α, β, maximizingPlayer) In order to win each player must select the move that minimizes the opponent’s maximum payoff. The interesting idea of this algorithm is that each level represents the turn of one of the two players. Once those leaf states are reached, their values are used to estimate the ones of the intermediate nodes. The Minimax algorithm searches through the space of possible game states creating a tree which is expanded until it reaches a particular predefined depth. In each state of the game we associate a value. The Minimax is a recursive algorithm which can be used for solving two-player zero-sum games. To solve the problem I tried two different approaches, using Minimax algorithm and using Alpha-beta pruning. The most notable is the one developed by Matt Overlan. Several approaches have been published to solve automatically this game. Artificial Intelligence Techniques: Minimax vs Alpha-beta pruning The AIsolver is the primary class of the Artificial Intelligence module which is responsible for evaluating the next best move given a particular Board. The ConsoleGame is the main class which allows us to play the game and test the accuracy of the AI Solver. The ActionStatus and the Direction are 2 essential enums which store the outcome of a move and its direction accordingly. The board class contains the main code of the game, which is responsible for moving the pieces, calculating the score, validating if the game is terminated etc. Below we provide a high level description of the architecture of the implementation: 1. Maurits van der Schee has recently written an article about it which I believe is worth checking out.Īll the classes are documented with Javadoc comments. A nice simplification of the algorithm can be performed if we fix the direction towards which we can combine the pieces and rotate the board accordingly to perform the move. In the original implementation of the game, the move-merge algorithm is a bit complicated because it takes into account all the directions. The game ends when the player manages to create a cell with value 2048 (win) or when there are no other moves to make (lose). At the end of every move a random value is added in the board in one of the empty cells and its value is either 2 with 0.9 probability or 4 with 0.1 probability. If that previous cell has the same value, the two cells are merged into one cell with double value. When you perform a move all the values of the grid move towards that direction and they stop either when they reach the borders of the grid or when they reach another cell with non-zero value.
At every point during the game you are able to move the values towards 4 directions Up, Down, Right or Left. The main idea of the game is that you have a 4×4 grid with Integer values, all of which are powers of 2. The original game is written in JavaScript, so I had to rewrite it in JAVA from scratch. The code is open-sourced under GPL v3 license and you can download it from Github. In this article I will briefly discuss my approach for building the Artificial Intelligence Solver of Game 2048, I will describe the heuristics that I used and I will provide the complete code which is written in JAVA. So the natural thing to do is to try to develop an AI solver in JAVA to beat the 2048 game.
Personally even though I spent a fair amount of time playing the game, I was never able to reach 2048. As expected the difficulty of the game increases as more cells are filled with high values. It’s a simple but highly addictive board game which requires you to combine the numbers of the cells in order to reach the number 2048.
By now most of you have heard/played the 2048 game by Gabriele Cirulli.