I programmed a tic tac toe game with Minimax Algorithm, but how does it work?
Intro to Minimax Algorithm, programmed in Python
Mentor: Nicolas Graves
In this article, you learn about the Minimax Algorithm and how this A.I. agent makes your Tic-Tac-Toe game unbeatable. In the following, I will go over concepts of Minimax and the python code for Minimax implementation. (For the entire code, go to the GitHub link at the bottom.)
Outline:
Tic-Tac-Toe:
Tic-Tac-Toe is a game in which two players seek alternate turns to complete a row, a column, or a diagonal with either three O’s or three X’s drawn in the spaces of a grid of nine squares.
Consider the following Tic-Tac-Toe scenario:
Minimax Algorithm:
You will be playing the Tic-Tac-Toe game against the computer with Minimax Algorithm which it never loses if correctly implemented. Now, what's Minimax Algorithm exactly and why should you use it? Minimax is a decision rule used in artificial intelligence, game theory, decision theory, etc… Minimax is useful because it leverages the capability of computers evaluating an exponentially growing series of possible scenarios. Looks into the future omi-presence. As for games, Minimax is often used for adversarial games. There’re two utility values called the min and max value that help the A.I. agent to decide its next optimal move. For this case, the Agent prioritizes moves with a max value of 10 and then opts for a min value of -10. (Agent wants to win more than preventing its opponent to win) If there aren’t any moves with a min or max value greater than or less than 10, it selects the move with the highest absolute value of min plus max value. Again, Minimax assumes that its opponent plays optimally.
— min value
This is the value where the A.I. agent seeks to minimize the possible loss for a worst-case scenario. For every horizontal, vertical, diagonal lane on the board position, the min value -1 per lane if the 3 positions have none of your moves. Then, for every additional opponent move on a lane, you -1 (Only if you didn’t make a move on that lane). However, if there are 2 opponent moves, your min value becomes -10(Your enemy will win if you don’t block that position!).
Say you’re the player( X ), consider the following board scenario:
For board position 1, there was no X on its row(horizontal lane) and column(vertical lane). This means by placing an X there, you eliminated 2 possible lanes for O to win. Additionally, on that row(horizontal lane), there’s an O so you -1 in addition to -2. We didn’t minus points from the diagonal lane because it contained an X even though there was an O. For board position 6, the min value was -10 because its column(vertical lane) had 2 Os.
— max value
This is the value where the A.I. seeks to maximize the possible gain for a best-case scenario. For every horizontal, vertical, diagonal lane on the board position, you +1 per lane if the 3 positions have none of your opponent’s moves. Then, for every additional move you made on the lane, you +1 again(Only if your enemy didn’t make any move on that lane). However, if there are 2 of your moves, your max value becomes +10(You win by making a move there!).
Say you’re the player( X ), consider the following board scenario:
For board position 1, you add 2 for no opponent( O ) moves on its column(vertical lane) and diagonal lane. Additionally, you made a move( X ) on the diagonal lane so you add 1 to the max value which results in 3. For board position 8, the max value is 10 because you made 2( X ) moves on its column(vertical lane). By placing your move on position 8, you win.
Python code for Minimax:
Let’s look at the Code for generating min and max values!
- Line 1–7
Imported the library copy. Defined a class called Cell to transform each position on the board passed on line 9 into separate objects storing 4 items: position, the 2D index of that position, max value, and min value for easier access.
2. Line 9–19
Defined a function called generate_cells that takes in an input of the Tictactoe board(should be 2 dimensional) and returns a utility board for each position on the board. The utility board is a 2D list, each position is a list containing 3 items: its position, max value, and min value. The function generates max and min values by calling the max_val function(line 21) and min_val function(line 32) on line 15–16.
3. line 21–30
Defined a function called max_val which takes in a board position and its 2D index and returns a max value. On line 24, the check_horizontal function generates max values by checking the position’s horizontal lane.
On line 25, the check_vertical function generates max values by checking the position’s vertical lane.
On line 27, the left_diagonal function generates max values by checking the position’s top left to bottom right diagonal lane.
On line 28, the right_diagonal function generates max values by checking the position’s top right to bottom left diagonal lane.
4. Line 32–40
Defined a function called min_val which takes in a board position and its 2D index and returns a min value. On line 35, the check_horizontal function generates min values by checking the position’s horizontal lane. On line 36, the check_vertical function generates min values by checking the position’s vertical lane. On line 37, the left_diagonal function generates min values by checking the position’s top left to bottom right diagonal lane. On line 38, the right_diagonal function generates min values by checking the position’s top right to bottom left diagonal lane.
What’s Next:
By now you should be able to understand the general concepts behind Minimax. My program was relatively simple and it could be further optimized by implementing more advanced concepts such as utility tree and alpha-beta pruning.
utility tree: Basically a decision tree that contains possible board states given a board, evaluated with min and max values. Consider the following example:
alpha-beta pruning: A search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree to improve the time efficiency of the program.
Note: The Minimax Algorithm is suitable for Tic-Tac-Toe where the A.I. agent made this game unbeatable. However, tic-tac-toe doesn’t fully utilize the potential of Minimax where the chess game might be a better representation. Chess fully manipulates the strength of Minimax: perfectly manipulates the strength of the computer, has perfect recall, has perfect memory, no scenario is uncalculated, and generates a lot of possible scenarios in advance compared to a human. Compared to Chess… Tictactoe has fewer possible scenarios the computer could come up with given its 3 by 3 board.
The python codes are on GitHub: https://github.com/729557989/MiniMax-Algorithm-with-tictactoe-optimized
Questions? Comments? Your questions or comments are very important for helping both of us learn! Feel free to leave your comments or feedback in the comment sections. Thank you for reading this!
