This is the first part in a series where you will learn the core principles of Artificial Intelligence (AI) programming in Java. We will be using the minimax algorithm to create our very own web-based, online, Tic Toe Game.
I have solid foundations in Computer Information Science & Engineering with about 6 Years of progressive CSE/ISE education. In my later life, I attended a specialized program on Artificial Intelligence (AI) and Intelligent Agents at the Indian Institute of Science, Bangalore. As a Computer Science student for life, studying AI programming has helped me understand – and appreciate – software development at a higher level.
Even though I was introduced late to the concepts of the minimax algorithm, I was amazed by the many potential applications of this algorithm. To gain further insight into its working and better grasp the core concepts of AI development, I decided to create a web-based version of the Tic-Tac-Toe game using the minimax algorithm.
I hope that you enjoy the game and learning how to create Tic-Tac-Toe using JAVA, AI concepts, and minimax. If you managed to beat the ‘T3oW AI Engine’ (in this case, the “engine” is simply the server/computer whom you are playing against), let us know in the comments section.
You can try an online version of the Tic-Tac-Toe game here: https://rebrand.ly/skp-ai-t3ow
What Is The Minimax Algorithm in Java?
The minimax algorithm is an algorithm – recursive in nature – that is used in games. It allows the AI player to choose the next move in a game and, typically, chooses the optimal move based on its opponent’s moves and the moves it would take to win a game in general. It can also be used in other decision-making and game theory situations.
Another way to consider the core concept behind the minimax algorithm is to consider that every step we take should be aimed at minimizing the maximum loss that can occur. This is different than ‘Maximin’ , which works to maximize the minimum profit one can have. To demonstrate this, I built a simple web user interface (UI) for the Online Game. You can find the Java code for that here:
Step By Step Guide to the Minimax Algorithm
Minimax uses backtracking for dynamic decision making where the ‘most optimal move’ is decided at each iteration of the algorithm. As a first step, we will compute the game tree that is possible from the ‘remaining moves.’ In the image below, the ‘cross’ – or ‘X’ – represents the Maximizing Player (the actual AI or robotic/computer player). The ‘circles’ represent the moves of the opponent that are of the ‘Minimizing Player.’
Representation of a Computed Game Tree using Minimax Algorithm
We can place the first ‘X’ randomly – as per a few online research papers on best opening moves in Tic Tac Toe, an ‘X’ in any of the 0,2,6,8 corner spots is the best first move.
Representation of a 3×3 Tic-Tac-Toe Game Board
In this game, we can look ahead up to the nth level, but due to constraints in computational resources, we usually reduce it to levels between 1 to 4. This can also be used to decide the difficulty level of the game, as the more moves ahead we predict, the more difficult the game becomes.
Using an evaluation function, the minimax algorithm evaluates each node obtaining the moves/values shown above. Any moves in which the maximizing player wins are assigned with positive infinity, in this case, a +1.
Moves that result in a win for the minimizing player are awarded negative infinity – or -1. Otherwise, a value of zero (0) is assigned at the leaf levels, which denotes a draw or tie.
At every circle level, the algorithm will choose, for each node, the smallest of the child node values and assign it to that same node. At every cross-level, the algorithm will choose, for each node, the largest of the child node values. Once again, the values are assigned to each parent node. The algorithm continues evaluating the maximum and minimum values of the child nodes alternately until it reaches the root node, where it chooses the move with the largest value. This is the move that the player should make in order to minimize the maximum possible loss.