Tic Tac Toe 3: Hard AI

Planning
Step 1
In this lesson we will be making a hard to beat computer for the Tic Tac Toe game
Information
Step 2
The first thing we will need to do is improve the "gameOver" function

It will return a number based on the result of the board. We will need to know which player is winning for the AI algorithm to work.

Note: The computer "O" will be a positive number and the player "X" will be a negative number so the algorithm is trying to help the computer.

Step 3
Change this code inside the gameOver function:

Note: we explained the ? : operator in the previous lesson. It acts like an if else statement.

Information
Step 4
We will also want the gameOver function to be able to check multiple grid possibilities and not just the active one

We will pass in a certain grid to the function so it can return that grid's result

Step 5
Add a new function parameter named "g" and replace all grid mentions with that parameter

Change this code inside the gameOver function:

Step 6
Now we need to change how we call the gameOver function.

Remember that any number greater than or equal to -1 returned by gameOver means the game is now over.

Change this code inside the endTurn funciton:

Challenge
Step 7
Inside the "mousePressed" function, fix how we call the "gameOver" function.

We need the gameOver function to take in the grid array and then we need to check if the game is NOT over (which number is that result?).

Check Your Work
Step 8
Save and run you code

The game should be working as it did before.

Planning
Step 9
Let's start learning about the "minimax" algorithm

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
Minimax Algorithm

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
Using minimax in Tic Tac Toe

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.

Step 12
Let's create a new function named "minimax"

The function will take in two parameters: "g" for grid and "p" for player.

Step 13
Now we are going to check if the current grid has a game over result

If it does, then we return the result as an object because we will need to know the score and the move index to get that score.

Step 14
If the game is not over, then go through all possible moves with the current grid

This for loop and array will find all possible moves. The moves array will keep track of all possible moves.

Challenge
Step 15
Next we will be using minimax as a recursive function to find every possible move

The blank code should be the symbol of the next player for the next turn.

Basically this logic:


If (p == "O") {
return "X";
}else{
return "O";
}

Hint: Use the ? : operator.

Step 16
Now that we have every move, we will select the best move based on which player's turn it is

The computer's turn will try to find the move with the greatest score with this code:

I use -10000 as some random small number so it will return true maximum value.

Challenge
Step 17
Now we need to get the player's best move which will be the minimum score

The bestScore should be some random large number so we can check if any of the move's score is less than it.

Step 18
The last thing we need to change is the "computerTurn" function so it uses the minimax algorithm
Check Your Work
Step 19
Save and run your code

We should now have an invincible computer!

Tic Tac Toe 3: Hard AI Info

Account

MVCode Clubs

Created By

aaronjau101

Course:

Artificial Intelligence (A.I.)

Access Level

premium

For Teachers and Schools

Teach coding to your students with MVCode Teach

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

Learn more about MVCode Teach