Information

Step 2
Check Your Work

Step 8
The game should be working as it did before.

Planning

Step 9
The minimax algorithm is used to find the best worst-case scenario. It "minimizes" the "maximum" loss potential, hence the name "minimax".

It's useful in two player games that are turn based such as Chess, Checkers, and (of course) Tic Tac Toe.

Information

Step 10
Let's use this example binary tree:

Player 1 starts at the top node and gets to choose the left or right path.

Then Player 2 gets to choose the next left or right path.

Player 1 is trying to achieve the highest possible number and Player 2 is trying to achieve the lowest possible number.

The minimax algorithm will go through each scenario to determine what is the maximum value for Player 1 assuming Player 2 wants the minimum value.

Using the best possible outcome, Player 1 will choose the left path and Player 2 will then also choose the next left path and return the value 3. It may not be the best possible number but it is the best outcome given the 2 player turn system

Information

Step 11
Let's take an example starting grid and assume it is the computer's (Player 1 or "O") turn:

We can now go through each possibility and shape it as a tree:

If we switch out each result with the value that gameOver would return, then the tree starts to look familiar:

Using the minimax algorithm, we can minimize Player 2's turn and maximize Player 1's turn to find that the best path is indeed putting a "O" in the bottom right corner.

Check Your Work

Step 19
We should now have an invincible computer!

Tic Tac Toe 3: Hard AI Info

For Teachers and Schools

Teach coding to your students with MVCode Teach

MVCode offers an integrated product designed to teach coding to students.