SKP's AI-ML-DM Series #01: Tic-Tac-Toe Using the Minimax Algorithm
SKP's AI-ML-DM Series is Dedicated to Algorithms, Articles, Theory, Vision, Applications, and Tutorials on Artificial Intelligence, Data Mining, and Machine Learning. In this Article, We Learn to Build a Core Java-Based Tic-Tac-Toe Algorithm using Minimax Algorithm.
Join the DZone community and get the full member experience.Join For Free
I created a Version of the Classical Game using the Minimax Algorithm (T3oW, Tic-Tac-Toe on the Web). Enjoy the Game and Let Me/Us Know in the Comments, If you were able to beat the 'T3oW AI Engine' (Well, Simply the Server/Computer!)
Minimax Algorithm works towards minimizing the maximum loss that can occur (as opposed to the 'Maximin' which works to maximize the minimum profit that one can have). I have also built a user interface (Work in Progress) for the above.
Core Java Code (Core Logic): https://rebrand.ly/skp-ai-t3ow-core-logic
Java Web Project (. Eclipse.): https://rebrand.ly/skp-ai-t3ow-war-eclipse-project
This is how the Minimax Algorithm works, usually:
1. Compute the game tree that is possible from the remaining moves where the cross represents the maximizing player (running the algorithm — like the computer player) and circles represent the moves of the opponent that are of the minimizing player.
2. In this game, we usually do a look-ahead of the nth level, but due to computational resources, we may want to reduce it to levels between 1 to 4.
3. The algorithm evaluates each node using an evaluation function, obtaining the values shown. The moves where the maximizing player wins are assigned with positive infinity (+1 here), while the moves that lead to a win of the minimizing player are assigned with negative infinity (-1). Otherwise, a value of zero (0) is assigned at the leaf levels, which denotes a draw.
4. 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.
[Partial credits: https://en.wikipedia.org/wiki/minimax]
Published at DZone with permission of Sumith Puri, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.