Skip to main content
Loading Explore guides…
Adversarial Search · Acedra
Home
Explore
Computer Science
Adversarial Search
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
175 segments
Copy
Hide video
0:00
[NO AUDIO]
2:17
[SIDE CONVERSATION]
2:58
PROFESSOR: Hi, everyone. Welcome to the sixth lecture of CS 188. Couple of announcements for today-- your homework 2 was due yesterday. So this is an after-the-fact announcement, but it's good if you missed it that you know that next time not to miss it. Also, your homework going forward always has three components. There is an electronic part, a written part, and a self-assessment of the previous written homework, so just a reminder of that. For the written and for the self-assessment,
3:35
use the template we provide such that it matches exactly up with what we have and fill in the blanks as you solve the problem. There is a mini contest-- a little more about that in a second. Homework 3 games will go out soon, probably tonight, otherwise tomorrow. It will be due next Monday. We'll again have three components. And project 2 games will go out probably tomorrow and will be due next week Friday at 4:00 PM.
4:11
The contest that's part of project 1, this is optional but we think very exciting. So I want to highlight a little bit what's going on there. So this only counts for extra credit and for glory, not for regular points. What do you get to do in this contest? In project 1, the mazes were relatively small, and there was only one Pac-Man trying to eat the food. In the mini contest, you get to control multiple agents who together are supposed to clear out the board.
4:46
And in addition to controlling multiple agents on large boards, you also get to be time-constrained. So we all know that if you get infinite time, you can even run uniform cost search on these problems and ultimately return a solution. But that's not useful in practice. In mini contest 1, you get penalized for time used. The more time you use, the more you get penalized. If you can make fast decisions, you lose less points. And then if you eat dots, you win points.
5:18
So this is an example of a board there. If you submit-- so a couple things to note-- this will be closing on Sunday. So there's about a week left. You get 0.5 points of extra credit on project 1 per staff bot beaten. There is two staff bots coincidentally named staff bot 3 and staff bot 2. And there is 0.5 points for submitting any bot. So just go in there, get yourself a bot, and submit. You get 0.5 points already. And then we'll also rank students based on performance of their bots.
5:51
And there is a little bit of extra credit related to that. And there's a leaderboard. Here is the current leader board. Staff bot's not on top anymore. Jason [? Lu ?] here-- here? Congratulations, you're currently first. That's awesome. [APPLAUSE] [INAUDIBLE] here? [INAUDIBLE]? Anybody just want to claim it? Don't do that. [LAUGHS] White guy claiming [INAUDIBLE].. [LAUGHTER] You can choose the name of your team freely. It doesn't have to be your own name.
6:33
You can do it in teams of two, just like for the project itself. And when you submit, your agent will appear on the leaderboard. Right now, this is the first 20. But actually, there is six of those pages for about 120 total agents in competition now. Some agents have one student behind them. Some agents have two students working together behind them. So I encourage you to check it out. It's set up such that once you've completed project 1, getting a starter agent going should
7:03
take extremely little time. Then, of course, to do something more interesting requires some extra thought about what it takes to get two agents or multiple agents to work together and how to work under time constraints. Any questions about logistics? Yes. STUDENT: So you find the string for the how long it takes to find a path or how long it takes Pac-Man to move on the path? PROFESSOR: OK. So you get penalized for amount of time you use before you decide what your next action is.
7:35
So the interface is the environment waits for the next action to be given. And the agent is computing, computing, computing, finally gives the next action. Then the environment says, how much time did you take? Based on that, points get subtracted and then executes the action. And thanks to the action, you might get new points. And this process repeats. If you have a shorter path, you might collect more points than if you used the longer path.
8:03
But if you take a very long time thinking to get a short path, you might still do worse than somebody who has an agent who chooses a longer path but can find it quickly.
8:15
STUDENT: [INAUDIBLE] [LAUGHTER] PROFESSOR: Any other questions about logistics?
8:33
OK, let's start with the technical content of this lecture, adversarial search. This is about game playing in many ways. So let's take a look at game playing state of the art. Checkers-- one of the first games for which there were good AI players. In the '50s, there was a computer player-- decent. In '94, there was the first computer champion. This computer champion took over from Marion Tinsley, who had for 40 years straight been the number one in the world in playing checkers.
9:05
So this was somebody who was just superior to everybody else in the world for 40 years. But then a computer came in and took it from him in '94. Then in 2007, checkers was "solved." What does it mean to be "solved" versus beating the best humans? Beating the best humans is something where it's just the level of play that you're at. Being "solved" will become more clear later in lecture, but it means that you know that you can force a win or force a draw if both sides play optimally.
9:36
And we'll find out more about what that means. But for now, let's already put it on the chart-- checkers solved. Chess-- '97, Deep Blue defeated Kasparov, the human champion, in a six-game match. Deep Blue was able to examine 200 positions per second at that time, with computers from 20 years ago. Used a very sophisticated evaluation function, which we'll see more about today, and some undisclosed methods that IBM did not tell anybody. And some searches were 40-ply deep,
10:07
which we'll also see more about today, but that's searching very deep in your game tree of possible scenarios of how things could play out. Current programs are even better, but a little less historic because the best human player has been beaten. Chess is not solved in the sense that checkers is solved in that we don't know for sure who is guaranteed to win or whether it's guaranteed to be a draw if both players play optimally. A lot of people suspect it's a draw, but it's not been proven.
10:38
Go-- this is what we would say just a few years ago. Human champions are now starting to be challenged by machines. And that's a recent thing as of the 2010s. Before the 2010s, humans wouldn't play against computer Go players, because it was just too boring. It would be an insult to be asked to spend your time that way. Why was it so hard to build good Go players? So on Go, the branching factor is 300 roughly on average throughout the game.
11:06
And that means there's a lot of possible future scenarios. So classic programs used knowledge bases. But then a lot of advances started to come in through Monte Carlo. Expansion methods, which essentially means something along the lines of, from the current situation, if I let both players play randomly a few times, who wins more often? And you use that to decide whether that's a good position for white or for black to be in. But this changed.
11:35
In 2016, AlphaGo defeated the human champion using still Monte Carlo tree search but also learned evaluation functions of a quality nobody had really anticipated were achievable anytime soon. And again, we'll see more about evaluation functions in this lecture. But that's where the big surprise was. A lot of people thought Go was maybe still 10, 20, 30 years away. But the quality of evaluation functions completely changed that. And then Pac-Man-- that's what we all want to know here.
12:06
Still have to figure it out. Maybe we'll figure it out by the end of the semester. Open problem for now. OK, so let's take a look at Pac-Man in action. So here is-- where is the game? There it is. Here is a game situation. Now there are ghosts. Let's watch a mastermind Pac-Man in action.
12:40
In the terminal window, you see a bunch of competition happening, which we'll understand more about later. For now, the thing to pay attention to is that indeed it is somehow avoiding the ghosts, eating food pellets, and periodically eating one of the power pellets. And when it eats power pellets, it can eat ghosts and get extra score for eating the ghosts at that time.
13:26
OK. That's how I mastermind Pac-Man. And that's what we we're going to be after in this lecture, to try to understand what it takes to build something like this but while not having to write lines of code of the type "if a ghost is nearby on that side, move in the other direction. If there's a power pellet in that direction, move in that direction." We want it to reason about the consequences of its actions and the ghosts' actions to infer from that what is the right thing to do.
13:55
OK, so let's first do a quick step back and talk about types of games. There are many different types of games. You've already probably in your free time played a lot of games-- computer games, board games, and so forth. What are some axes along which we can categorize them? Well, one axis is whether they're deterministic or stochastic. So an example of deterministic would be checkers, or chess, or Go. Example of stochastic would be backgammon, where there is a roll of dice that determines which
14:24
moves are available to you. Then the number of players-- one, two, or more players. Solitaire would be a canonical game to play alone. Two players-- checkers, chess, Go, backgammon. More players-- poker. A lot of board games have more than two players. Then another axis along which you could categorize games is whether they are zero-sum or not. We'll see a little more on that very soon. But the general notion here is, are you all playing against each other or is there some notion that you're not
14:59
all playing against each other? And then there is a question of perfect information or not. Do you know everything about the current state of the game when you decide on your action? Or do you not know everything? An example of knowing everything would be chess, checkers, Go. You see the board, and that's all there is to it. An example of not knowing everything would be poker. You don't know the cards of the other players. So that's an imperfect information
15:26
game where you have to think about possible scenarios-- what cards might they be holding; as a function of what cards they're holding, what might I want to do; and so forth. What we want in this setting-- any one of those settings-- is somehow an approach that allows us to calculate a strategy, a policy that tells us what to do in a current situation and then again in future situations. So this is going to be a little different, the result of this, than what we get in regular planning.
15:54
In regular planning, we just generate a sequence of actions that we can just execute. But here, because there's an opponent that we don't control very often, we need to find a strategy which prescribes what to do as a function of the situation we are currently in or going to be in. Well, folks, in deterministic games for now, we'll see stochastic games next lecture. Now, the same thing we've done with search and with CSPs is that we want to find a unified interface for all
16:23
these real-world problems such that once we have the unified interface, we can then have one implementation of an algorithm that applies to any of the real-world problems that's cast into this interface. So here's one way to formalize the interface for games. There is a set of states and a start state as 0. There is a set of players which often take turns. Definitely in what we consider, they take turns. Then there is a set of actions. This can depend on which player you are,
16:51
what actions are available to you. There is a transition function, which is a lot like a successor function in regular search-- state and action to next state. There is a terminal test. Is the game over or not in the current situation? And then there are terminal utilities. This is maybe the newest type of thing. But what we're going to do is every outcome of a game will be scored. Simple games might have just three types of outcomes-- win, draw, or lose.
17:20
But more complicated games might have a wider range of outcomes. For example, in poker, the amount of money you make might be the utility assigned to an outcome. And then it could be a range of values rather than just win, lose, or draw. Solution to something put into this interface is a policy. And a policy is something that tells you for every possible situation you could be in what action you should be taking.
17:48
What's this zero-sum thing that we're going to be focusing on in this lecture? In zero-sum games, agents have opposite utilities. They have to fight over one resource or set of resources that's available. And if one agent gets it, the other one doesn't get it. And so the more the other one gets, the less you get. This allows us to think of utilities as not separate utilities for each agent for each situation. We just need one number. We have the utility for agent 1.
18:16
And then agent 2 we know has the opposite utility, the negative of the utility of agent 1. So this models situations where it's pure competition. It's one agent against the other. There are other types of games-- and we'll see some of them in the future-- where agents have independent utilities. And sometimes this opens up more opportunities. This opens up opportunities for win-win outcomes where you say, I might not care so much about the orange ones. I don't care about the green ones.
18:46
But the other way around, you do care. And so here, blue agent collects all the green ones. Red agent collects all the orange ones. And in the process, they're helping each other, making it easier to collect the ones they're looking for. Many real-world scenarios, in some sense, are of this type. But often, the essence can still be simplified in many situations to zero-sum games. And those are the ones we're studying today. OK, so to solve zero-sum games, we'll
19:15
use a set of approaches called adversarial search. It's something where you, as an agent, have to think about as a function of what you do what will the other agent do who's working against you, what opportunities will you then see after that, what will they see after that, and keep thinking about what if, if, if, if, and so forth through, ideally, the end of the game. So let's first look at something we're already familiar with, which is a single-agent game tree.
19:42
A lot like search, but we'll formalize it as a game tree. And then from there, we'll generalize to multiple agents-- two agents for today. OK, here is Pac-Man trying to collect food-- simple maze. Two actions available-- west or east. Then after that, again two actions available and so forth. All the way on the right, it's done. The other ones, it can still keep going. In these game scenarios, with each terminal state, we associate a utility. So for example, this has a utility of 8--
20:12
which is a standard scoring we have in our Pac-Man games-- minus 1 for every time step spent, every action taken, plus 10 for every pellet eaten. So two steps, one pellet eaten, that's 10 minus 2, 8. And maybe the numbers for the other ones end up being something like 2, 0, 2, 6, 4, 6, and so forth. If you're a single-agent, you control where you go in this tree. So things are actually relatively easy. You would say, OK, let me look at the tree. What do I see here? Well, 8 is the highest.
20:41
So I should do this and then this. And that solves the game. But let's formalize this a little bit more. So each state in the game has a value associated with it, which is the best achievable outcome from that state. So for example, for this data over here, that's very easy. It's a terminal state. The best achievable outcome? Well, there's only one outcome from that state. It's that you terminate the game, and you get 8. So the value of this state is 8. How about a state like this one?
21:14
What would be the value of that state? Well, it's the best you can achieve starting from that state. And it looks like from looking at this tree that you can end up with a 4, with a 6, or with an 8. 8 is the best achievable. And so the value here would also be 8. How about the value of this state over here? Well, it looks like there's opportunities for a 2, a 0, a 2, a 6. 6 is the highest. So the value would be 6. How about this one at the top here?
21:45
Well, you can either go to the left or to the right. Either you end up with a value of 6 or with a value of 8. 8 is better. You control that. So 8 would be the value of your state over here. And so the way we did this is that for non-terminal states, we looked at the children and took the max of the values of the children, because we control where we go and that's the value of that non-terminal state.
22:17
Let's now generalize this to adversarial games. So here we have Pac-Man and ghosts. They're working against each other. Pac-Man tries to maximize score. The ghost wants to minimize score by eating Pac-Man. So let's see what happens. First, Pac-Man gets to take an action. So we're assuming alternating moves here. Could be going left or right. Then after that, the ghost gets to take an action. Then after that, things keep repeating. And then for each sequence of alternating actions,
22:53
at some point the game might end. And then with the end of that game, some utility is associated. If Pac-Man survives and has eaten all the food pellets, it would probably be a high score. If Pac-Man doesn't survive, it'd be a very low score. So let's zone in on a smaller version of this to annotate this with some concepts. Let's assume that the game is over after each player has made a move. This is not how the real game works, but just to get it on a slide. This is a very short game--
23:23
one move for Pac-Man, one move for the ghost. And here are the scores we have associated with that. There is a minus 8, a minus 5, a minus 10, a plus 8. You might say, well, I'd love the plus 8. That sounds pretty good to me. And you might say, well, OK, I should try to get here. But that's not how it works in this kind of game, because actually the ghost controls this node. And if you were to end up in this node, ghost would prefer to have the lowest possible outcome.
23:54
So ghost would say, I'm going to do this, and it's going to end up with minus 10, such the value of this node over here is minus 10. The plus 8 is just there. It might be tempting you. You might want to try to get it. But you're just not going to get it. The ghost is not going to give it to you. So this value here is minus 10. Similarly, on the other side there's a minus 8, minus 5. Ghost working against you will decide it's going to be minus 8. So the value over here is minus 8.
24:22
Going one level up-- again, from bottom to top-- now, what's the value of this node over here? Well, it's the maximum of the values of the leaves-- not the leaves, but nodes below it. What's below it? An option to get minus 8 and an option to get minus 10. Minus 8 is better. So the value here is minus 8. Pac-Man will choose this move, after which the ghost will choose this move. And that's how the game will play out if both players are playing optimally.
24:53
Formalizing this a little bit, terminal states, we have known values. v of s is whatever we annotated it with when this slide was not written on yet. Then states under opponent's control, we have a minimization happening of the utility. And states under our own control, for the maximizer agent, we have a maximization happening. And again, keep in mind there is a plus 8 here, but we're not going to get that. What we're actually going to get is this outcome over here.
25:23
OK, let's look at a very simple board game-- Tic-Tac-Toe. Has anyone not played Tic-Tac-Toe before? OK, so everybody knows Tic-Tac-Toe. You need to get three in a row. It starts with an empty board. You can choose any of the nine squares to put your mark in. Then the other player goes. And this process repeats until either one player has three in a row or the board is full and then the game is over with a draw. What is the value of this node over here? Well, you have to think about this.
25:58
You have to think about, well, I mean, there is a plus 1 at the bottom somewhere. There's many plus 1's for various outcomes. There's various 0's and various negative 1's. But what can you get to when you're playing against an opponent who's really playing cleverly against you? Well, one thing we definitely know is that either the value here is going to be negative 1, or 0, or plus 1. It's not going to be anything else, because the values are obtained by just taking maxes and mins of values that
26:26
are leafing out to leaf nodes. And by taking maxes and mins of negative 1, 0, and plus 1, you never end up with anything else than those three. But which one it is? Well, for that, you have to work through the game tree. You figure out the entire tree. You work through the process that we just did on the previous slide here, taking maxes and mins at each respective node till you're all the way out the top. And it turns out that if you work through this carefully,
26:50
you find out that the value is 0, which means that if you're two smart people who are going to play this game, you know ahead of time it's going to be a draw. And that's actually what it means when I referred to at the very beginning of this lecture for a game to be "solved." The game of Tic-Tac-Toe is solved because we know that if both players play optimally, the value of the top node is 0. Same thing is true for checkers. People have worked through it with more efficient algorithms
27:20
than just drawing out the whole game tree but have worked through it in efficient ways to conclude that for checkers it's also 0, I believe. But I'm not 100% sure whether it's 0 or 1. So that's what it means to be "solved." OK. So now let's design an algorithm that is more computer executable than us looking at trees. Yes. STUDENT: Back to the last slide for a second. PROFESSOR: OK. STUDENT: A game with the possibility for an arbitrarily long cycle of states, how could you end up solving it?
27:57
PROFESSOR: OK, so the question is, what if there is a way to keep playing? So the tree would be infinite in that scenario, right? For example, what if in Tic-Tac-Toe maybe you could erase something and then you could keep going? So a lot of games have setups where you cannot repeat the same move over and over to avoid getting into loops. But if there is a possibility to get into a loop that indeed the tree could keep going, and then you'd somehow have to--
28:29
well, you then have to decide what that even means. If both players decide to keep playing forever, is that a draw or-- I mean, it's not very clear what the definition is of what that means if both players just keep playing forever. But you somehow have to come up with a definition of what that means. Let's say you call it a draw. That's what some games might do, are just forbid it to go in the same cycle again. Then all of a sudden, you have something again.
28:56
Because now we've gone through a cycle a certain number of times, that's the limit. Now it's a draw. They could begin so the trees are infinite in other ways without having repeats. Maybe you have some kind of infinite board you can play on in principle, and you can keep expanding in many, many directions. Then you might need a little bit extra machinery compared to what we're seeing today in lecture. So we're not going to specifically look at that.
29:26
OK, so let's formalize this. We've been looking at deterministic zero-sum games. Examples are Tic-Tac-Toe, chess, checkers. One player maximizes the utility at the leaf nodes. The other one minimizes it. In minimax search, we have a state space search tree. Players alternate turns. And to compute minimax values at each node, we can work from the bottom to the top. For example, for this here, we have minimizer says this is 2. Minimizer says this is 5.
29:54
And then the maximizer knows that the value at the top is 5. And the game would be played out this way. That's the minimax solution to the game, with both players playing minimax strategy.
30:10
This is illustrated on the slides. How do we formalize this? Well, at a max node, what we're doing is we're initializing our estimate of the value of that node as negative infinity. And then we start inspecting all the children, see what the value are of the successor nodes, and if they're higher than what we have so far, we increase and ultimately return the maximum value we've seen among all successors. Min, that's the exact counterpart. Start out plus infinity when you've seen nothing.
30:40
And then whenever you have examined a new successor, you check if it's better for the minimizer than what you've seen before. And if so, you update the value. And you keep looping till you have gone through everything. Of course, if you just use this, this is a recursion where you go from min to max from max to min and keep going. There is no base case here. So this actually wouldn't really work. So in your code, you'll have to install a base case of some type so you'd
31:07
have dispatch function that computes value of a state. First checks, am I hitting a base case? If I'm hitting a base case that is a terminal state, return the value of that terminal state. If not, then check what kind of node I'm in. Am I in a maximizer node? Then call max. If I am in a minimizer node, call the min value function and execute that. And to the earlier question, if the game keeps going forever, then some of these occasions you will never hit the terminal state, and you'll
31:42
have to somehow decide how your algorithm is going to stop early. It might say, after I am a million moves deep in the game, I'm just calling it done on this branch and have some kind of resolution calling it nevertheless a terminal state because it's been going for so long.
31:59
STUDENT: Question. PROFESSOR: Question-- yes. STUDENT: So if there's an algorithm, are we [INAUDIBLE] to move step-by-step? For example, the one Pac-Man question where we first moved Pac-Man then the ghost movement, is it a different type on all [INAUDIBLE]?? PROFESSOR: Correct. In everything we're looking at here, it's going to be turn-based games, where the moves are alternating between players. There are other types of games where players takes decisions simultaneously.
32:27
We're not going to look at those in the current two lectures.
32:42
OK, now we have an algorithm. This is essentially the counterpart of our tree search or graph search from when we did search in the first-- well, in lecture 2 and 3. And we can now run this. This is a lot like depth-first search. It's just traversing the entire tree. It's not skipping anything. It's not prioritizing anything over anything else. Just going successor, by successor, by successor, and going deeper, deeper, deeper before it's coming back up. So if you had a game tree and the program
33:10
was running through it, it would start with the start state. It wouldn't draw out the entire tree like we've been doing and then from the bottom push things up. It would actually start at the top. It would say, OK, what are the successors? Three successors. Let me look at the first one. Let me dispatch that one. It's a min node. OK, let me call min value on that. What does it mean to call min value on this one? It means to call its successors and loop through them.
33:34
Oh, looks like the first successor is a terminal state, value of 3. That can be passed back up. And now we have v equal 3 here as our estimate. Next one is 12. Since we're minimizing, v stays 3. Next one is 8. v stays 3. At this point, we're done. We've seen all successors. And we can pass this back up. And our estimate at the top here is now 3. But it might still change, because we've only seen one of the successor nodes, not all of them yet. Now the depth-first search goes down next branch.
34:06
Oh, it's a minimizer node again. Look at its successors-- terminal state. This now says, oh, the value here is 2. But it might still change as we see other successors. 4 is not going to change that. 6 is not going to change that. So it's 2. We pass this back up. The maximizer says, I had 3 so far. This new option is 2. That's worse. So I'm sticking with 3. Going to the next successor, again minimizer. Here, the value would be 14 right now. Then the minimizer looks at the next successor.
34:40
5-- so updates to 5. Then sees 2. Updates to 2. 2 over here. That gets passed back up. Maximizer says, well, 2 is worse than 3. 3 is the best I've seen. I've seen all my successors. 3 it is. And I will take the corresponding action, which is going this way, after which the minimizer would take the corresponding action, which is going this way. And the game would end up over here. So that's the procedural execution of how the minimax search would work. Any questions about this?
35:27
OK. Then let's take a look at some properties.
35:34
Let's say we have this tree over here. And the question we're asking ourselves here is along the lines of we're faced with a real-world situation in some sense, and we've formalized it into a game tree. And what will minimax give us? Well, look at this. What's the value for the top player, max? Top node? STUDENT: 10. PROFESSOR: 10? Saying 10. Why 10? STUDENT: Because if you go in the other direction, the other player is going to do 9. PROFESSOR: So the answer is well,
36:10
it looks very tempting here to go for the 100 maybe. But there is a 9 there, and the minimizer would force the 9. So the value here would be 9. On the other side, it's 10. So the value of the game is 10. OK. So we have a value of the game that's 10. So that's when you play against a perfect player, like a mastermind player. You would always assume that they get it really, really, really right. But what if you play against a player like this one? Maybe you are willing to take your chances.
36:43
Maybe you don't think playing Tic-Tac-Toe is a waste of your time. You can actually win a few games. Even though the value of the game in principle for Tic-Tac-Toe is 0 against this player, it might be plus 1 for you, because they might make mistakes. And so when you play against a player that might make mistakes, maybe you want to go this way, because maybe they would go there. And if they don't, 9 is not that much worse than 10. But if they do make a mistake, a hundred
37:09
is so much better than 10. And so, if just periodically they were to make a mistake, it's worth it going that way. So now we're doing some probabilistic calculation, really. It's like, what's the chances that they might make a mistake? And based on that, maybe we go that way, if the chances are high enough and the payoff is high enough for when they make a mistake. That's a different kind of way of looking at modeling the world. It's modeling the opponent not as a optimal mastermind
37:34
playing against you but as somebody who might do some things stochastically. We're not going to look at the details of how that works in this lecture. That's for next lecture. But let's look at some of the consequences of the differences of how you look at the world will affect what you do. So here we'll look at--
37:56
well, some apologies for the situation we're putting Pac-Man into here. Pretty grim situation-- no dots nearby, just ghosts. What's our scoring system? Plus 10 for eating a dot. Negative 1 for each action you take.
38:18
So what do you think Pac-Man should do in this scenario? STUDENT: [INAUDIBLE] PROFESSOR: Some people are pointing to the right. What does that mean? There is a ghost right there. Why would you go to the right, dive-bomb the ghost? Well, it turns out to give you a higher score. If you can manage to be eaten by the ghost in one step, you only lose 1 point due to time. If you get eaten after more steps, you lose more points. So you want to get eaten as quickly as possible in this case. [LAUGHTER]
38:55
That's the minimax solution. Let's see what happens. So Pac-Man playing minimax. Boom-- one step, and game is over. But now let's consider this again. And let's think back to the not-so-smart players and look at the ghosts. Maybe they're not that smart. You say, they look a little bleary-eyed. They're not that smart, probably. Maybe I should take my chances. Well, what does it mean to take your chances? The red one is always going to come towards you. It only has one way to go.
39:29
But the blue one could go up or down. So maybe half the time it will come towards, half the time it'll go away from you. If it goes away from you, then you're lucky, because the ghosts keep running the direction they're going whenever there's no intersection. And it'll keep going away from you. You'll be able to eat all the dots and win the game. Of course, you're taking the risk that you live longer. If it does come towards you, then you could have just dive-bombed the red ghost.
39:53
So let's see what happens. Of course, if the ghost is really taking random actions to choose whether to go up or down, we don't know right now what's going to happen. But let's see what happens. Pac-Man took their chances. And indeed, blue ghost moved away. And got lucky and ate everything just in time. Now, if we play the game again, it might be that it doesn't work out the same way. I'm going to try this. OK, let's see what happens this time. Got lucky again.
40:23
But in principle, after it runs a few times, half the time it would be lucky, half the time unlucky. But it might be better than always dive-bombing into the red ghost. So the second scenario here is when you're saying, well, I'm playing one of these kind of players. So it's worth taking my chances. And we'll see how to compute optimal strategies for that in next lecture.
40:49
How much compute do we need to do this minimax computation? Well, we already covered depth-first search and how much compute it needs in the second lecture. What was it? Well, it's order branching factor to the power depth of the game, so b to the m, where m is depth of the game. Space-- b times m. So space complexity is pretty good, but time complexity is pretty bad. For chess, branching factor about 35. Of course, not the same in every moment of the game, but some average-- 35.
41:20
Maybe a hundred moves total. Then 35 to the 100, which is completely infeasible to search the entire tree. So that's not how Deep Blue beat Kasparov. It's not by searching the entire tree. Other machinery was needed to get there. And we'll see some of that machinery now.
41:41
OK, since we only have finite compute, we cannot explore the entire game tree. So what are we going to do? A first method we'll look at is game tree pruning. The question here is, do we really need to look at the entire tree to find a solution? If we look back at previous weeks in solving CSPs, we had backtracking whenever filtering said that there will be no solution down here. It's not worth doing more work because we've already determined that the domain of one of the variables is empty.
42:13
So it's waste of time to go look further here. We don't have domains of variables here that can go empty. But maybe there's something similar we can do where at some point we can conclude this part of the search tree is just not useful to explore anymore to find a solution that we need to find.
42:32
So let's do this by example first. Here's our minimax simple example again. And let's say we run depth-first search. As a reminder, what happens-- we keep going left to right through the tree. We're straight through, collect values. So at this point, this is a 3, which has been passed up. This guy thinks it might be 3, but it might still be something else. Here we now have 2. And now stays 2. Stays 2. The 2 gets passed up. This one stays 3, and so forth.
43:02
Do we really need to look at all these numbers to solve this problem? Another way to phrase this, is there is something-- like, are there any nodes at the bottom here, leaf nodes, where I could have changed their value to anything else and the outcome would have been the same, the value would have still been 3? Because if that's the case, if I can change the value of leaf node to anything else and the value was still 3 and I could know that while I'm doing
43:36
the search that that leaf node, no matter what the value, the top-- the evaluation will remain the same, then we don't need to go look at that leaf node, and we can skip it. So that's what we're after now. OK, let's see how we can achieve this. We start out just the same way. Right now we have no information about the game. So it's going to be very hard to make any claims like, oh, I can skip this because such and such. We don't know anything yet.
44:03
After we've gone through the left bottom-most node and we know this value is 3, we can propagate this back up. We have maybe 3 here. Now we have a little bit of knowledge about the game. We know that one way of ending the game is by going to this before-last node where the minimizer will choose 3. Could we have skipped any of these or these nodes? No, because if it had been lower than 3, the minimizer would have chosen it. So there's nothing we could have skipped here so far.
44:36
Now go to the next one. Is there anything we can do here? Can we just say, let's skip it? No, we can't, because the minimizer is sitting there. And what if the minimizer's options are only a hundred and above? Then definitely we need to know about that. But if they're below 3, we also need to know about that. Essentially, what we'll need to know, if there are going to be options here below or above 3, because that's what we have right now at the top. So let's take a look. The first one is 2.
45:04
What does that tell us? This tells us that the value of this minimizer node is less than or equal to 2. We don't know if it's 2 or less. We don't know if it's 2 or maybe another other value, but we know it's less than 2. Once we know it's less than 2, we know the maximizer would never prefer this. It would always prefer going that way. So it does not matter what the values are here. Because no matter what they are, the maximizer would never let the game get to that node,
45:37
because it would be worse than going to a node where you get a 3 guaranteed. The guaranteed 3 it already has up here is better than anything that could happen down there, no matter what lives over here. So we can just skip over these. Don't need to look at them. And note this would be true even if these were not terminal nodes. Imagine we're a whole big tree living underneath here-- a whole big tree living underneath here. We don't have to explore any of that tree
46:02
because we know the maximizer would never let the game go that way because minimizer will be able to make it less than or equal to 2, and maximizer could force a 3. And so we could prune massive amounts of computation if there are big subtrees over there. We continue. OK, we have a minimizer node again. At this point, we know nothing yet about this branch. We know the maximizer can force a 3. We don't know if this might be a better or worse option than the 3 it can already force.
46:34
Now we see a value of 14. Oh wow. This looks promising. We know the value here is less than or equal to 14. But if it could be 14, that would be great. Can we stop here and just ignore these? No, we can't, because we're not guaranteed to get 14. It could be negative infinity for all we know, and then we don't want to go there. So we need to keep looking. Now it's 5. So we know this one is less than or equal to 5. 5 would be great. It's better than 3.
47:01
But there are still other parts that we haven't seen. And as long as we haven't seen that, we don't know what the minimizer will force us to get there. So we need to keep looking. What is it? A 2? Now we know that it's actually 2. That's worse. And maximizer will conclude to go this way, and the game will end up over here. What computation did we save? All of the computation that would have happened over here. In a small tree like this, it might not be a lot.
47:27
But this principle can be reused everywhere in your game tree. It's called alpha-beta pruning. So what's the general version? We have a game tree. And in this game tree, we're computing the min value at some node, n, over here. To do that, we loop over n's children. As we loop over n's children, the estimate of the value of that node will keep dropping. It will never go up. Any time you see a next child's value, it can only go down what your estimate is, never go back up.
48:03
So if at some point our estimate here-- we said at this node, the value of this node is, let's say, less than or equal to some value, x. If any time x is smaller than a, which is a value the maximizer can guarantee over here, then we know that no matter what else is still in other successor nodes, it's only going to make it worse than x. And so what we know is that it's already worse than a. Maximizer can force a. So maximizer will never let this path
48:45
happen, because that would open up the opportunity to end up with something worse. So what we now know is that maximizer will never let the game get over here. So we don't really care about the exact value of the node over there because the game will not end up over there. We know it's a worse value than what the maximizer can force over here. And that's all we need to know. And we can stop exploring the successors and just pass up that value, x.
49:14
As a substitute, we know the value is not necessarily really x. But we know it's x or worse. And that's good enough a value to pass up for the maximizer to conclude, I'm never going to go there, and we're good to go. And so this way you might be able to prune a large amount of computation over here. Note when looking at the comparison, when we compare with this value a over here, what are we actually comparing with? We take a path from the node that we're currently
49:47
exploring all the way to the root of the tree. And anywhere along the path to the root, we look at maximizer nodes. There's a maximizer node here. There's one here. Maybe one here. And for each of the maximizer nodes, we see, what have they already been able to guarantee themselves? And the best thing that's been guaranteed by any of the maximizer nodes so far is the thing we compare with. And that's what we call a.
50:14
Formally, what does this look like, a or alpha? Alpha is the maximizer's best option on the path to root from the current node we're working on. And there will be a counterpart, beta, which is min's best option on the path to the root. We were talking about min. So let's go here. We're working on a min value node. As before, we initialize with plus infinity. We loop over successors. There's a recursive call in there to get the value of the successor. You compare the value of the successor
50:48
with the current value estimate. If it's lower, you update, because that means you can get even lower than you thought before. You do pass along alpha and beta in the recursive call. And what are alpha and beta? It's from where you currently are all the way to the root. For alpha, you check what's max best option already available. And for beta, you check what's min's best option already available on that path. So those you can just pass on to your child.
51:15
Then if the value we see is less than alpha-- so min can do something that guarantees less than alpha, which max can already force somewhere else-- then we know we're done. This part of the tree is not going to be visited because max will not allow it. So we might as well just return the current v that we have, which is not a precise value of that node. It's just a value that signals it's going to be v or worse. And that's enough information from max
51:43
to know further up the tree to never go there. If along the way as min is checking options it sees something that is a better option than beta, the best thing it's seen on the path to the root, then of course I should update beta. Note that these betas are local. If it updates beta here-- I'm going back into this drawing. If this min node has a beta that goes down by seeing something, that does not get passed back up. Beta is about things you can guarantee on the path to the root.
52:15
And if you're over here, that option down there is not on the path to the root. So the update of beta will only get passed into children, not passed back up. What's being passed back up is only v. OK. Any questions about this?
52:46
There. STUDENT: Isn't the calculation of the value of a node requires you to convert the tree? Because you get the value of the node, but to get to the value of that part, you have to traverse the tree or have some sort of heuristic or-- PROFESSOR: Yeah, so the question is-- if I can rephrase it, there's really two parts to the question. One part of the question is, when we're doing this work, the value of successor, what does that mean to do that work? And the second part of your question was,
53:23
can we even afford to do that work? Because it sounds like a recursion, and that recursion could be really deep. And the answer is yes. You will have to do a recursion. That's what it is doing. And this could go very, very deep and branching very widely and could be very expensive. We're hoping to reduce how expensive it is by the alpha-beta pruning, which allows us to skip over subtrees in various places. But even then, there might still be too much work.
53:49
And we'll look at how much we can prune soon. And then we'll see what else we'll need in additional machinery for many, many games to make it all work together to get to something that you can actually run. This will probably still run out of time just running it this way on a big game. You're absolutely right.
54:13
What are the properties of alpha-beta pruning? One is that it has no effect on the minimax value computed at the root. Because we only skip over things that we know no matter what the values are there, we'll end up with the same result. That's how we started out inventing this process. The intermediate nodes might have incorrect values. So when you go through this process, if you were to then keep the tree around and look at the values passed around, they
54:39
will not be exact very often, because you've decided to not compute them exactly to save time because you don't need them exactly to know what to do at the top. And all we care about is to do the right thing at the top. Then, actually, we can repeat this process. When it's next time our turn, we can run this again. So effectively, we end up with a replanning type of agent. The next time, we just run it again. Note that in the most naive way, you don't get enough information.
55:05
Because if all you have is the value at the top, you might say, oh, it's 0. We shouldn't even play. And then maybe you can convince the other person it's 0 and you shouldn't play. But actually, the other person says, no, no, no. I want to play. Just knowing that it's 0 doesn't tell you what to do. You need to know which of these are the right one. For example, if we run alpha-beta pruning, we would first go down here. We would get a 10. Pass that up. We say 10 so far. Then we go down here.
55:32
Min says it's going to be less than or equal to 10. Well, we already have a 10 that we can force. So we don't need to look at any of this. No matter what's there, we would go there. So we pass up the 10. And we end up with a 10 over here. But we actually need to remember in the process not just that we have a 10 at the top but that this 10 is one that we're able to guarantee. And what came from this side was a 10. That didn't mean you're going to get a 10 here.
56:01
But that meant it's going to be a 10 or worse. So probably don't take this one. Take the one where you're guaranteed a 10. How do we keep this information around? There is a few different ways of doing it. The simplest way to do it is then it turns out that the first one you find is the one that tells you're able to guarantee something. So if you just remember which one was first, that's the one that told you for the other ones not to do all the work.
56:26
So you keep around the one that you found first. You can take that action. If you have a hard time bookkeeping that, other options are you could instead of running the search from the top, you could run it from the children of the top node. Compute the exact values for these nodes. And then you can say, OK, these are the exact values for each of my children obtained by alpha beta pruning. Let me see which child is best. Or you could decide that you only prune on inequality, not on equality.
56:52
So you'd say, I prune if the value-- oh, that's a little big. I'll prune on strict inequality, strict smaller than-- rather than allowing for equality. So there's three different ways you can do this-- keep track of which one was first, because that one you guaranteed it, whereas the other ones you skipped computation and just said, might be this or worse; run it on the children; or prune on only strict inequalities. Good child ordering improves effectiveness of pruning. What does this mean?
57:34
Well, when you get to prune, when the other player already has a good guarantee somewhere else-- what does it mean to have a good guarantee? That means that the other player somehow looked at some good options already. So if somehow you're clever about exploring good options first and then the bad options, then more often this pruning might be triggered. With a perfect ordering, you can show that the time complexity drops to order b to the m over 2, so square root amount of computation
58:03
from doing regular minimax if you have the perfect ordering of how you explore the tree. This doubles how deep you can look. If you have a fixed compute budget, you can look twice as deep, which is a lot. If you look twice as deep as your opponent, you're going to probably beat them. But even then, just the square root-- to the question earlier-- is not often enough to solve something like chess all the way to the bottom.
58:28
This is a simple example of meta-reasoning. What do we mean with meta-reasoning? It's where you do compute to decide about what you're going to compute. So we compute alpha beta values, which allow us to then decide that for a certain subtree, we're not going to do any compute. And so we do a little bit of extra compute to then be able to discard other compute.
58:52
Let's take a one-minute break here. And then after the break, let's do a quick quiz and look at what we still need to solve problems like chess and so forth.
59:05
[SIDE CONVERSATION]
1:00:04
All right, let's restart.
1:00:09
Any questions about the first part of lecture?
1:00:17
Question there. STUDENT: Can you go back to the last one? PROFESSOR: Sure. STUDENT: So what is m here on the [INAUDIBLE]?? PROFESSOR: Oh. The question is, what is m? m stands for the number of moves before the game ends. So let's say it takes in Tic-Tac-Toe nine moves to fill the board. I mean, sometimes it stops earlier. But then m would be 9. And with alpha-beta pruning, theoretically of the optimal expansion ordering, you would have an effective depth of 4 and 1/2 instead of 9.
1:00:51
STUDENT: A different question also-- so if we do strict inequality for minimax, would that mean that we have to do more nodes that-- PROFESSOR: Correct. If you do strict inequality for pruning, you might lose a lot. Especially if a lot of nodes have similar values, then you would lose out on a lot of pruning. So your effectiveness will go down as a consequence of your approach. STUDENT: All those methods that we can start of the three, which one is the best?
1:01:16
PROFESSOR: The most-- the one that requires the least compute will be the one where you carefully keep track of which was the first one that guaranteed you a certain outcome. And you prune also on equality.
1:01:37
OK, let's do a quick quiz here. Let's have you look at this game tree. Talk with your neighbors and think about what would happen if you run alpha-beta pruning on this game tree. I'll give you 30 seconds. Just talk to each other. What's the value of the game? Which nodes might you be able to prune?
1:02:01
[STUDENTS DISCUSSING QUIZ]
1:02:34
OK, let's see. What is the value of this game, the minimax value of the game or alpha-beta value of the game? Any thoughts?
1:02:48
What's the value?
1:02:51
Anyone? STUDENT: 8. PROFESSOR: 8-- value 8. Do we need to run alpha-beta pruning to know the value is 8? No, we don't, because we know alpha-beta pruning will give us the same value as minimax. So if I ask you, what's the result of running alpha-beta pruning on this, you could say, well, that's a complicated procedure. You need to think about a lot of things. But I know it computes the same as minimax. And minimax I can just read off. On one side, min forces 8. On the other side, min forces 4.
1:03:17
8 is a better thing to be forced. So the value of the game is this. And this is how the game will play out, with a value of 8. So even though the question might have been about alpha-beta pruning, you could have solved it and found the answer without doing it. Now, what will happen when you run alpha-beta printing? Are there any nodes-- and this is a question we love to ask. It's like, OK, which nodes will not be expanded when running alpha-beta pruning? Well, let's see.
1:03:45
And let's assume we go from left to right and then see where we get to skip expansion of nodes, or inspection of terminal values. OK, initially, we have no way of skipping, because we don't know anything yet. Then here, we don't know anything yet either. So keep going. We see a 10. Can we skip the next one? No, because it might be a better option for min. And it actually is better. It's 8. Now it's 8. That's being passed back up. We have a 8 over here. What now? Can we skip anything?
1:04:17
Can we skip this next one? No, because maybe there's only good options down there, and min cannot force us to anything bad. So we need to go look. Min looks here, finds a 4. That means things are going to be less than or equal to 4 down here. Max can already force an 8 that way. Doesn't matter what's here. No matter how good or bad, the game's not going to end up over there. We can just pass up this 4 and continue. And also, it doesn't matter how big the tree is.
1:04:45
If it happens to be a terminal node-- it could be a huge tree there-- you can completely skip over it. How about this one here? What's the value of the game and which nodes can be pruned in the process? I'll give you a minute to think about it. And feel free to talk with your neighbors, see what you conclude. [STUDENTS DISCUSSING QUIZ]
1:05:41
All right. What's the value of the game? What do we get from running minimax or alpha-beta pruning? They all give the same result. Anybody? STUDENT: Is that a 10? PROFESSOR: 10, OK. How do we get 10? Again, whether we run alpha-beta pruning or minimax, it's going to be the same thing. We can just look at this is going to be 10. This is going to be a hundred. This is going to be 2. This is going to be 20. That means min can force a 2 here. It can only force a 10 over here. 10 is better.
1:06:09
Value of the game. But now we looked at everything. The question is if we ran alpha-beta pruning, could we have skipped looking at some things? OK, let's see.
1:06:20
What nodes can be skipped? Any thoughts?
1:06:28
Over there. STUDENT: The third branch. PROFESSOR: Can you give the letter on the branch that you're referring to? STUDENT: I. PROFESSOR: I? So the suggestion is that we can skip I. Any other things? STUDENT: L and M. STUDENT: After we look at I, we can skip L. PROFESSOR: After looking at I, we might be able to skip L. So that would be something not just a terminal node but in a tree that's bigger than just terminal node. Any other branches we can skip? G? G over here.
1:06:56
So we can skip going down that one. Any other ones?
1:07:04
OK, let's see if it's true, what happens. We go down this way. Can't skip anything. No information yet. We always have to first do the left bottom-most one. We're always going to have to look at everything. That's just always going to be the case. If you work through it, you'll see this one has 10. Once we have this, we can pass it up. This means that min can get less than or equal to 10 over here. We go down here. Max is looking at some things. Max says, I also already see a hundred.
1:07:35
So I'm going to do better than or equal to a hundred. But min can force less than or equal to 10 over here and force 10 that side. So a hundred is worse. No matter what's here, doesn't matter. We can prune it. G was correct. Doesn't need to be looked at. The hundred gets passed back up, and min concludes it's 10.
1:07:55
And then the 10 gets passed back up. And now max knows they can get at least 10 over here. Now we can go down the other branch. Min has to look for things here. As long as you haven't seen anything, you can't really say, I can skip the rest. So you have to go look here. Then here we're at a max. Max has to look around. Hasn't seen anything yet. And min hasn't guaranteed anything above max. So there's nothing max could do here. So we have to look at this one as 1. Then 2 is better. It becomes 2.
1:08:33
Pass 2 back up. Now this node here can force something. It can force to be 2 or less. It specifically forced a 2 by going this way. Now I'll look over here. Actually, we know that we can force 2. We look up to what max can force. Max on the path to the root can force 10. So that means max will never let the game over here. This can get cut off. And we pass up the 2, and we're done. So L was also correct. We chopped off L and G in our expansion and saved some time. OK. That was alpha-beta.
1:09:12
In terms of intuition, probably one of the harder things to wrap your head around. But after you've seen a few more examples that you've done on your own, it'll probably start coming together pretty well. Now, even when we use alpha-beta pruning and we have maybe only square root of the number of nodes to be expanded, it's still often too much. We cannot go all the way to the bottom of the tree. So what do we do? We do depth-limited search.
1:09:39
So we might say instead of going to the bottom, we stop here. And we call these in some sense terminal nodes. They're not really terminal nodes. We say it's done after two moves and associate values with those nodes and then propagate that off. That means if these are the actual values of those nodes, that's great. Typically, we wouldn't know the actual values, because that's exactly what we're trying to find. And we'll have some approximations there. And we pass up the approximations.
1:10:07
And we hope that these approximations are good enough. Remember A* heuristics, we had an approximation of distance to the goal? Same thing here. We will have some approximation of value of that node and work with it instead of the real value to achieve something. In this case, solve for minimax with-- well, evaluated against these numbers.
1:10:31
So now suppose we have a hundred seconds. We can explore 10,000 nodes per second. That means we can check a million nodes per move. Alpha-beta can then reach a depth of about 8 on a decent chess program. So we would do this at depth 8. Guarantee of optimal play is gone, because these numbers will not be precise. And once they are not precise and we use them to decide what to do, we're not solving the actual game. We're solving some approximation that we hope is going to be good enough.
1:10:59
And so the deeper we can go, the better, because then later we have to bring in our approximation. And often in practice, if you don't know how much time you have left, you might run iterative deepening. You say, I'll go up to depth 2. And if I still have time left after I'm done, I run again up to depth 3. If I still have time left, I run up to depth 4. And just like we had when we tried to combine the best of breadth-first and depth-first search through iterative deepening
1:11:27
and where the last search really takes all the time because it's the next level in a tree which is much larger than anything you've seen before, same thing here. So very quickly, the shallow depths and you keep taking more and more time for next one, next one. But if at some time in that process your clock runs out, you have the solution from the previous search to tell you what to do.
1:11:50
OK, let's take a look at this in action. So demo 6-- we run depth-limited minimax here or alpha-beta. It'll give the same result. Depth 2.
1:12:09
This is the behavior we get. What's going on here? Why does it keep thrashing back and forth? Well, let's think about this.
1:12:21
We have Pac-Man in this world. Two options-- left or right. Then only one option left, two options left. In our scoring, this would be a--
1:12:35
let's see. 8 plus 10 for one dot, negative 2 for two time steps. This would be a--
1:12:45
negative 2. And this would be also a 8.
1:12:56
So what happens here is that there are two options that are equally good. Going to the left or to the right is equally good. It doesn't really distinguish, breaks ties, and happens to go to the right. Then once it's here, it's effectively in a symmetric situation. Happens to break ties the other way, go to the left, keeps going back and forth. Because what is it doing? It's solving a new type of game. It's not solving the original game. It's solving the game, if I look 2 ahead,
1:13:20
what is the best thing to do as my first move? And if you only get to look 2 ahead, the best you can do is collect the food pellet. And it doesn't matter which direction you start. You can collect the food pellet in the next time step as needed. So that's the problem here. Our evaluation function by just looking at the score after two steps is not very indicative of how good that situation is. So maybe we need to use something better. So if we look at it, this situation
1:13:46
versus this situation, well, the one on the left is clearly better, because you already made progress getting to the next one. So maybe we should get a bonus here, a plus 1 or something, for getting already closer to the next one. Now we have a 8 plus 1 here. This branch gives us 9. The other one gives us 8. And we will go that way. So this is one of the things you might see in your own agents too. If your evaluation function is not good enough, doesn't give enough signal, and you only
1:14:15
look that deep, you might get weird behaviors that are not what you're hoping for. But you can solve it by having a better evaluation function that better evaluates how good a situation is. Don't just use the score in the game. Use something smarter. So here's what it looks like when fixed.
1:14:37
And it clears the board effectively. So what are these evaluation functions in practice? Imagine you're building one for the game of chess. We just heard that you can only go 8 deep. After 8 deep, usually the game's not over yet. How are you going to evaluate the board situation? Well, you might have heard things like the queen is worth a lot. Maybe a rook is worth something. A bishop is worth something. And maybe you take a weighted sum of the quality scores of each of the pieces
1:15:05
that you have left minus some weighted sum of the quality score of the pieces the opponent has left. But maybe you also have something about quality of the mobility on the board and so forth. So you come up with some way of evaluating the quality of the situation. And however good you make this will drastically affect how well your agent plays the game, because that is what it's going to use to evaluate what to do until you're very close to the end of the game, where you can search all
1:15:33
the way till the end and use the actual outcome of the game. So a lot of thinking can go into this. Also, often machine learning can go into this to learn what are good or bad positions to be in. For example, for Pac-Man, let's say you design an evaluation function. You're in this situation here. You might say, oh, I have an evaluation function. You run it on the situation. You get a number back. Then you can sanity check. Now here is another situation-- better or worse?
1:16:01
Well, this might look worse. If you think this is worse, you can check your evaluation function to see if indeed it gives this a worse score. If it doesn't, then maybe you should change your evaluation function or change your intuition and conclude that maybe this is better. How about this? Maybe even worse, because you're getting cornered more by the ghosts, getting closer to dead-ends than you were before. How about this? Even worse. Even worse.
1:16:30
And so you want to have a few sample situations for which you evaluate your evaluation function and inspect that indeed it gives you good numbers back. So now we're going to look at it from the perspective of the ghosts. So the ghosts also run minimax. They're just the opposite player. Here's what you get with ghosts running minimax.
1:16:57
They can't think all the way till the end of the game. So they use an evaluation function. The evaluation function says getting closer to Pac-Man is good. But then at the end, something else happens. Why does the behavior change at the end? Let's look at this again.
1:17:11
What's happening here? You evaluate based on evaluation function. You can't get to the end of the game in your search. Evaluation function says close to Pac-Man is good. But then you're at a point where you can get to the end of the game, which once you realize that this is how you can finish up the game and that's what you're going to do.
1:17:31
Here's a zoomed-in version.
1:17:37
Even more difficult situation. So the ghosts initially will just try to follow Pac-Man. But when they can look till the end of the game, they'll change their strategy, and flank, and win.
1:17:52
Depth matters. The deeper you can look by being fast at computing things, the better your evaluations will be. Your evaluation function will typically be better closer to the end of the game. There's a trade-off here. If you spend a lot of time on your evaluation function computationally, you'll have less time to run search, just like in A*. If your heuristic function is very expensive, then you don't have as much time to run the search.
1:18:17
What does limited depth do to you? Here is a limited-depth execution. Pac-Man-- well, execution's also probably the right way to phrase the outcome. Pac-Man's looking only 2 ahead. What happens?
1:18:35
Doesn't know what to do. Gets eaten. But what if Pac-Man can look much-- oh, wrong one. This one is unsolvable.
1:18:48
What if you look much further ahead? What if you can look 10 steps ahead? What can you do? You can actually anticipate that once blue chooses which way to go, they'll keep going that way. So if you can just hold off-- rather than running away from the red ghost, run towards it to hold off and gain time to see where blue is headed, and then choose where you go-- you can actually win this game. And so this is an example of looking further ahead,
1:19:15
giving you the edge compared to an agent that doesn't look nearly as far ahead. One thing you might wonder-- are there any synergies between what we've seen in terms of evaluation functions in alpha-beta pruning? We've looked at them as two orthogonal things. Evaluation function is a way to call a node a terminal node effectively rather than keep searching. Alpha-beta is a way to skip parts of the tree. Well, the amount of pruning you get in alpha-beta depends on the expansion ordering.
1:19:44
The evaluation function can give you guidance about what to expand first. We said that if you find good options first, then you get to prune more. Well, the evaluation function for your successor nodes can tell you which successor nodes are more promising for you and which ones are less promising. You can go to the more promising ones first and that way increase the amount of pruning you get in alpha-beta pruning.
1:20:10
Another thing that's happening is the value of a min node will keep going down. Once a value of a min node is lower than a better option available to max on the path to the root, you can stop. Here's an alternative how to decide to stop. If you have an evaluation function that is a bound-- you say, I evaluate this node. And I know that the value of this node is this much or less. And if the evaluation function is quick, you can quickly evaluate whether you get a certain value
1:20:41
or less at a specific node. That is enough information to potentially already prune. So rather than going down your first child and hope you find something that is promising that allows you to prune, your evaluation function, if it's a bound in the right direction, will also allow you to already prune. I strongly encourage you to think about these two ideas a little bit on your own time, because I think if you fully understand what's going on here, that means you have
1:21:07
a lot of the intuition in place of everything we covered in this lecture. See you next time, and we'll cover uncertainty. [SIDE CONVERSATION]
1:21:28
[NO AUDIO]
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat