Name: Coding Challenge 154: Tic Tac Toe AI with Minimax Algorithm
Uploaded: 2020-03-27T19:21:07.000Z
Duration: 26 min 33 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

[WHISTLE] Hello, and welcome to a coding challenge, Tic, Tac,

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

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

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

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

made is that I added a mouse pressed function

And then I called next turn where next turn

picks a random spot in the board and makes

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

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

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

If you want to learn more about the Minimax algorithm,

can look at that I actually looked at before beginning

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

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

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

So Minimax is typically visualized as a tree.

So the root of the tree is the current state

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

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

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

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.

And another possible move is X going here.

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

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

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

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

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

Subtitles ListPlay Video

Coding Challenge 154: Tic Tac Toe AI with Minimax Algorithm

ultimately

scenario

figure

negative