Let’s talk about Minimax.
Before I get into what it is, I want to mention its usefulness in case anyone doesn’t know. Ok, I’m sure you know but it’s still my process.
Why!
During my first iteration of an Unbeatable Tic Tac Toe, I used many if statements for the logic behind the decision making of the computer. I did create a few helper functions to finish the game, and to block the opposition player if that was necessary. Outside of those, I still wrote hundreds of lines of code filled with if statements which are not ideal.
Luckily Tic Tac Toe doesn’t take much time to run, so I constantly tested it to make sure that it functioned the way I wanted it to. I had run it through every game iteration I could conceive, until it worked perfectly. As far as I know there are no holes in the logic, but there could be.
If there are 3 options per slot, and 9 slots that means there are 3^9 possibilities or 19, 683. I am not sure if I covered every single one of these. To be fair, most of those possibilities are not possible because at max you can only have a 5-4 count either way for X or O, where 19,683 contains the possibilities of 6 or more Xs/Os. Regardless, it is a tough task.
Minimax!
Forget those crazy if statements, and possible holes in your logic, let’s solve that by adding a decision making algorithm. The goal of Minimax is to determine the best move for a player by considering all possible moves and their potential outcomes. This is great because now I don’t have to, the computer can do it.
Here is the pseudo code below.
Minimax(s):
if Terminal(s):
return Value(s)
if Player(s) == MAX:
value = -infinity
for a in actions(s):
value = Max(value, Minimax(Result(s, a)))
return value
if Player(s) == MIN:
value = infinity
for a in Actions(s):
value = Min(value, Minimax(Results(s,a)))
return value
Here are the ideas that follow this code:
Ideas that follow this code:
Terminal state means game over.
The terminal gets the value of the terminal state, 12 for win, 0 for tie, -12 loss.
(12 is a personal preference because it can be easily divided)
Determine who’s turn it is.
Player takes a game state, and tells if it’s Max or Min’s turn.
In a particular game state, you need to know what actions are available to the player.
Action takes a game state, and gives all possible actions that can be taken.
Result, takes a state and action and tells what the new state of the game will be after taking that action.
Minimax will take gamestate S.
Simple Explanation
Minimax will run through every action possible for this game state until the game ends. When the game ends it will give a value for the end result, if it wins it gets a +12, lose -12, and Tie a 0.
It will take that value and compare it with the previous highest score of the games it has played.
It wants to get a 12, so it will store the initial move that led to that decision. If for some reason, the game ends in a -12 or 0, it will try to avoid those moves unless 0 is the best outcome.
After it has run through every possible iteration, it will provide the move which leads to the most favorable outcome.
It’s brilliant! Until next time,
Merl