This project was created as a course deliverable in ITU Intelligent systems course. The main goal of the project was to create functioning AI with Minimax algorithm and alpha beta pruning.
What is the bloody Minimax algorithm?
Minimax algorithm is a recursive or backtracking algorithm which is used in decision-making and game theory. Thanks to this algorithm we managed to develop an algorithm that beat chess world champion in 1997. Keep in mind that chess has 10^120 moves (yes, that’s 10 with 120 zero’s). There is no way to keep track of all moves and possibilities. This is where MinMax algorithm (together with alpha beta pruning) comes in play. The idea behind Minimax algorithm is that it provides an optimal move for the player assuming that opponent is also playing optimally.
The simple example is displayed in the picture above. Min will choose [1 5 -50] as it’s optimal values. Max then takes Min’s decision and maximizes it’s value taking 5 as a final output. Alpha beta pruning brings additional optimization changes to the table. Skipping all the math, the main idea of the method is to reduce calculation space which significantly increases performance.
In the image below we can see the alpha beta pruning method in action. Imagine that it’s Min’s turn to traverse the tree. Min already knows that it has [1 5] selected and that after him - it’s Max turn. Going down the tree Min finds -2 at the leaf node. This means that the Min, picking optimally will select -2 or less from all the leaf nodes left. We also know that Max has already a bigger number to pick (5) and whatever Min will pick on the right side doesn’t acutally matter. At this point, the whole right side can be thrown away, thus reducing the calculation space.
How can I play the game?
We decided to use Java language for this project. Pull the code from the repository, run ShowGame.java file with parameters:
<player> <player> width height
<player>possible options - human, GameLogic.width,height- integer values. [6 6] is recommended board size.
To make move press one of the top arrows, the coin will be inserted. In order to trigger AI move press anywhere on the game board.
Project outcome
In the final program computer’s response time on a board with 7 columns and 6 rows on average was not longer than 10 seconds although few moves took up to 30 seconds. The computer made reasonable moves an managed to beat every puny human it came across. You are very welcome to download and try the game ourself!