AI News, Using Artificial Intelligence to solve the 2048 Game (JAVA code)
- On Thursday, October 4, 2018
- By Read More
Using Artificial Intelligence to solve the 2048 Game (JAVA code)
🙂 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.
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. If that previous cell has the same value, the two cells are merged into one cell with double value.
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.
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.
Below we provide a high level description of the architecture of the implementation: 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.
Here is a nice video presentation of the minimax algorithm: Below you can see pseudocode of the Minimax Algorithm: The Alpha-beta pruning algorithm is an expansion of minimax, which heavily decreases (prunes) the number of nodes that we must evaluate/expand.
On the other hand the computer in the original game is not specifically programmed to block the user by selecting the worst possible move for him but rather randomly inserts values on the empty cells.
despite the fact that it is only the first player who tries to maximize his/her score, the choices of the computer can block the progress and stop the user from completing the game.
The main idea is not to use the score alone to evaluate each game-state but instead construct a heuristic composite score that includes the aforementioned scores.
Additionally unlike other implementations, I don’t prune aggressively the choices of the computer using arbitrary rules but instead I take all of them into account in order to find the best possible move of the player.
The one that I found most useful is the following: The above function combines the actual score of the board, the number of empty cells/tiles and a metric called clustering score which we will discuss later.
Finally we should note that when the player reaches a terminal game state and no more moves are allowed, we don’t use the above score to estimate the value of the state.
If the game is won we assign the highest possible integer value, while if the game is lost we assign the lowest non negative value (0 or 1 with similar logic as in the previous paragraph).
In my tests, a search with depth 3 lasts less than 0.05 seconds but gives 20% chance of winning, a depth of 5 lasts about a 1 second but gives 40% chance of winning and finally a depth of 7 lasts 27-28 seconds and gives about 70-80% chance of winning.
- On Friday, January 18, 2019
How to Make an Amazing Video Game Bot Easily
In this video, we first go over the history of video game AI, then I introduce OpenAI's Universe, which lets you build a bot that can play thousands of different video ...
Programming Interviews: Find Path in NXN Maze (Backtracking problem)
This video is produced by IITian S.Saurabh. He is B.Tech from IIT and MS from USA. Given a NXN maze, find a path from top left cell to bottom right cell given ...
MS Excel 2010 Tutorial - Use a Formula to Rank Scores in Excel
Want all of our free Excel videos? Download our free iPad app at ..
Paul Andersen shows you how to calculate the ch-squared value to test your null hypothesis. He explains the importance of the critical value and defines the ...
Lesson Code: In this programming exercise you can learn to create a ..
How to use Q Learning in Video Games Easily
In this video, I go over the history of reinforcement learning then talk about how a type of reinforcement learning called Q learning works. We'll then write a 10 ...
Game Playing- Minimax Search
Artificial Intelligence by Prof. Deepak Khemani,Department of Computer Science and Engineering,IIT Madras.For more details on NPTEL visit
Unity Endless Runner Tutorial #4 - Generating Infinite Platforms
Learn how to generate platforms ahead of the player as you move forward through the world! Get the art asset's used in this episode from Kenney here: ...
CellProfiler: Classifying Cells with Machine Learning
Copyright Broad Institute, 2013. All rights reserved. CellProfiler Analyst contains a machine-learning tool for identifying complex and subtle cellular phenotypes.