Toe.

Oh, with the Minimax algorithm.

That's why I'm here, because I made this other coding

challenge, Tic-Tac-Toe, where I created a kind of a big--

it was kind of a mess if I'm being perfectly honest.

But I made a working version of the Tic-Tac-Toe game

that just played with two players picking random spots.

So since then, you can check one of my live streams

if you want to find where I did this.

I made some adjustments to it so that I could, as a human being,

play the game.

So right now I'm going to play the random computer picker.

I'm going to go here.

And then I'm going to block X. And then I'm going to go here.

And ha, ha, I win.

O wins.

So what I have the adjustment that I

made is that I added a mouse pressed function

where I find where did I click?

And I put my human variable, which

is the letter o onto the board.

And then I called next turn where next turn

picks a random spot in the board and makes

that the AI spot or X's spot.

So the whole point of this video is

for me to implement something called

Minimax, which is an algorithm, a search algorithm, if you

will, to find the optimal next move for the AI.

I mean, it could find it for myself.

And then I could implement it.

But the idea is I want this player, the computer player

to beat me at the game or at least

tie to play a perfect game.

If you want to learn more about the Minimax algorithm,

I would suggest two resources that you

can look at that I actually looked at before beginning

this coding challenge.

I haven't programmed this before.

But I watched this video by Sebastian Lague that

explains the Minimax algorithm, also something called

alpha-beta pruning, which I'm not going to implement

but could be a good exercise, next step for you.

And I also found this article on the geeksforgeeks.org website,

which is three-part series about the Minimax algorithm

and how to apply it to Tic-Tac-Toe.

So those resources are probably your best bet

for learning about the theory of the Minimax algorithm

and how it can be applied to a wide variety of scenarios.

But I'm going to look at the specifics of Tic-Tac-Toe, which

is a great starting example, because it's

a simple enough game that I can actually diagram out

all of the possibilities, which even if that's computationally

possible, it's very hard to diagram.

And there's lots of scenarios where you couldn't even compute

all of the possible outcomes.

And chess is an example of that.

So Minimax is typically visualized as a tree.

So the root of the tree is the current state

of the game board.

[MUSIC PLAYING]

So I've drawn a configuration here of the Tic-Tac-Toe board

midway through the game because I

don't want to start at the beginning

where there's so many possibilities

that I couldn't diagram.

So right now it's X's turn.

And X has three possible moves.

So I could express that in a tree diagram as move one,

move two, and move three.

So let's take a look at what I mean by that.

[MUSIC PLAYING]

I'm going to use a blue marker so you can see the new moves.

So let's say one possible move is X going here.

Let me diagram out the next two possible moves.

[MUSIC PLAYING]

Another possible move is X going here.

[MUSIC PLAYING]

And another possible move is X going here.

So we need to look at each of these

and determine is the game over, or is it continuing?

So only in this case is the game over.

And in this case, the game is over, and X has one.

So I'm going to mark this green for the state of X

having won the game.

Now, it's O's turn.

And for each of these spots, O could

make two possible options.

[MUSIC PLAYING]

O could go here, or O could go here.

Oh could go here, or O could go here.

And look at these.

In this case and this case, O has won.

Remember, we're trying to solve for the optimal move

for X. X is making the first turn.

So this means I can mark these were O wins as red, as

like, those are bad outcomes.

So while these are not terminal states,

there's only one move possible for X. So I could draw an arrow

and put that down here.

But ultimately I can just consider this

as X has to go here.

So these, you could consider as terminal and in which case

X will win.

Now, you see that I visualized all the possible outcomes

of the Tic-Tac-Toe game based on this starting configuration.

So how does X pick which path to go down

where we can see here that the goal is X to win the game

to get to here, here, or there.

How does it do that?

And the way that it does that--

by the way, spoiler alert.

This is the move it should pick.

It should just win instantly.

But the idea of the Minimax algorithm

is if we could score every possible outcome,

those scores can ripple back up the tree

and help X decide which way to go to find the highest

possible score.

The nice thing about Tic-Tac-Toe is

there's not a range of scores.

The endpoints are either you won, you lost, or you tied.

I could say if X wins, it's a score of plus 1 .

If O wins, it's a score of negative 1.

And if it's a tie, it's a score of 0.

So in other words, we can give this a score of plus 1.

This a score of plus 1 .

This a score of negative 1.

This a score of negative 1, and this a score of plus 1.

But we've got an issue.

I'm trying to pick between this option, this option,

and this option.

These two don't have a score.

How do I pick their score?

Well, I can pick their score based on which one of these

would be picked.

But who's picking these?

This is why the algorithm is called Minimax,

because we have two players each trying

to make an optimal score.

X is what's known as the maximizing player.

So to go from here to here, it's X's turn.

And X is maximizing.

But here, it's now O's turn.

O wants to win.

X can assume that O is going to play their optimal move.

Now, you could have a situation where your player doesn't

play optimally.

And that's something you might have to consider

in terms of game theory.

But in this case of the algorithm,

we can assume that O is going to make the best possible move.

I mean, if it makes a worse move, that's only better for us

anyway so it's all going to work out.

So O is what's referred to as the minimizing player--

the minimizing player.

So O has the option of picking negative 1 or plus 1,

negative 1 or plus 1.

Which one is O going to pick as the minimizing player?

The option to win so we can then take the best outcome for O,

the minimizing outcome for O and pass that back up

here's the score and the same thing here.

Now, X is the maximizing player.

Which one of these is it going to pick--

negative 1, plus 1, or negative 1.

These are negative 1, because even

though it could win here, if X goes this way,

O is going to win.

If X goes this way, O is going to win if O plays optimally.

So this is the way to go.

This scenario that I picked might not

be the best demonstration of the idea.

In fact, there's no ties here.

There's only two turns being played.

So maybe what you might want to do is pause this video

and do the same exact diagram but have

X and O with two starting positions

and see if you can diagram that whole thing out yourself.

So how do we implement this in code?

So that your first clue should be the fact

that this is a tree diagram.

Anytime you see a tree diagram, typically

speaking, a recursive algorithm, a function

that calls itself is something that will apply.

And this case is no different.

I want to call Minimax on this board position,

try, and then loop through all the possible moves

and call Minimax on each one of these board positions, loop

through all the possible moves.

If I ever get to an end point, return the score,

and have that score backtrack up or ripple back up the chain.

So let's see if we can write the code to do this.

So this here is the place where I want to write the new code.

Currently, a move is chosen by picking

a random available spot, and I no longer want to do that.

I'm actually going to change the name of this function

to Best Move.

And I don't need to worry about this, what's available.

I just want to actually look at all the possible spots.

So basically, I just want to know is the spot available?

If the spot is available, I want to try going there.

So I'm going to say board--

IJ is the AI player.

And then I want to call Minimax on the board.

Why do I want to call Minimax?

Because I want to get what is the score?

I want Minimax with return to me the score

for this particular move.

Now, it's going to have to recursively check

these two spots.

But we'll get there.

We're getting there.

Ultimately, though, I need to figure out

which one was the best.

So I need to keep track by saying,

like the best score is negative infinity.

If score is greater than the best score,

then that's the new best score.

And the best move is this particular IJ.

And let me declare best move.

So, again, I haven't implemented Minimax yet.

I'm just getting the basic idea down.

For the furthest turn, I need to start

by looking at all the possible moves, get the score for those

by calling this mysterious Minimax

function I'm about to write, and find the best one,

then apply that move.

There's a big issue here, though,

because I am changing the global variable aboard.

I am altering the game.

I am moving X to that spot and then moving X to the next spot.

So I can make a copy of the board.

But I think an easy way to deal with this would actually just

be to undo it.

So right afterwards, I'm going to just quickly undo that move.

The next step would be to write the Minimax function that truly

write the algorithm itself.

I kind of want to know to see if there's any errors here.

So actually, what I'm going to do

is I'm just going to put a placeholder function in,

Minimax, which receives a board.

And then I'm just going to return the score of 1.

So Minimax is always going to return the score of 1,

meaning it's not going to be able to pick.

They're all going to be a tie.

So it still is going to pick the first one.