0:14

In this video I'm going to talk about Minimax.

Â A Minimax strategy is a game playing strategy

Â in which you try to minimize the maximum loss.

Â All right?

Â Now at first this might seem counter-intuitive.

Â Right?

Â When you're playing a game you want to do the best that you can.

Â But the problem here is your opponent.

Â Right?

Â Your opponent's not going to just let you do whatever you want.

Â So the basic idea here is that you look at if I were to

Â make this move, what are all the possible counters that my opponent can make.

Â All right?

Â When you look at all those counter moves, all right, what you want to do.

Â Minimize your maximum loss, right?

Â Because I'm going to do the thing that makes you lose

Â the most, and you want to pick the move that

Â minimizes that maximum loss, and that ends up being your

Â best move and your best strategy for playing the game.

Â So let's take a look at how this works.

Â So the first thing I want to do is represent my game as a tree.

Â Okay?

Â And so what I'm doing here is I'm saying

Â that this is the initial state, or the current state.

Â Okay, it doesn't really matter.

Â All right.

Â And that could be a board position, so

Â if I'm playing tic-tac-toe, this is a board position.

Â All right?

Â And, then, this is the first move.

Â Okay, so let's say that player A is the first to go.

Â So this is A's move, all right?

Â And this is the next move.

Â So these are B's moves.

Â Okay, so from the current board position what I'm saying

Â here is A could go to here, here, or here.

Â So A has three possible moves, and after A has made those moves,

Â B has two possible counter moves to each move that A could have made.

Â 1:45

Now, let's imagine that this is just a two game, and we're done.

Â At that point, I want to score these bottom boards here.

Â And let's just give them numbers; let's say that

Â this is one, zero, minus one, zero, zero, one.

Â Okay, and let's look at this print from the perspective of a, all right?

Â Player A is the first to move so a

Â positive one means, you know, something good for A.

Â A negative one means something bad for A and

Â good for B and a zero perhaps means a draw.

Â Okay, so, perhaps this means a one is a wins.

Â So this is A wins,

Â 2:24

this is a draw, this is A loses.

Â Okay?

Â All right, so what's actually happening here now

Â is that this first level, all right, okay.

Â It's a maximum level.

Â I want to choose the maximum score of my three possibilities.

Â This is a minimum level.

Â Okay?

Â So what's going to happen here is I picked the minimum of what's

Â going to happen, so I've got zero here, minus one here, and zero here.

Â 2:55

Okay?

Â And now at this top level it's a maximum level so I

Â pick the maximum of zero minus one, zero and here is a zero.

Â And so what that basically means is, A tried to

Â minimize his maximum loss and ended up with a zero.

Â Okay, [LAUGH], all right, fine.

Â So what does that mean?

Â He draw, he ended up with a draw.

Â And let's intuitively figure out what that means.

Â Okay, so, so if A were to move down here.

Â Okay, there's two thing that could happen.

Â He could win or he could draw.

Â So, B is not dumb.

Â B is going to make, pick the, make the move this way to draw.

Â Okay, so the best I can do if I go over here is a draw.

Â All right?

Â If I go here, all right if this is the move I make.

Â All right I've got two possibilities all right.

Â And B has a winning move now.

Â So B is going to pick this move and so B wins the game all right.

Â So if I go here B is going to win.

Â So this is a bad move.

Â All right if I go over here all right.

Â B has two choices, B can force a draw.

Â All right, or B can lose at the game.

Â So B's obviously going to force a draw.

Â All right so there's no move that A can make

Â in this game, that allows A to win the game.

Â The best that A can do, is force a draw.

Â Okay, and if B actually screws up, I guess A could win the game.

Â All right?

Â And so this is the basic idea, you

Â alternate back and forth taking the max and

Â the min, and when you get down to

Â the bottom you have to actually score the board.

Â This is easy if you can build the tree all the way

Â out to the end of the game, then the score becomes obvious.

Â Yes, right.

Â You assign some value to winning, some value to losing and some value to a draw.

Â All right, if you can't go all the way

Â then you have to have some juristic function that

Â just sor, sort of gives you some notion of

Â how good it is to be at a particular position.

Â So we're trying to do this for chess for instance.

Â You're not going to be able to go all the way to the end of the game.

Â You're going to have to evaluate particular chess board positions and

Â say this is a good position, this is a bad position.

Â And then you can run minimax on that.

Â 4:42

Let's make this more concrete by looking at tic-tac-toe, okay.

Â I could draw the tree for tic-tac-toe starting at the empty

Â board but that's going to get way too big for the slide.

Â So instead, we're going to start the tree from here.

Â Okay, this is the current state of the game.

Â Okay, and I can run minimax from any state okay.

Â So if this is where we're at, then I

Â can run minimax here to decide what to do next.

Â Okay and if you look at this board it's now X's term, so these are all the

Â possible moves that X could make, these are

Â all the moves that O could make in response.

Â And these are the final moves that X could make.

Â All right.

Â And we're to try, we're trying to decide what X should do here.

Â So we have to figure out how do we actually score these boards, all right.

Â And I'm going to make the arbitrary decision to decide that

Â if X wins, we're going to score the board plus one.

Â If it's a draw.

Â 5:33

We're going to square the board zero.

Â And, if O wins, we're going to score the board minus one.

Â All right, and what this means basically is that

Â every time it's X's term, a we're going to

Â try and maximize the score, and every time it's

Â O's term we are going to minimize the score.

Â All right, and this is going to allow us to

Â choose the best moves for X the best moves for O.

Â 6:20

Now let's move over to the far right and think about

Â what's happening at the right hand side of this tree, okay?

Â So if we're at this board position, okay?

Â It's now X's turn to move, right?

Â X only has one choice but this is a maximizing

Â level, so we try to maximize what we can get.

Â Our only choice gives us a score of zero, so the max of zero is zero.

Â All right, that does actually look like a zero, all right.

Â Over here on this board right next to it, again we only have

Â one move, we're trying to maximize, we end up with a zero, okay.

Â Now, let's consider the parent node here.

Â This node right here, okay, it's O's turn.

Â So, this is a minimizing node.

Â O have two choices, O can either move here or here.

Â All right?

Â Unfortunately both of these moves you know, have a

Â score of zero, so minimizing them, I get zero here.

Â O has no, you know, winning move or no better move than either, you know, each

Â move is equally good or equally bad depending

Â on the way you want to look at it.

Â Okay, so let's move over to the middle know.

Â All right?

Â So, if I look at the bottom, it has a score of zero.

Â If I look over here.

Â All right, O actually won the game.

Â All right, so this has a score of minus one.

Â All right, let's look at this node here, okay.

Â It is you know, X's turned so, this is going to be you know, maximizing level.

Â So, I look down there, and the score is zero, so I maximize that by taking zero.

Â Okay.

Â Now, let's step up here.

Â 7:53

Okay, if we're here, it's O's turn.

Â All right?

Â So it's a minimizing level.

Â So I look at the two scores beneath me,

Â minus one and zero, the answer here is minus one.

Â This is a board position by which O can win the game.

Â All right, so this has a score minus one.

Â All right, let's move back over to the right here.

Â 8:10

Okay.

Â This game is over.

Â Okay so there is three in a row for O,

Â O wins the game, this has a score of minus one.

Â Over here it is X's turn, X has one move,

Â it's maximizing at maximum of zero is zero, okay fine, zero.

Â Okay, we look over here up at the parent.

Â Okay, it is X's turn, so we are going, or I

Â mean, I'm sorry, it is O's turn, so we're going to

Â minimize, all right, we minimize, we look at minus one and

Â zero, okay, we give this board a score of minus one.

Â So if X chooses to make this move, O has a winning move.

Â If X chooses to make the center move, all right.

Â So, I guess this is the move here.

Â If X choose to make this move O can win the game.

Â If instead X chooses to make this move, O can win the game, or finally

Â if X blocks that winning spot here, okay, the game is going to end up in a draw.

Â All right.

Â So, we go back up to the top and say, what is the the score here.

Â Well, all right.

Â We want to maximize because it's X's turn, so the

Â maximum of minus one minus one and zero is zero.

Â Which indicates that X should move here, right

Â doesn't matter what O does after that, okay?

Â All right and this is the basic idea behind Minimax.

Â It not only tells you what the score is, it actually tells you what move to make.

Â Okay, I can trace back through here.

Â Right.

Â If I go this way, if X does make a bad move and put us in the left.

Â Then O should move this way, right?

Â Because that's the minimum node.

Â Similarly O should move this way because that's the minimum node.

Â All right, so you should move along if you're X,

Â along the maximum path if you're O among the minimum path.

Â Okay?

Â 9:47

So key idea of Minimax here is to think about the game as a tree, right?

Â Where the root of the tree is the current state of the game.

Â And then each successive level of the tree is a move by you

Â or a set of moves that are possibly by either you or your opponent.

Â Right, and then you try to evaluate that tree in such

Â a way that you figure out what you're best move is.

Â Assuming that you're going to do the best thing at you can at each level

Â and your opponent is going to do the best thing that they can at each level.

Â So how do I define best?

Â Well, the idea here is that best is defined as minimizing your maximum loss.

Â All right, so you want to force your opponent

Â into a situation where they can do the

Â least damage so to speak, because you know they're trying to, you know, win as well.

Â So they're trying to give you the maximum loss that they can.

Â And so by restricting them into minimizing the maximum that

Â they can do to you, you've made your best move.

Â And they are going to be doing exactly the same thing at each level.

Â All right, and so you alternate back

Â and forth between minimizing and maximizing, all right.

Â And you end up picking the best move that you can.

Â