Harvard CS50’s Artificial Intelligence with Python – Full University Course

0:00 This course from Harvard University explores the concepts and algorithms at the foundation of modern artificial intelligence, diving into the ideas that give rise to technologies like game-playing engines, handwriting recognition, and machine translation. You'll gain exposure to the theory

0:21 behind graph search algorithms, classification, optimization, reinforcement learning, and other topics in artificial intelligence and machine learning. Brian Yu teaches this course. Hello, world. This is CS50, and this is an introduction to artificial intelligence with

0:57 Python with CS50's own Brian Yu. This course picks up where CS50 itself leaves off and explores the concepts and algorithms at the foundation of modern AI. We'll start with a look at how AI can search for solutions to problems, whether those problems are learning how to play a game or trying

1:13 to find driving directions to a destination. We'll then look at how AI can represent information, both knowledge that our AI is certain about, but also information and events about which our AI might be uncertain, learning how to represent that information, but more importantly, how to use that information to draw inferences and new conclusions as well.

1:30 We'll explore how AI can solve various types of optimization problems, trying to maximize profits or minimize costs or satisfy some other constraints before turning our attention to the fast-growing field of machine learning, where we won't tell our AI exactly how to solve a problem, but instead,

1:45 give our AI access to data and experiences so that our AI can learn on its own how to perform these tasks. In particular, we'll look at neural networks, one of the most popular tools in modern machine learning, inspired by the way that human brains learn and reason as well before finally taking a look at the world of natural language processing

2:03 so that it's not just us humans learning to learn how artificial intelligence is able to speak, but also AI learning how to understand and interpret human language as well. We'll explore these ideas and algorithms, and along the way, give you the opportunity to build your own AI programs to implement all of this and more.

2:20 This is CS50. All right.

2:45 Welcome, everyone, to an introduction to artificial intelligence with Python. My name is Brian Yu, and in this class, we'll explore some of the ideas and techniques and algorithms that are at the foundation of artificial intelligence. Now, artificial intelligence covers a wide variety of types of techniques.

3:00 Anytime you see a computer do something that appears to be intelligent or rational in some way, like recognizing someone's face in a photo, or being able to play a game better than people can, or being able to understand human language when we talk to our phones and they understand what we mean and are able to respond back to us,

3:16 these are all examples of AI, or artificial intelligence. And in this class, we'll explore some of the ideas that make that AI possible. So we'll begin our conversations with search, the problem of we have an AI, and we would like the AI to be able to search for solutions to some kind of problem,

3:32 no matter what that problem might be. Whether it's trying to get driving directions from point A to point B, or trying to figure out how to play a game, given a tic-tac-toe game, for example, figuring out what move it ought to make. After that, we'll take a look at knowledge. Ideally, we want our AI to be able to know information,

3:49 to be able to represent that information, and more importantly, to be able to draw inferences from that information, to be able to use the information it knows and draw additional conclusions. So we'll talk about how AI can be programmed in order to do just that. Then we'll explore the topic of uncertainty,

4:04 talking about ideas of what happens if a computer isn't sure about a fact, but maybe is only sure with a certain probability. So we'll talk about some of the ideas behind probability, and how computers can begin to deal with uncertain events in order to be a little bit more intelligent in that sense as well.

4:21 After that, we'll turn our attention to optimization, problems of when the computer is trying to optimize for some sort of goal, especially in a situation where there might be multiple ways that a computer might solve a problem, but we're looking for a better way, or potentially the best way, if that's at all possible.

4:37 Then we'll take a look at machine learning, or learning more generally, and looking at how, when we have access to data, our computers can be programmed to be quite intelligent by learning from data and learning from experience, being able to perform a task better and better based on greater access to data.

4:51 So your email, for example, where your email inbox somehow knows which of your emails are good emails and which of your emails are spam. These are all examples of computers being able to learn from past experiences and past data. We'll take a look, too, at how computers are able to draw inspiration from human intelligence,

5:08 looking at the structure of the human brain, and how neural networks can be a computer analog to that sort of idea, and how, by taking advantage of a certain type of structure of a computer program, we can write neural networks that are able to perform tasks very, very effectively.

5:22 And then finally, we'll turn our attention to language, not programming languages, but human languages that we speak every day. And taking a look at the challenges that come about as a computer tries to understand natural language, and how it is some of the natural language processing that occurs in modern artificial intelligence can actually

5:39 work. But today, we'll begin our conversation with search, this problem of trying to figure out what to do when we have some sort of situation that the computer is in, some sort of environment that an agent is in, so to speak, and we would like for that agent to be able to somehow look for a solution to that problem.

5:56 Now, these problems can come in any number of different types of formats. One example, for instance, might be something like this classic 15 puzzle with the sliding tiles that you might have seen. Where you're trying to slide the tiles in order to make sure that all the numbers line up in order.

6:09 This is an example of what you might call a search problem. The 15 puzzle begins in an initially mixed up state, and we need some way of finding moves to make in order to return the puzzle to its solved state. But there are similar problems that you can frame in other ways. Trying to find your way through a maze, for example,

6:26 is another example of a search problem. You begin in one place, you have some goal of where you're trying to get to, and you need to figure out the correct sequence of actions that will take you from that initial state to the goal. And while this is a little bit abstract, any time

6:39 we talk about maze solving in this class, you can translate it to something a little more real world. Something like driving directions. If you ever wonder how Google Maps is able to figure out what is the best way for you to get from point A to point B, and what turns to make at what time,

6:52 depending on traffic, for example, it's often some sort of search algorithm. You have an AI that is trying to get from an initial position to some sort of goal by taking some sequence of actions. So we'll start our conversations today by thinking about these types of search problems and what

7:08 goes in to solving a search problem like this in order for an AI to be able to find a good solution. In order to do so, though, we're going to need to introduce a little bit of terminology, some of which I've already used. But the first term we'll need to think about is an agent.

7:22 An agent is just some entity that perceives its environment. It somehow is able to perceive the things around it and act on that environment in some way. So in the case of the driving directions, your agent might be some representation of a car that is trying to figure out what actions to take in order

7:37 to arrive at a destination. In the case of the 15 puzzle with the sliding tiles, the agent might be the AI or the person that is trying to solve that puzzle to try and figure out what tiles to move in order to get to that solution. Next, we introduce the idea of a state. A state is just some configuration of the agent in its environment.

7:57 So in the 15 puzzle, for example, any state might be any one of these three, for example. A state is just some configuration of the tiles. And each of these states is different and is going to require a slightly different solution. A different sequence of actions will be needed in each one of these

8:11 in order to get from this initial state to the goal, which is where we're trying to get. So the initial state, then, what is that? The initial state is just the state where the agent begins. It is one such state where we're going to start from. And this is going to be the starting point for our search algorithm,

8:27 so to speak. We're going to begin with this initial state and then start to reason about it, to think about what actions might we apply to that initial state in order to figure out how to get from the beginning to the end, from the initial position to whatever our goal happens to be.

8:42 And how do we make our way from that initial position to the goal? Well, ultimately, it's via taking actions. Actions are just choices that we can make in any given state. And in AI, we're always going to try to formalize these ideas a little bit more precisely, such that we could program them a little bit more

8:57 mathematically, so to speak. So this will be a recurring theme. And we can more precisely define actions as a function. We're going to effectively define a function called actions that takes an input, s, where s is going to be some state that exists inside of our environment. And actions of s is going to take the state as input and return as output

9:18 the set of all actions that can be executed in that state. And so it's possible that some actions are only valid in certain states and not in other states. And we'll see examples of that soon, too. So in the case of the 15 puzzle, for example, there are generally going to be four possible actions that we can do most of

9:36 the time. We can slide a tile to the right, slide a tile to the left, slide a tile up, or slide a tile down, for example. And those are going to be the actions that are available to us. So somehow our AI, our program, needs some encoding of the state, which is often going to be in some numerical format,

9:52 and some encoding of these actions. But it also needs some encoding of the relationship between these things. How do the states and actions relate to one another? And in order to do that, we'll introduce to our AI a transition model, which will be a description of what state we get after we perform some available

10:08 action in some other state. And again, we can be a little bit more precise about this, define this transition model a little bit more formally, again, as a function. The function is going to be a function called result that this time takes two inputs. Input number one is s, some state.

10:25 And input number two is a, some action. And the output of this function result is it is going to give us the state that we get after we perform action a in state s. So let's take a look at an example to see more precisely what this actually means. Here is an example of a state, of the 15 puzzle, for example.

10:43 And here is an example of an action, sliding a tile to the right. What happens if we pass these as inputs to the result function? Again, the result function takes this board, this state, as its first input. And it takes an action as a second input. And of course, here, I'm describing things visually

10:59 so that you can see visually what the state is and what the action is. In a computer, you might represent one of these actions as just some number that represents the action. Or if you're familiar with enums that allow you to enumerate multiple possibilities, it might be something like that.

11:12 And this state might just be represented as an array or two-dimensional array of all of these numbers that exist. But here, we're going to show it visually just so you can see it. But when we take this state and this action, pass it into the result function, the output is a new state.

11:27 The state we get after we take a tile and slide it to the right, and this is the state we get as a result. If we had a different action and a different state, for example, and pass that into the result function, we'd get a different answer altogether. So the result function needs to take care

11:41 of figuring out how to take a state and take an action and get what results. And this is going to be our transition model that describes how it is that states and actions are related to each other. If we take this transition model and think about it more generally and across the entire problem, we can form what we might call a state space.

12:00 The set of all of the states we can get from the initial state via any sequence of actions, by taking 0 or 1 or 2 or more actions in addition to that, so we could draw a diagram that looks something like this, where every state is represented here by a game board, and there are arrows

12:16 that connect every state to every other state we can get to from that state. And the state space is much larger than what you see just here. This is just a sample of what the state space might actually look like. And in general, across many search problems, whether they're this particular 15 puzzle or driving directions or something else,

12:34 the state space is going to look something like this. We have individual states and arrows that are connecting them. And oftentimes, just for simplicity, we'll simplify our representation of this entire thing as a graph, some sequence of nodes and edges that connect nodes. But you can think of this more abstract representation

12:53 as the exact same idea. Each of these little circles or nodes is going to represent one of the states inside of our problem. And the arrows here represent the actions that we can take in any particular state, taking us from one particular state to another state, for example. All right.

13:11 So now we have this idea of nodes that are representing these states, actions that can take us from one state to another, and a transition model that defines what happens after we take a particular action. So the next step we need to figure out is how we know when the AI is done solving the problem.

13:26 The AI needs some way to know when it gets to the goal that it's found the goal. So the next thing we'll need to encode into our artificial intelligence is a goal test, some way to determine whether a given state is a goal state. In the case of something like driving directions, it might be pretty easy.

13:43 If you're in a state that corresponds to whatever the user typed in as their intended destination, well, then you know you're in a goal state. In the 15 puzzle, it might be checking the numbers to make sure they're all in ascending order. But the AI needs some way to encode whether or not

13:56 any state they happen to be in is a goal. And some problems might have one goal, like a maze where you have one initial position and one ending position, and that's the goal. In other more complex problems, you might imagine that there are multiple possible goals. That there are multiple ways to solve a problem,

14:11 and we might not care which one the computer finds, as long as it does find a particular goal. However, sometimes the computer doesn't just care about finding a goal, but finding a goal well, or one with a low cost. And it's for that reason that the last piece of terminology that we'll use to define these search problems

14:28 is something called a path cost. You might imagine that in the case of driving directions, it would be pretty annoying if I said I wanted directions from point A to point B, and the route that Google Maps gave me was a long route with lots of detours that were unnecessary that took longer

14:43 than it should have for me to get to that destination. And it's for that reason that when we're formulating search problems, we'll often give every path some sort of numerical cost, some number telling us how expensive it is to take this particular option, and then tell our AI that instead of just finding

14:59 a solution, some way of getting from the initial state to the goal, we'd really like to find one that minimizes this path cost. That is, less expensive, or takes less time, or minimizes some other numerical value. We can represent this graphically if we take a look at this graph again,

15:16 and imagine that each of these arrows, each of these actions that we can take from one state to another state, has some sort of number associated with it. That number being the path cost of this particular action, where some of the costs for any particular action might be more expensive than the cost for some other action, for example.

15:33 Although this will only happen in some sorts of problems. In other problems, we can simplify the diagram and just assume that the cost of any particular action is the same. And this is probably the case in something like the 15 puzzle, for example, where it doesn't really make a difference

15:48 whether I'm moving right or moving left. The only thing that matters is the total number of steps that I have to take to get from point A to point B. And each of those steps is of equal cost. We can just assume it's of some constant cost like one. And so this now forms the basis for what we might consider to be a search problem.

16:08 A search problem has some sort of initial state, some place where we begin, some sort of action that we can take or multiple actions that we can take in any given state. And it has a transition model. Some way of defining what happens when we go from one state and take one action, what state do we end up with as a result.

16:25 In addition to that, we need some goal test to know whether or not we've reached a goal. And then we need a path cost function that tells us for any particular path, by following some sequence of actions, how expensive is that path. What does its cost in terms of money or time or some other resource

16:41 that we are trying to minimize our usage of. And the goal ultimately is to find a solution. Where a solution in this case is just some sequence of actions that will take us from the initial state to the goal state. And ideally, we'd like to find not just any solution but the optimal solution, which is a solution that

16:59 has the lowest path cost among all of the possible solutions. And in some cases, there might be multiple optimal solutions. But an optimal solution just means that there is no way that we could have done better in terms of finding that solution. So now we've defined the problem. And now we need to begin to figure out how it

17:16 is that we're going to solve this kind of search problem. And in order to do so, you'll probably imagine that our computer is going to need to represent a whole bunch of data about this particular problem. We need to represent data about where we are in the problem. And we might need to be considering multiple different options at once.

17:32 And oftentimes, when we're trying to package a whole bunch of data related to a state together, we'll do so using a data structure that we're going to call a node. A node is a data structure that is just going to keep track of a variety of different values. And specifically, in the case of a search problem,

17:47 it's going to keep track of these four values in particular. Every node is going to keep track of a state, the state we're currently on. And every node is also going to keep track of a parent. A parent being the state before us or the node that we used in order to get to this current state.

18:03 And this is going to be relevant because eventually, once we reach the goal node, once we get to the end, we want to know what sequence of actions we use in order to get to that goal. And the way we'll know that is by looking at these parents to keep track of what led us to the goal and what led us to that state

18:20 and what led us to the state before that, so on and so forth, backtracking our way to the beginning so that we know the entire sequence of actions we needed in order to get from the beginning to the end. The node is also going to keep track of what action we took in order to get from the parent to the current state.

18:36 And the node is also going to keep track of a path cost. In other words, it's going to keep track of the number that represents how long it took to get from the initial state to the state that we currently happen to be at. And we'll see why this is relevant as we start to talk about some of the optimizations

18:52 that we can make in terms of these search problems more generally. So this is the data structure that we're going to use in order to solve the problem. And now let's talk about the approach. How might we actually begin to solve the problem? Well, as you might imagine, what we're going to do

19:06 is we're going to start at one particular state, and we're just going to explore from there. The intuition is that from a given state, we have multiple options that we could take, and we're going to explore those options. And once we explore those options, we'll find that more options than that are going to make themselves available.

19:22 And we're going to consider all of the available options to be stored inside of a single data structure that we'll call the frontier. The frontier is going to represent all of the things that we could explore next that we haven't yet explored or visited. So in our approach, we're going to begin the search algorithm

19:39 by starting with a frontier that just contains one state. The frontier is going to contain the initial state, because at the beginning, that's the only state we know about. That is the only state that exists. And then our search algorithm is effectively going to follow a loop. We're going to repeat some process again and again and again.

19:57 The first thing we're going to do is if the frontier is empty, then there's no solution. And we can report that there is no way to get to the goal. And that's certainly possible. There are certain types of problems that an AI might try to explore and realize that there is no way to solve that problem.

20:13 And that's useful information for humans to know as well. So if ever the frontier is empty, that means there's nothing left to explore. And we haven't yet found a solution, so there is no solution. There's nothing left to explore. Otherwise, what we'll do is we'll remove a node from the frontier.

20:29 So right now at the beginning, the frontier just contains one node representing the initial state. But over time, the frontier might grow. It might contain multiple states. And so here, we're just going to remove a single node from that frontier. If that node happens to be a goal, then we found a solution.

20:45 So we remove a node from the frontier and ask ourselves, is this the goal? And we do that by applying the goal test that we talked about earlier, asking if we're at the destination. Or asking if all the numbers of the 15 puzzle happen to be in order. So if the node contains the goal, we found a solution.

21:00 Great. We're done. And otherwise, what we'll need to do is we'll need to expand the node. And this is a term of art in artificial intelligence. To expand the node just means to look at all of the neighbors of that node. In other words, consider all of the possible actions that I could take from the state that this node is representing

21:19 and what nodes could I get to from there. We're going to take all of those nodes, the next nodes that I can get to from this current one I'm looking at, and add those to the frontier. And then we'll repeat this process. So at a very high level, the idea is we start with a frontier that contains the initial state.

21:35 And we're constantly removing a node from the frontier, looking at where we can get to next and adding those nodes to the frontier, repeating this process over and over until either we remove a node from the frontier and it contains a goal, meaning we've solved the problem, or we run into a situation

21:51 where the frontier is empty, at which point we're left with no solution. So let's actually try and take the pseudocode, put it into practice by taking a look at an example of a sample search problem. So right here, I have a sample graph. A is connected to B via this action. B is connected to nodes C and D. C is connected to E. D is connected to F.

22:11 And what I'd like to do is have my AI find a path from A to E. We want to get from this initial state to this goal state. So how are we going to do that? Well, we're going to start with a frontier that contains the initial state. This is going to represent our frontier. So our frontier initially will just contain

22:29 A, that initial state where we're going to begin. And now we'll repeat this process. If the frontier is empty, no solution. That's not a problem, because the frontier is not empty. So we'll remove a node from the frontier as the one to consider next. There's only one node in the frontier.

22:44 So we'll go ahead and remove it from the frontier. But now A, this initial node, this is the node we're currently considering. We follow the next step. We ask ourselves, is this node the goal? No, it's not. A is not the goal. E is the goal. So we don't return the solution. So instead, we go to this last step, expand the node,

23:03 and add the resulting nodes to the frontier. What does that mean? Well, it means take this state A and consider where we could get to next. And after A, what we could get to next is only B. So that's what we get when we expand A. We find B. And we add B to the frontier. And now B is in the frontier.

23:20 And we repeat the process again. We say, all right, the frontier is not empty. So let's remove B from the frontier. B is now the node that we're considering. We ask ourselves, is B the goal? No, it's not. So we go ahead and expand B and add its resulting nodes to the frontier. What happens when we expand B?

23:37 In other words, what nodes can we get to from B? Well, we can get to C and D. So we'll go ahead and add C and D from the frontier. And now we have two nodes in the frontier, C and D. And we repeat the process again. We remove a node from the frontier. For now, I'll do so arbitrarily just by picking C.

23:53 We'll see why later, how choosing which node you remove from the frontier is actually quite an important part of the algorithm. But for now, I'll arbitrarily remove C, say it's not the goal. So we'll add E, the next one, to the frontier. Then let's say I remove E from the frontier.

24:07 And now I check I'm currently looking at state E. Is it a goal state? It is, because I'm trying to find a path from A to E. So I would return the goal. And that now would be the solution, that I'm now able to return the solution. And I have found a path from A to E. So this is the general idea, the general approach of this search algorithm,

24:27 to follow these steps, constantly removing nodes from the frontier, until we're able to find a solution. So the next question you might reasonably ask is, what could go wrong here? What are the potential problems with an approach like this? And here's one example of a problem that could arise from this sort of approach.

24:43 Imagine this same graph, same as before, with one change. The change being now, instead of just an arrow from A to B, we also have an arrow from B to A, meaning we can go in both directions. And this is true in something like the 15 puzzle, where when I slide a tile to the right, I could then slide a tile to the left

25:01 to get back to the original position. I could go back and forth between A and B. And that's what these double arrows symbolize, the idea that from one state, I can get to another, and then I can get back. And that's true in many search problems. What's going to happen if I try to apply the same approach now?

25:16 Well, I'll begin with A, same as before. And I'll remove A from the frontier. And then I'll consider where I can get to from A. And after A, the only place I can get to is B. So B goes into the frontier. Then I'll say, all right, let's take a look at B. That's the only thing left in the frontier.

25:32 Where can I get to from B? Before, it was just C and D. But now, because of that reverse arrow, I can get to A or C or D. So all three, A, C, and D, all of those now go into the frontier. They are places I can get to from B. And now I remove one from the frontier. And maybe I'm unlucky, and maybe I pick A. And now I'm looking at A again.

25:53 And I consider, where can I get to from A? And from A, well, I can get to B. And now we start to see the problem. But if I'm not careful, I go from A to B, and then back to A, and then to B again. And I could be going in this infinite loop, where I never make any progress, because I'm constantly just going back and forth between two states

26:09 that I've already seen. So what is the solution to this? We need some way to deal with this problem. And the way that we can deal with this problem is by somehow keeping track of what we've already explored. And the logic is going to be, well, if we've already explored the state,

26:23 there's no reason to go back to it. Once we've explored a state, don't go back to it. Don't bother adding it to the frontier. There's no need to. So here's going to be our revised approach, a better way to approach this sort of search problem. And it's going to look very similar, just with a couple of modifications.

26:40 We'll start with a frontier that contains the initial state, same as before. But now we'll start with another data structure, which will just be a set of nodes that we've already explored. So what are the states we've explored? Initially, it's empty. We have an empty explored set.

26:55 And now we repeat. If the frontier is empty, no solution, same as before. We remove a node from the frontier. We check to see if it's a goal state, return the solution. None of this is any different so far. But now what we're going to do is we're going to add the node to the explored state.

27:12 So if it happens to be the case that we remove a node from the frontier and it's not the goal, we'll add it to the explored set so that we know we've already explored it. We don't need to go back to it again if it happens to come up later. And then the final step, we expand the node

27:26 and we add the resulting nodes to the frontier. But before, we just always added the resulting nodes to the frontier. We're going to be a little clever about it this time. We're only going to add the nodes to the frontier if they aren't already in the frontier and if they aren't already

27:41 in the explored set. So we'll check both the frontier and the explored set, make sure that the node isn't already in one of those two. And so long as it isn't, then we'll go ahead and add it to the frontier, but not otherwise. And so that revised approach is ultimately what's going to help make sure that we don't go back and forth between two

27:59 nodes. Now, the one point that I've kind of glossed over here so far is this step here, removing a node from the frontier. Before, I just chose arbitrarily. Like, let's just remove a node and that's it. But it turns out it's actually quite important how we decide to structure our frontier, how we add and how we remove our nodes.

28:18 The frontier is a data structure and we need to make a choice about in what order are we going to be removing elements. And one of the simplest data structures for adding and removing elements is something called a stack. And a stack is a data structure that is a last in, first out data type, which

28:34 means the last thing that I add to the frontier is going to be the first thing that I remove from the frontier. So the most recent thing to go into the stack or the frontier in this case is going to be the node that I explore. So let's see what happens if I apply this stack-based approach to something

28:51 like this problem, finding a path from A to E. What's going to happen? Well, again, we'll start with A and we'll say, all right, let's go ahead and look at A first. And then notice this time, we've added A to the explored set. A is something we've now explored. We have this data structure that's keeping track.

29:09 We then say from A, we can get to B. And all right, from B, what can we do? Well, from B, we can explore B and get to both C and D. So we added C and then D. So now, when we explore a node, we're going to treat the frontier as a stack, last in, first out. D was the last one to come in.

29:28 So we'll go ahead and explore that next and say, all right, where can we get to from D? Well, we can get to F. And so all right, we'll put F into the frontier. And now, because the frontier is a stack, F is the most recent thing that's gone in the stack. So F is what we'll explore next.

29:44 We'll explore F and say, all right, where can we get to from F? Well, we can't get anywhere, so nothing gets added to the frontier. So now, what was the new most recent thing added to the frontier? Well, it's now C, the only thing left in the frontier. We'll explore that from which we can see, all right, from C, we can get to E.

30:00 So E goes into the frontier. And then we say, all right, let's look at E. And E is now the solution. And now, we've solved the problem. So when we treat the frontier like a stack, a last in, first out data structure, that's the result we get. We go from A to B to D to F. And then we sort of backed up and went down to C

30:19 and then E. And it's important to get a visual sense for how this algorithm is working. We went very deep in this search tree, so to speak, all the way until the bottom where we hit a dead end. And then we effectively backed up and explored this other route that we didn't try before.

30:34 And it's this going very deep in the search tree idea, this way the algorithm ends up working when we use a stack that we call this version of the algorithm depth first search. Depth first search is the search algorithm where we always explore the deepest node in the frontier. We keep going deeper and deeper through our search tree.

30:53 And then if we hit a dead end, we back up and we try something else instead. But depth first search is just one of the possible search options that we could use. It turns out that there's another algorithm called breadth first search, which behaves very similarly to depth first search with one difference.

31:09 Instead of always exploring the deepest node in the search tree, the way the depth first search does, breadth first search is always going to explore the shallowest node in the frontier. So what does that mean? Well, it means that instead of using a stack which depth first search or DFS

31:24 used, where the most recent item added to the frontier is the one we'll explore next, in breadth first search or BFS, we'll instead use a queue, where a queue is a first in first out data type, where the very first thing we add to the frontier is the first one we'll explore and they effectively form a line or a queue,

31:44 where the earlier you arrive in the frontier, the earlier you get explored. So what would that mean for the same exact problem, finding a path from A to E? Well, we start with A, same as before, then we'll go ahead and have explored A and say, where can we get to from A? Well, from A, we can get to B, same as before.

32:02 From B, same as before, we can get to C and D. So C and D get added to the frontier. This time, though, we added C to the frontier before D. So we'll explore C first. So C gets explored. And from C, where can we get to? Well, we can get to E. So E gets added to the frontier. But because D was explored before E, we'll look at D next.

32:24 So we'll explore D and say, where can we get to from D? We can get to F. And only then will we say, all right, now we can get to E. And so what breadth first search or BFS did is we started here, we looked at both C and D, and then we looked at E. Effectively, we're looking at things one away from the initial state,

32:43 then two away from the initial state, and only then, things that are three away from the initial state, unlike depth first search, which just went as deep as possible into the search tree until it hit a dead end and then ultimately had to back up. So these now are two different search algorithms

32:59 that we could apply in order to try and solve a problem. And let's take a look at how these would actually work in practice with something like maze solving, for example. So here's an example of a maze. These empty cells represent places where our agent can move. These darkened gray cells represent walls that the agent can't pass through.

33:17 And ultimately, our agent, our AI, is going to try to find a way to get from position A to position B via some sequence of actions, where those actions are left, right, up, and down. What will depth first search do in this case? Well, depth first search will just follow one path.

33:34 If it reaches a fork in the road where it has multiple different options, depth first search is just, in this case, going to choose one. That doesn't a real preference. But it's going to keep following one until it hits a dead end. And when it hits a dead end, depth first search effectively

33:48 goes back to the last decision point and tries the other path, fully exhausting this entire path. And when it realizes that, OK, the goal is not here, then it turns its attention to this path. It goes as deep as possible. When it hits a dead end, it backs up and then tries this other path,

34:04 keeps going as deep as possible down one particular path. And when it realizes that that's a dead end, then it'll back up, and then ultimately find its way to the goal. And maybe you got lucky, and maybe you made a different choice earlier on. But ultimately, this is how depth first search is going to work.

34:20 It's going to keep following until it hits a dead end. And when it hits a dead end, it backs up and looks for a different solution. And so one thing you might reasonably ask is, is this algorithm always going to work? Will it always actually find a way to get from the initial state?

34:33 To the goal. And it turns out that as long as our maze is finite, as long as there are only finitely many spaces where we can travel, then, yes, depth first search is going to find a solution. Because eventually, it'll just explore everything. If the maze happens to be infinite and there's an infinite state space,

34:50 which does exist in certain types of problems, then it's a slightly different story. But as long as our maze has finitely many squares, we're going to find a solution. The next question, though, that we want to ask is, is it going to be a good solution? Is it the optimal solution that we can find?

35:05 And the answer there is not necessarily. And let's take a look at an example of that. In this maze, for example, we're again trying to find our way from A to B. And you notice here there are multiple possible solutions. We could go this way or we could go up in order to make our way from A to B.

35:22 Now, if we're lucky, depth first search will choose this way and get to B. But there's no reason necessarily why depth first search would choose between going up or going to the right. It's sort of an arbitrary decision point because both are going to be added to the frontier. And ultimately, if we get unlucky, depth first search

35:39 might choose to explore this path first because it's just a random choice at this point. It'll explore, explore, explore. And it'll eventually find the goal, this particular path, when in actuality there was a better path. There was a more optimal solution that used fewer steps, assuming we're measuring the cost of a solution based on the number of steps

35:58 that we need to take. So depth first search, if we're unlucky, might end up not finding the best solution when a better solution is available. So that's DFS, depth first search. How does BFS, or breadth first search, compare? How would it work in this particular situation? Well, the algorithm is going to look very different visually

36:18 in terms of how BFS explores. Because BFS looks at shallower nodes first, the idea is going to be, BFS will first look at all of the nodes that are one away from the initial state. Look here and look here, for example, just at the two nodes that are immediately next to this initial state.

36:36 Then it'll explore nodes that are two away, looking at this state and that state, for example. Then it'll explore nodes that are three away, this state and that state. Whereas depth first search just picked one path and kept following it, breadth first search, on the other hand, is taking the option of exploring all of the possible paths

36:53 as kind of at the same time bouncing back between them, looking deeper and deeper at each one, but making sure to explore the shallower ones or the ones that are closer to the initial state earlier. So we'll keep following this pattern, looking at things that are four away, looking at things that are five away, looking at things that are six away,

37:11 until eventually we make our way to the goal. And in this case, it's true we had to explore some states that ultimately didn't lead us anywhere, but the path that we found to the goal was the optimal path. This is the shortest way that we could get to the goal. And so what might happen then in a larger maze?

37:29 Well, let's take a look at something like this and how breadth first search is going to behave. Well, breadth first search, again, we'll just keep following the states until it receives a decision point. It could go either left or right. And while DFS just picked one and kept following that until it hit a dead end,

37:45 BFS, on the other hand, will explore both. It'll say look at this node, then this node, and it'll look at this node, then that node. So on and so forth. And when it hits a decision point here, rather than pick one left or two right and explore that path, it'll again explore both,

38:01 alternating between them, going deeper and deeper. We'll explore here, and then maybe here and here, and then keep going. Explore here and slowly make our way, you can visually see, further and further out. Once we get to this decision point, we'll explore both up and down until ultimately we make our way to the goal.

38:22 And what you'll notice is, yes, breadth first search did find our way from A to B by following this particular path, but it needed to explore a lot of states in order to do so. And so we see some trade offs here between DFS and BFS, that in DFS, there may be some cases where there is some memory savings

38:39 as compared to a breadth first approach, where breadth first search in this case had to explore a lot of states. But maybe that won't always be the case. So now let's actually turn our attention to some code and look at the code that we could actually write in order to implement something like depth first search or breadth

38:56 first search in the context of solving a maze, for example. So I'll go ahead and go into my terminal. And what I have here inside of maze.py is an implementation of this same idea of maze solving. I've defined a class called node that in this case is keeping track of the state, the parent, in other words,

39:16 the state before the state, and the action. In this case, we're not keeping track of the path cost because we can calculate the cost of the path at the end after we found our way from the initial state to the goal. In addition to this, I've defined a class called a stack frontier.

39:32 And if unfamiliar with a class, a class is a way for me to define a way to generate objects in Python. It refers to an idea of object oriented programming, where the idea here is that I would like to create an object that is able to store all of my frontier data. And I would like to have functions, otherwise known

39:49 as methods, on that object that I can use to manipulate the object. And so what's going on here, if unfamiliar with the syntax, is I have a function that initially creates a frontier that I'm going to represent using a list. And initially, my frontier is represented by the empty list.

40:06 There's nothing in my frontier to begin with. I have an add function that adds something to the frontier as by appending it to the end of the list. I have a function that checks if the frontier contains a particular state. I have an empty function that checks if the frontier is empty.

40:22 If the frontier is empty, that just means the length of the frontier is 0. And then I have a function for removing something from the frontier. I can't remove something from the frontier if the frontier is empty, so I check for that first. But otherwise, if the frontier isn't empty,

40:37 recall that I'm implementing this frontier as a stack, a last in first out data structure, which means the last thing I add to the frontier, in other words, the last thing in the list, is the item that I should remove from this frontier. So what you'll see here is I have removed the last item of a list.

40:56 And if you index into a Python list with negative 1, that gets you the last item in the list. Since 0 is the first item, negative 1 kind of wraps around and gets you to the last item in the list. So we give that the node. We call that node. We update the frontier here on line 28 to say,

41:13 go ahead and remove that node that you just removed from the frontier. And then we return the node as a result. So this class here effectively implements the idea of a frontier. It gives me a way to add something to a frontier and a way to remove something from the frontier as a stack.

41:29 I've also, just for good measure, implemented an alternative version of the same thing called a queue frontier, which in parentheses you'll see here, it inherits from a stack frontier, meaning it's going to do all the same things that the stack frontier did, except the way we remove a node from the frontier

41:46 is going to be slightly different. Instead of removing from the end of the list the way we would in a stack, we're instead going to remove from the beginning of the list. Self.frontier 0 will get me the first node in the frontier, the first one that was added, and that is going to be the one

42:00 that we return in the case of a queue. Then under here, I have a definition of a class called maze. This is going to handle the process of taking a sequence, a maze-like text file, and figuring out how to solve it. So it will take as input a text file that looks something like this,

42:17 for example, where we see hash marks that are here representing walls, and I have the character A representing the starting position and the character B representing the ending position. And you can take a look at the code for parsing this text file right now. That's the less interesting part.

42:32 The more interesting part is this solve function here, the solve function is going to figure out how to actually get from point A to point B. And here we see an implementation of the exact same idea we saw from a moment ago. We're going to keep track of how many states we've explored,

42:48 just so we can report that data later. But I start with a node that represents just the start state. And I start with a frontier that, in this case, is a stack frontier. And given that I'm treating my frontier as a stack, you might imagine that the algorithm I'm using here is now depth-first search,

43:06 because depth-first search, or DFS, uses a stack as its data structure. And initially, this frontier is just going to contain the start state. We initialize an explored set that initially is empty. There's nothing we've explored so far. And now here's our loop, that notion of repeating something again and again.

43:26 First, we check if the frontier is empty by calling that empty function that we saw the implementation of a moment ago. And if the frontier is indeed empty, we'll go ahead and raise an exception, or a Python error, to say, sorry, there is no solution to this problem. Otherwise, we'll go ahead and remove a node from the frontier

43:45 as by calling frontier.remove and update the number of states we've explored, because now we've explored one additional state. So we say self.numexplored plus equals 1, adding 1 to the number of states we've explored. Once we remove a node from the frontier, recall that the next step is to see whether or not

44:02 it's the goal, the goal test. And in the case of the maze, the goal is pretty easy. I check to see whether the state of the node is equal to the goal. Initially, when I set up the maze, I set up this value called goal, which is a property of the maze, so I can just check to see if the node is actually the goal.

44:19 And if it is the goal, then what I want to do is backtrack my way towards figuring out what actions I took in order to get to this goal. And how do I do that? We'll recall that every node stores its parent, the node that came before it that we used to get to this node, and also the action used in order to get

44:37 there. So I can create this loop where I'm constantly just looking at the parent of every node and keeping track for all of the parents what action I took to get from the parent to this current node. So this loop is going to keep repeating this process of looking through all of the parent nodes

44:52 until we get back to the initial state, which has no parent, where node.parent is going to be equal to none. As I do so, I'm going to be building up the list of all of the actions that I'm following and the list of all the cells that are part of the solution. But I'll reverse them because when I build it up,

45:08 going from the goal back to the initial state and building the sequence of actions from the goal to the initial state, but I want to reverse them in order to get the sequence of actions from the initial state to the goal. And that is ultimately going to be the solution. So all of that happens if the current state is equal to the goal.

45:27 And otherwise, if it's not the goal, well, then I'll go ahead and add this state to the explored set to say, I've explored this state now. No need to go back to it if I come across it in the future. And then this logic here implements the idea of adding neighbors to the frontier.

45:43 I'm saying, look at all of my neighbors, and I implemented a function called neighbors that you can take a look at. And for each of those neighbors, I'm going to check, is the state already in the frontier? Is the state already in the explored set? And if it's not in either of those, then I'll go ahead and add this new child

45:59 node, this new node, to the frontier. So there's a fair amount of syntax here, but the key here is not to understand all the nuances of the syntax. So feel free to take a closer look at this file on your own to get a sense for how it is working. But the key is to see how this is an implementation

46:13 of the same pseudocode, the same idea that we were describing a moment ago on the screen when we were looking at the steps that we might follow in order to solve this kind of search problem. So now let's actually see this in action. I'll go ahead and run maze.py on maze1.txt, for example.

46:32 And what we'll see is here, we have a printout of what the maze initially looked like. And then here down below is after we've solved it. We had to explore 11 states in order to do it, and we found a path from A to B. And in this program, I just happened to generate a graphical representation of this as well.

46:48 So I can open up maze.png, which is generated by this program, that shows you where in the darker color here are the walls, red is the initial state, green is the goal, and yellow is the path that was followed. We found a path from the initial state to the goal. But now let's take a look at a more sophisticated maze

47:06 to see what might happen instead. Let's look now at maze2.txt. We're now here. We have a much larger maze. Again, we're trying to find our way from point A to point B. But now you'll imagine that depth-first search might not be so lucky. It might not get the goal on the first try.

47:22 It might have to follow one path, then backtrack and explore something else a little bit later. So let's try this. We'll run python maze.py of maze2.txt, this time trying on this other maze. And now, depth-first search is able to find a solution. Here, as indicated by the stars, is a way to get from A to B.

47:42 And we can represent this visually by opening up this maze. Here's what that maze looks like, and highlighted in yellow is the path that was found from the initial state to the goal. But how many states did we have to explore before we found that path? Well, recall that in my program, I was keeping

47:59 track of the number of states that we've explored so far. And so I can go back to the terminal and see that, all right, in order to solve this problem, we had to explore 399 different states. And in fact, if I make one small modification of the program and tell the program at the end when we output this image,

48:18 I added an argument called show explored. And if I set show explored equal to true and rerun this program, python maze.py, running it on maze2, and then I open the maze, what you'll see here is highlighted in red are all of the states that had to be explored to get from the initial state to the goal.

48:38 Depth-first search, or DFS, didn't find its way to the goal right away. It made a choice to first explore this direction. And when it explored this direction, it had to follow every conceivable path all the way to the very end, even this long and winding one, in order to realize that, you know what?

48:52 That's a dead end. And instead, the program needed to backtrack. After going this direction, it must have gone this direction. It got lucky here by just not choosing this path, but it got unlucky here, exploring this direction, exploring a bunch of states it didn't need to, and then likewise exploring

49:08 all of this top part of the graph when it probably didn't need to do that either. So all in all, depth-first search here really not performing optimally, or probably exploring more states than it needs to. It finds an optimal solution, the best path to the goal, but the number of states needed to explore in order to do so,

49:26 the number of steps I had to take, that was much higher. So let's compare. How would breadth-first search, or BFS, do on this exact same maze instead? And in order to do so, it's a very easy change. The algorithm for DFS and BFS is identical with the exception of what data structure we use to represent the frontier,

49:47 that in DFS, I used a stack frontier, last in, first out, whereas in BFS, I'm going to use a queue frontier, first in, first out, where the first thing I add to the frontier is the first thing that I remove. So I'll go back to the terminal, rerun this program on the same maze, and now you'll see that the number of states

50:09 we had to explore was only 77 as compared to almost 400 when we used depth-first search. And we can see exactly why. We can see what happened if we open up maze.png now and take a look. Again, yellow highlight is the solution that breadth-first search found, which incidentally is the same solution that depth-first search found.

50:29 They're both finding the best solution. But notice all the white unexplored cells. There was much fewer states that needed to be explored in order to make our way to the goal because breadth-first search operates a little more shallowly. It's exploring things that are close to the initial state

50:45 without exploring things that are further away. So if the goal is not too far away, then breadth-first search can actually behave quite effectively on a maze that looks a little something like this. Now, in this case, both BFS and DFS ended up finding the same solution, but that won't always be the case.

51:04 And in fact, let's take a look at one more example. For instance, maze3.txt. In maze3.txt, notice that here there are multiple ways that you could get from A to B. It's a relatively small maze, but let's look at what happens. If I use, and I'll go ahead and turn off show explored

51:22 so we just see the solution. If I use BFS, breadth-first search, to solve maze3.txt, well, then we find a solution, and if I open up the maze, here is the solution that we found. It is the optimal one. With just four steps, we can get from the initial state to what the goal happens to be.

51:43 But what happens if we tried to use depth-first search or DFS instead? Well, again, I'll go back up to my Q frontier, where Q frontier means that we're using breadth-first search, and I'll change it to a stack frontier, which means that now we'll be using depth-first search. I'll rerun pythonmaze.py, and now you'll see that we find the solution,

52:07 but it is not the optimal solution. This instead is what our algorithm finds, and maybe depth-first search would have found the solution. It's possible, but it's not guaranteed that if we just happen to be unlucky, if we choose this state instead of that state, then depth-first search might find a longer route

52:24 to get from the initial state to the goal. So we do see some trade-offs here, where depth-first search might not find the optimal solution. So at that point, it seems like breadth-first search is pretty good. Is that the best we can do, where it's going to find us the optimal solution,

52:39 and we don't have to worry about situations where we might end up finding a longer path to the solution than what actually exists? Where the goal is far away from the initial state, and we might have to take lots of steps in order to get from the initial state to the goal, what ended up happening

52:55 is that this algorithm, BFS, ended up exploring basically the entire graph, having to go through the entire maze in order to find its way from the initial state to the goal state. What we'd ultimately like is for our algorithm to be a little bit more intelligent. And now what would it mean for our algorithm to be a little bit more

53:14 intelligent in this case? Well, let's look back to where breadth-first search might have been able to make a different decision and consider human intuition in this process as well. What might a human do when solving this maze that is different than what BFS ultimately chose to do?

53:31 Well, the very first decision point that BFS made was right here, when it made five steps and ended up in a position where it had a fork in the row. It could either go left or it could go right. In these initial couple steps, there was no choice. There was only one action that could be taken from each of those states.

53:47 And so the search algorithm did the only thing that any search algorithm could do, which is keep following that state after the next state. But this decision point is where things get a little bit interesting. Depth-first search, that very first search algorithm we looked at, chose to say, let's pick one path and exhaust that path.

54:05 See if anything that way has the goal. And if not, then let's try the other way. Depth-first search took the alternative approach of saying, you know what, let's explore things that are shallow, close to us first. Look left and right, then back left and back right, so on and so forth,

54:20 alternating between our options in the hopes of finding something nearby. But ultimately, what might a human do if confronted with a situation like this of go left or go right? Well, a human might visually see that, all right, I'm trying to get to state b, which is way up there, and going right just feels like it's closer to the goal.

54:40 It feels like going right should be better than going left because I'm making progress towards getting to that goal. Now, of course, there are a couple of assumptions that I'm making here. I'm making the assumption that we can represent this grid as like a two-dimensional grid where I know the coordinates of everything.

54:55 I know that a is in coordinate 0, 0, and b is in some other coordinate pair, and I know what coordinate I'm at now. So I can calculate that, yeah, going this way, that is closer to the goal. And that might be a reasonable assumption for some types of search problems, but maybe not in others.

55:10 But for now, we'll go ahead and assume that, that I know what my current coordinate pair is, and I know the coordinate, x, y, of the goal that I'm trying to get to. And in this situation, I'd like an algorithm that is a little bit more intelligent, that somehow knows that I should be making progress towards the goal,

55:28 and this is probably the way to do that because in a maze, moving in the coordinate direction of the goal is usually, though not always, a good thing. And so here we draw a distinction between two different types of search algorithms, uninformed search and informed search. Uninformed search algorithms are algorithms like DFS and BFS,

55:49 the two algorithms that we just looked at, which are search strategies that don't use any problem-specific knowledge to be able to solve the problem. DFS and BFS didn't really care about the structure of the maze or anything about the way that a maze is in order to solve the problem.

56:05 They just look at the actions available and choose from those actions, and it doesn't matter whether it's a maze or some other problem, the solution or the way that it tries to solve the problem is really fundamentally going to be the same. What we're going to take a look at now is an improvement

56:20 upon uninformed search. We're going to take a look at informed search. Informed search are going to be search strategies that use knowledge specific to the problem to be able to better find a solution. And in the case of a maze, this problem-specific knowledge is something like if I'm in a square that is geographically closer to the goal,

56:40 that is better than being in a square that is geographically further away. And this is something we can only know by thinking about this problem and reasoning about what knowledge might be helpful for our AI agent to know a little something about. There are a number of different types of informed search.

56:59 Specifically, first, we're going to look at a particular type of search algorithm called greedy best-first search. Greedy best-first search, often abbreviated G-BFS, is a search algorithm that instead of expanding the deepest node like DFS or the shallowest node like BFS, this algorithm

57:17 is always going to expand the node that it thinks is closest to the goal. Now, the search algorithm isn't going to know for sure whether it is the closest thing to the goal. Because if we knew what was closest to the goal all the time, then we would already have a solution. The knowledge of what is close to the goal,

57:33 we could just follow those steps in order to get from the initial position to the solution. But if we don't know the solution, meaning we don't know exactly what's closest to the goal, instead we can use an estimate of what's closest to the goal, otherwise known as a heuristic, just some way of estimating whether or not

57:51 we're close to the goal. And we'll do so using a heuristic function conventionally called h of n that takes a status input and returns our estimate of how close we are to the goal. So what might this heuristic function actually look like in the case of a maze solving algorithm? Where we're trying to solve a maze, what does the heuristic look like?

58:12 Well, the heuristic needs to answer a question between these two cells, C and D, which one is better? Which one would I rather be in if I'm trying to find my way to the goal? Well, any human could probably look at this and tell you, you know what, D looks like it's better. Even if the maze is convoluted and you haven't thought about all the walls,

58:30 D is probably better. And why is D better? Well, because if you ignore the wall, so let's just pretend the walls don't exist for a moment and relax the problem, so to speak, D, just in terms of coordinate pairs, is closer to this goal. It's fewer steps that I wouldn't take to get to the goal as compared to C,

58:49 even if you ignore the walls. If you just know the xy-coordinate of C and the xy-coordinate of the goal, and likewise you know the xy-coordinate of D, you can calculate the D just geographically. Ignoring the walls looks like it's better. And so this is the heuristic function that we're going to use.

59:06 And it's something called the Manhattan distance, one specific type of heuristic, where the heuristic is how many squares vertically and horizontally and then left to right, so not allowing myself to go diagonally, just either up or right or left or down. How many steps do I need to take to get from each of these cells to the goal?

59:24 Well, as it turns out, D is much closer. There are fewer steps. It only needs to take six steps in order to get to that goal. Again, here, ignoring the walls. We've relaxed the problem a little bit. We're just concerned with if you do the math to subtract the x values from each other and the y values from each other,

59:42 what is our estimate of how far we are away? We can estimate the D is closer to the goal than C is. And so now we have an approach. We have a way of picking which node to remove from the frontier. And at each stage in our algorithm, we're going to remove a node from the frontier.

59:58 We're going to explore the node if it has the smallest value for this heuristic function, if it has the smallest Manhattan distance to the goal. And so what would this actually look like? Well, let me first label this graph, label this maze, with a number representing the value of this heuristic function,

60:15 the value of the Manhattan distance from any of these cells. So from this cell, for example, we're one away from the goal. From this cell, we're two away from the goal, three away, four away. Here, we're five away because we have to go one to the right and then four up. From somewhere like here, the Manhattan distance is two.

60:32 We're only two squares away from the goal geographically, even though in practice, we're going to have to take a longer path. But we don't know that yet. The heuristic is just some easy way to estimate how far we are away from the goal. And maybe our heuristic is overly optimistic.

60:48 It thinks that, yeah, we're only two steps away. When in practice, when you consider the walls, it might be more steps. So the important thing here is that the heuristic isn't a guarantee of how many steps it's going to take. It is estimating. It's an attempt at trying to approximate.

61:03 And it does seem generally the case that the squares that look closer to the goal have smaller values for the heuristic function than squares that are further away. So now, using greedy best-first search, what might this algorithm actually do? Well, again, for these first five steps, there's not much of a choice.

61:22 We start at this initial state a, and we say, all right, we have to explore these five states. But now we have a decision point. Now we have a choice between going left and going right. And before, when DFS and BFS would just pick arbitrarily, because it just depends on the order you throw these two nodes into the frontier,

61:38 and we didn't specify what order you put them into the frontier, only the order you take them out, here we can look at 13 and 11 and say that, all right, this square is a distance of 11 away from the goal according to our heuristic, according to our estimate. And this one, we estimate to be 13 away from the goal.

61:58 So between those two options, between these two choices, I'd rather have the 11. I'd rather be 11 steps away from the goal, so I'll go to the right. We're able to make an informed decision, because we know a little something more about this problem. So then we keep following, 10, 9, 8.

62:14 Between the two 7s, we don't really have much of a way to know between those. So then we do just have to make an arbitrary choice. And you know what, maybe we choose wrong. But that's OK, because now we can still say, all right, let's try this 7. We say 7, 6, we have to make this choice,

62:29 even though it increases the value of the heuristic function. But now we have another decision point, between 6 and 8, and between those two. And really, we're also considering this 13, but that's much higher. Between 6, 8, and 13, well, the 6 is the smallest value, so we'd rather take the 6.

62:45 We're able to make an informed decision that going this way to the right is probably better than going down. So we turn this way, we go to 5. And now we find a decision point where we'll actually make a decision that we might not want to make, but there's unfortunately not too much of a way around this.

63:00 We see 4 and 6. 4 looks closer to the goal, right? It's going up, and the goal is further up. So we end up taking that route, which ultimately leads us to a dead end. But that's OK, because we can still say, all right, now let's try the 6. And now follow this route that will ultimately lead us to the goal.

63:17 And so this now is how greedy best-for-search might try to approach this problem by saying, whenever we have a decision between multiple nodes that we could explore, let's explore the node that has the smallest value of h of n, this heuristic function that is estimating how far I have to go.

63:35 And it just so happens that in this case, we end up doing better in terms of the number of states we needed to explore than BFS needed to. BFS explored all of this section and all of that section, but we were able to eliminate that by taking advantage of this heuristic, this knowledge about how close we are to the goal or some estimate of that idea.

63:56 So this seems much better. So wouldn't we always prefer an algorithm like this over an algorithm like breadth-first search? Well, maybe one thing to take into consideration is that we need to come up with a good heuristic, how good the heuristic is, is going to affect how good this algorithm is.

64:12 And coming up with a good heuristic can oftentimes be challenging. But the other thing to consider is to ask the question, just as we did with the prior two algorithms, is this algorithm optimal? Will it always find the shortest path from the initial state to the goal? And to answer that question, let's take a look at this example for a moment.

64:32 Take a look at this example. Again, we're trying to get from A to B. And again, I've labeled each of the cells with their Manhattan distance from the goal. The number of squares up and to the right, you would need to travel in order to get from that square to the goal. And let's think about, would greedy best-first search

64:50 that always picks the smallest number end up finding the optimal solution? What is the shortest solution? And would this algorithm find it? And the important thing to realize is that right here is the decision point. We're estimated to be 12 away from the goal. And we have two choices.

65:08 We can go to the left, which we estimate to be 13 away from the goal. Or we can go up, where we estimate it to be 11 away from the goal. And between those two, greedy best-first search is going to say the 11 looks better than the 13. And in doing so, greedy best-first search will end up

65:26 finding this path to the goal. But it turns out this path is not optimal. There is a way to get to the goal using fewer steps. And it's actually this way, this way that ultimately involved fewer steps, even though it meant at this moment choosing the worst option between the two or what we estimated to be the worst option based on the heuristics.

65:47 And so this is what we mean by this is a greedy algorithm. It's making the best decision locally. At this decision point, it looks like it's better to go here than it is to go to the 13. But in the big picture, it's not necessarily optimal. That it might find a solution when in actuality,

66:03 there was a better solution available. So we would like some way to solve this problem. We like the idea of this heuristic, of being able to estimate the path, the distance between us and the goal. And that helps us to be able to make better decisions and to eliminate having to search through entire parts of this state space.

66:23 But we would like to modify the algorithm so that we can achieve optimality, so that it can be optimal. And what is the way to do this? What is the intuition here? Well, let's take a look at this problem. In this initial problem, greedy best research found us this solution here, this long path.

66:40 And the reason why it wasn't great is because, yes, the heuristic numbers went down pretty low. But later on, they started to build back up. They built back 8, 9, 10, 11, all the way up to 12 in this case. And so how might we go about trying to improve this algorithm? Well, one thing that we might realize is that if we go all the way

66:59 through this algorithm, through this path, and we end up going to the 12, and we've had to take this many steps, who knows how many steps that is, just to get to this 12, we could have also, as an alternative, taken much fewer steps, just six steps, and ended up at this 13 here. And yes, 13 is more than 12, so it looks like it's not as good.

67:20 But it required far fewer steps. It only took six steps to get to this 13 versus many more steps to get to this 12. And while greedy best research says, oh, well, 12 is better than 13, so pick the 12, we might more intelligently say, I'd rather be somewhere that heuristically looks

67:37 like it takes slightly longer if I can get there much more quickly. And we're going to encode that idea, this general idea, into a more formal algorithm known as A star search. A star search is going to solve this problem by instead of just considering the heuristic, also considering how long it took us to get to any particular state.

67:59 So the distinction is greedy best for search. If I am in a state right now, the only thing I care about is, what is the estimated distance, the heuristic value, between me and the goal? Whereas A star search will take into consideration two pieces of information. It'll take into consideration, how far do I estimate I am from the goal?

68:17 But also, how far did I have to travel in order to get here? Because that is relevant, too. So we'll search algorithms by expanding the node with the lowest value of g of n plus h of n. h of n is that same heuristic that we were talking about a moment ago that's going to vary based on the problem.

68:36 But g of n is going to be the cost to reach the node, how many steps I had to take, in this case, to get to my current position. So what does that search algorithm look like in practice? Well, let's take a look. Again, we've got the same maze. And again, I've labeled them with their Manhattan distance.

68:54 This value is the h of n value, the heuristic estimate of how far each of these squares is away from the goal. But now, as we begin to explore states, we care not just about this heuristic value, but also about g of n, the number of steps I had to take in order to get there. And I care about summing those two numbers together.

69:14 So what does that look like? On this very first step, I have taken one step. And now I am estimated to be 16 steps away from the goal. So the total value here is 17. Then I take one more step. I've now taken two steps. And I estimate myself to be 15 away from the goal, again, a total value of 17.

69:33 Now I've taken three steps. And I'm estimated to be 14 away from the goal, so on and so forth. Four steps, an estimate of 13. Five steps, estimate of 12. And now here's a decision point. I could either be six steps away from the goal with a heuristic of 13 for a total of 19, or I could be six steps away

69:53 from the goal with a heuristic of 11 with an estimate of 17 for the total. So between 19 and 17, I'd rather take the 17, the 6 plus 11. So so far, no different than what we saw before. We're still taking this option because it appears to be better. And I keep taking this option because it appears to be better.

70:11 But it's right about here that things get a little bit different. Now I could be 15 steps away from the goal with an estimated distance of 6. So 15 plus 6, total value of 21. Alternatively, I could be six steps away from the goal, because this is five steps away, so this is six steps away,

70:31 with a total value of 13 as my estimate. So 6 plus 13, that's 19. So here, we would evaluate g of n plus h of n to be 19, 6 plus 13. Whereas here, we would be 15 plus 6, or 21. And so the intuition is 19 less than 21, pick here. But the idea is ultimately I'd rather be having taken fewer steps, get to a 13,

70:55 than having taken 15 steps and be at a 6, because it means I've had to take more steps in order to get there. Maybe there's a better path this way. So instead, we'll explore this route. Now if we go one more, this is seven steps plus 14 is 21. So between those two, it's sort of a toss-up.

71:13 We might end up exploring that one anyways. But after that, as these numbers start to get bigger in the heuristic values, and these heuristic values start to get smaller, you'll find that we'll actually keep exploring down this path. And you can do the math to see that at every decision point,

71:28 A star search is going to make a choice based on the sum of how many steps it took me to get to my current position, and then how far I estimate I am from the goal. So while we did have to explore some of these states, the ultimate solution we found was, in fact, an optimal solution.

71:47 It did find us the quickest possible way to get from the initial state to the goal. And it turns out that A star is an optimal search algorithm under certain conditions. So the conditions are H of n, my heuristic, needs to be admissible. What does it mean for a heuristic to be admissible?

72:04 Well, a heuristic is admissible if it never overestimates the true cost. H of n always needs to either get it exactly right in terms of how far away I am, or it needs to underestimate. So we saw an example from before where the heuristic value was much smaller than the actual cost it would take.

72:23 That's totally fine, but the heuristic value should never overestimate. It should never think that I'm further away from the goal than I actually am. And meanwhile, to make a stronger statement, H of n also needs to be consistent. And what does it mean for it to be consistent? Mathematically, it means that for every node, which we'll call n,

72:42 and successor, the node after me, that I'll call n prime, where it takes a cost of C to make that step, the heuristic value of n needs to be less than or equal to the heuristic value of n prime plus the cost. So it's a lot of math, but in words what that ultimately means is that if I am here at this state right now,

73:01 the heuristic value from me to the goal shouldn't be more than the heuristic value of my successor, the next place I could go to, plus however much it would cost me to just make that step from one step to the next step. And so this is just making sure that my heuristic is consistent between all

73:19 of these steps that I might take. So as long as this is true, then A star search is going to find me an optimal solution. And this is where much of the challenge of solving these search problems can sometimes come in, that A star search is an algorithm that is known and you could write the code fairly easily,

73:34 but it's choosing the heuristic. It can be the interesting challenge. The better the heuristic is, the better I'll be able to solve the problem in the fewer states that I'll have to explore. And I need to make sure that the heuristic satisfies these particular constraints. So all in all, these are some of the examples of search algorithms

73:52 that might work, and certainly there are many more than just this. A star, for example, does have a tendency to use quite a bit of memory. So there are alternative approaches to A star that ultimately use less memory than this version of A star happens to use, and there are other search algorithms

74:08 that are optimized for other cases as well. But now so far, we've only been looking at search algorithms where there is one agent. I am trying to find a solution to a problem. I am trying to navigate my way through a maze. I am trying to solve a 15 puzzle. I am trying to find driving directions from point A to point B.

74:28 Sometimes in search situations, though, we'll enter an adversarial situation, where I am an agent trying to make intelligent decisions. And there's someone else who is fighting against me, so to speak, that has opposite objectives, someone where I am trying to succeed, someone else that wants me to fail.

74:45 And this is most popular in something like a game, a game like Tic Tac Toe, where we've got this 3 by 3 grid, and x and o take turns, either writing an x or an o in any one of these squares. And the goal is to get three x's in a row if you're the x player, or three o's in a row if you're the o player.

75:03 And computers have gotten quite good at playing games, Tic Tac Toe very easily, but even more complex games. And so you might imagine, what does an intelligent decision in a game look like? So maybe x makes an initial move in the middle, and o plays up here. What does an intelligent move for x now become?

75:20 Where should you move if you were x? And it turns out there are a couple of possibilities. But if an AI is playing this game optimally, then the AI might play somewhere like the upper right, where in this situation, o has the opposite objective of x. x is trying to win the game to get three in a row diagonally here.

75:38 And o is trying to stop that objective, opposite of the objective. And so o is going to place here to try to block. But now, x has a pretty clever move. x can make a move like this, where now x has two possible ways that x can win the game. x could win the game by getting three in a row across here.

75:55 Or x could win the game by getting three in a row vertically this way. So it doesn't matter where o makes their next move. o could play here, for example, blocking the three in a row horizontally. But then x is going to win the game by getting a three in a row vertically. And so there's a fair amount of reasoning that's

76:11 going on here in order for the computer to be able to solve a problem. And it's similar in spirit to the problems we've looked at so far. There are actions. There's some sort of state of the board and some transition from one action to the next. But it's different in the sense that this is now

76:26 not just a classical search problem, but an adversarial search problem. That I am at the x player trying to find the best moves to make, but I know that there is some adversary that is trying to stop me. So we need some sort of algorithm to deal with these adversarial type of search

76:41 situations. And the algorithm we're going to take a look at is an algorithm called Minimax, which works very well for these deterministic games where there are two players. It can work for other types of games as well. But we'll look right now at games where I make a move, then my opponent makes a move.

76:57 And I am trying to win, and my opponent is trying to win also. Or in other words, my opponent is trying to get me to lose. And so what do we need in order to make this algorithm work? Well, any time we try and translate this human concept of playing a game, winning and losing to a computer, we want to translate it

77:14 in terms that the computer can understand. And ultimately, the computer really just understands the numbers. And so we want some way of translating a game of x's and o's on a grid to something numerical, something the computer can understand. The computer doesn't normally understand notions of win or lose.

77:30 But it does understand the concept of bigger and smaller. And so what we might do is we might take each of the possible ways that a tic-tac-toe game can unfold and assign a value or a utility to each one of those possible ways. And in a tic-tac-toe game, and in many types of games,

77:48 there are three possible outcomes. The outcomes are o wins, x wins, or nobody wins. So player one wins, player two wins, or nobody wins. And for now, let's go ahead and assign each of these possible outcomes a different value. We'll say o winning, that'll have a value of negative 1.

78:07 Nobody winning, that'll have a value of 0. And x winning, that will have a value of 1. So we've just assigned numbers to each of these three possible outcomes. And now we have two players, we have the x player and the o player. And we're going to go ahead and call the x player the max player.

78:26 And we'll call the o player the min player. And the reason why is because in the min and max algorithm, the max player, which in this case is x, is aiming to maximize the score. These are the possible options for the score, negative 1, 0, and 1. x wants to maximize the score, meaning if at all possible,

78:45 x would like this situation, where x wins the game, and we give it a score of 1. But if this isn't possible, if x needs to choose between these two options, negative 1, meaning o winning, or 0, meaning nobody winning, x would rather that nobody wins, score of 0, than a score of negative 1, o winning.

79:04 So this notion of winning and losing and tying has been reduced mathematically to just this idea of try and maximize the score. The x player always wants the score to be bigger. And on the flip side, the min player, in this case o, is aiming to minimize the score. The o player wants the score to be as small as possible.

79:26 So now we've taken this game of x's and o's and winning and losing and turned it into something mathematical, something where x is trying to maximize the score, o is trying to minimize the score. Let's now look at all of the parts of the game that we need in order to encode it in an AI

79:41 so that an AI can play a game like tic-tac-toe. So the game is going to need a couple of things. We'll need some sort of initial state that will, in this case, call s0, which is how the game begins, like an empty tic-tac-toe board, for example. We'll also need a function called player, where the player function

80:00 is going to take as input a state here represented by s. And the output of the player function is going to be which player's turn is it. We need to be able to give a tic-tac-toe board to the computer, run it through a function, and that function tells us whose turn it is. We'll need some notion of actions that we can take.

80:19 We'll see examples of that in just a moment. We need some notion of a transition model, same as before. If I have a state and I take an action, I need to know what results as a consequence of it. I need some way of knowing when the game is over. So this is equivalent to kind of like a goal test,

80:34 but I need some terminal test, some way to check to see if a state is a terminal state, where a terminal state means the game is over. In a classic game of tic-tac-toe, a terminal state means either someone has gotten three in a row or all of the squares of the tic-tac-toe board are filled.

80:50 Either of those conditions make it a terminal state. In a game of chess, it might be something like when there is checkmate or if checkmate is no longer possible, that that becomes a terminal state. And then finally, we'll need a utility function, a function that takes a state and gives us a numerical value for that terminal state, some way of saying

81:08 if x wins the game, that has a value of 1. If o is won the game, that has a value of negative 1. If nobody has won the game, that has a value of 0. So let's take a look at each of these in turn. The initial state, we can just represent in tic-tac-toe as the empty game board. This is where we begin.

81:24 It's the place from which we begin this search. And again, I'll be representing these things visually, but you can imagine this really just being like an array or a two-dimensional array of all of these possible squares. Then we need the player function that, again, takes a state

81:40 and tells us whose turn it is. Assuming x makes the first move, if I have an empty game board, then my player function is going to return x. And if I have a game board where x has made a move, then my player function is going to return o. The player function takes a tic-tac-toe game board

81:55 and tells us whose turn it is. Next up, we'll consider the actions function. The actions function, much like it did in classical search, takes a state and gives us the set of all of the possible actions we can take in that state. So let's imagine it's o is turned to move in a game board that looks like this.

82:15 What happens when we pass it into the actions function? So the actions function takes this state of the game as input, and the output is a set of possible actions. It's a set of I could move in the upper left or I could move in the bottom middle. So those are the two possible action choices

82:32 that I have when I begin in this particular state. Now, just as before, when we had states and actions, we need some sort of transition model to tell us when we take this action in the state, what is the new state that we get. And here, we define that using the result function that takes a state as input as well as an action.

82:52 And when we apply the result function to this state, saying that let's let o move in this upper left corner, the new state we get is this resulting state where o is in the upper left corner. And now, this seems obvious to someone who knows how to play tic-tac-toe. Of course, you play in the upper left corner.

83:07 That's the board you get. But all of this information needs to be encoded into the AI. The AI doesn't know how to play tic-tac-toe until you tell the AI how the rules of tic-tac-toe work. And this function, defining this function here, allows us to tell the AI how this game actually works

83:23 and how actions actually affect the outcome of the game. So the AI needs to know how the game works. The AI also needs to know when the game is over, as by defining a function called terminal that takes as input a state s, such that if we take a game that is not yet over, pass it into the terminal function, the output is false.

83:42 The game is not over. But if we take a game that is over because x has gotten three in a row along that diagonal, pass that into the terminal function, then the output is going to be true because the game now is, in fact, over. And finally, we've told the AI how the game works in terms of what moves can be made and what happens when you make those moves.

84:01 We've told the AI when the game is over. Now we need to tell the AI what the value of each of those states is. And we do that by defining this utility function that takes a state s and tells us the score or the utility of that state. So again, we said that if x wins the game, that utility is a value of 1,

84:19 whereas if o wins the game, then the utility of that is negative 1. And the AI needs to know, for each of these terminal states where the game is over, what is the utility of that state? So if I give you a game board like this where the game is, in fact, over, and I ask the AI to tell me what the value of that state is, it could do so.

84:39 The value of the state is 1. Where things get interesting, though, is if the game is not yet over. Let's imagine a game board like this, where in the middle of the game, it's o's turn to make a move. So how do we know it's o's turn to make a move? We can calculate that using the player function.

84:56 We can say player of s, pass in the state, o is the answer. So we know it's o's turn to move. And now, what is the value of this board and what action should o take? Well, that's going to depend. We have to do some calculation here. And this is where the minimax algorithm really comes in.

85:14 Recall that x is trying to maximize the score, which means that o is trying to minimize the score. So o would like to minimize the total value that we get at the end of the game. And because this game isn't over yet, we don't really know just yet what the value of this game board is.

85:31 We have to do some calculation in order to figure that out. And so how do we do that kind of calculation? Well, in order to do so, we're going to consider, just as we might in a classical search situation, what actions could happen next and what states will that take us to. And it turns out that in this position, there are only two open squares,

85:50 which means there are only two open places where o can make a move. o could either make a move in the upper left or o can make a move in the bottom middle. And minimax doesn't know right out of the box which of those moves is going to be better. So it's going to consider both. But now, we sort of run into the same situation.

86:09 Now, I have two more game boards, neither of which is over. What happens next? And now, it's in this sense that minimax is what we'll call a recursive algorithm. It's going to now repeat the exact same process, although now considering it from the opposite perspective. It's as if I am now going to put myself, if I am the o player,

86:27 I'm going to put myself in my opponent's shoes, my opponent as the x player, and consider what would my opponent do if they were in this position? What would my opponent do, the x player, if they were in that position? And what would then happen? Well, the other player, my opponent, the x player,

86:44 is trying to maximize the score, whereas I am trying to minimize the score as the o player. So x is trying to find the maximum possible value that they can get. And so what's going to happen? Well, from this board position, x only has one choice. x is going to play here, and they're going to get three in a row.

87:02 And we know that that board, x winning, that has a value of 1. If x wins the game, the value of that game board is 1. And so from this position, if this state can only ever lead to this state, it's the only possible option, and this state has a value of 1, then the maximum possible value

87:21 that the x player can get from this game board is also 1. From here, the only place we can get is to a game with a value of 1, so this game board also has a value of 1. Now we consider this one over here. What's going to happen now? Well, x needs to make a move. The only move x can make is in the upper left, so x will go there.

87:40 And in this game, no one wins the game. Nobody has three in a row. And so the value of that game board is 0. Nobody is 1. And so again, by the same logic, if from this board position the only place we can get to is a board where the value is 0, then this state must also have a value of 0.

87:57 And now here comes the choice part, the idea of trying to minimize. I, as the o player, now know that if I make this choice moving in the upper left, that is going to result in a game with a value of 1, assuming everyone plays optimally. And if I instead play in the lower middle,

88:13 choose this fork in the road, that is going to result in a game board with a value of 0. I have two options. I have a 1 and a 0 to choose from, and I need to pick. And as the min player, I would rather choose the option with the minimum value. So whenever a player has multiple choices,

88:29 the min player will choose the option with the smallest value. The max player will choose the option with the largest value. Between the 1 and the 0, the 0 is smaller, meaning I'd rather tie the game than lose the game. And so this game board will say also has a value of 0, because if I am playing optimally, I will pick this fork in the road.

88:48 I'll place my o here to block x's 3 in a row, x will move in the upper left, and the game will be over, and no one will have won the game. So this is now the logic of minimax, to consider all of the possible options that I can take, all of the actions that I can take, and then to put myself in my opponent's shoes.

89:06 I decide what move I'm going to make now by considering what move my opponent will make on the next turn. And to do that, I consider what move I would make on the turn after that, so on and so forth, until I get all the way down to the end of the game, to one of these so-called terminal states.

89:21 In fact, this very decision point, where I am trying to decide as the o player what to make a decision about, might have just been a part of the logic that the x player, my opponent, was using, the move before me. This might be part of some larger tree, where x is trying to make a move in this situation,

89:38 and needs to pick between three different options in order to make a decision about what to happen. And the further and further away we are from the end of the game, the deeper this tree has to go. Because every level in this tree is going to correspond to one move, one move or action that I take, one move or action

89:55 that my opponent takes, in order to decide what happens. And in fact, it turns out that if I am the x player in this position, and I recursively do the logic, and see I have a choice, three choices, in fact, one of which leads to a value of 0. If I play here, and if everyone plays optimally, the game will be a tie.

90:12 If I play here, then o is going to win, and I'll lose playing optimally. Or here, where I, the x player, can win, well between a score of 0, and negative 1, and 1, I'd rather pick the board with a value of 1, because that's the maximum value I can get. And so this board would also have a maximum value of 1.

90:32 And so this tree can get very, very deep, especially as the game starts to have more and more moves. And this logic works not just for tic-tac-toe, but any of these sorts of games, where I make a move, my opponent makes a move, and ultimately, we have these adversarial objectives.

90:47 And we can simplify the diagram into a diagram that looks like this. This is a more abstract version of the minimax tree, where these are each states, but I'm no longer representing them as exactly like tic-tac-toe boards. This is just representing some generic game that might be tic-tac-toe,

91:02 might be some other game altogether. Any of these green arrows that are pointing up, that represents a maximizing state. I would like the score to be as big as possible. And any of these red arrows pointing down, those are minimizing states, where the player is the min player, and they are trying to make the score as small as possible.

91:20 So if you imagine in this situation, I am the maximizing player, this player here, and I have three choices. One choice gives me a score of 5, one choice gives me a score of 3, and one choice gives me a score of 9. Well, then between those three choices, my best option is to choose this 9 over here, the score that

91:39 maximizes my options out of all the three options. And so I can give this state a value of 9, because among my three options, that is the best choice that I have available to me. So that's my decision now. You imagine it's like one move away from the end of the game. But then you could also ask a reasonable question,

91:58 what might my opponent do two moves away from the end of the game? My opponent is the minimizing player. They are trying to make the score as small as possible. Imagine what would have happened if they had to pick which choice to make. One choice leads us to this state, where I, the maximizing player,

92:14 am going to opt for 9, the biggest score that I can get. And 1 leads to this state, where I, the maximizing player, would choose 8, which is then the largest score that I can get. Now the minimizing player, forced to choose between a 9 or an 8, is going to choose the smallest possible score,

92:31 which in this case is an 8. And that is then how this process would unfold, that the minimizing player in this case considers both of their options, and then all of the options that would happen as a result of that. So this now is a general picture of what the minimax algorithm looks like.

92:48 Let's now try to formalize it using a little bit of pseudocode. So what exactly is happening in the minimax algorithm? Well, given a state s, we need to decide what to happen. The max player, if it's max's player's turn, then max is going to pick an action a in actions of s. Recall that actions is a function that takes a state

93:08 and gives me back all of the possible actions that I can take. It tells me all of the moves that are possible. The max player is going to specifically pick an action a in this set of actions that gives me the highest value of min value of result of s and a. So what does that mean?

93:27 Well, it means that I want to make the option that gives me the highest score of all of the actions a. But what score is that going to have? To calculate that, I need to know what my opponent, the min player, is going to do if they try to minimize the value of the state that results.

93:45 So we say, what state results after I take this action? And what happens when the min player tries to minimize the value of that state? I consider that for all of my possible options. And after I've considered that for all of my possible options, I pick the action a that has the highest value.

94:03 Likewise, the min player is going to do the same thing but backwards. They're also going to consider what are all of the possible actions they can take if it's their turn. And they're going to pick the action a that has the smallest possible value of all the options. And the way they know what the smallest possible value of all the options

94:19 is is by considering what the max player is going to do by saying, what's the result of applying this action to the current state? And then what would the max player try to do? What value would the max player calculate for that particular state? So everyone makes their decision based on trying

94:36 to estimate what the other person would do. And now we need to turn our attention to these two functions, max value and min value. How do you actually calculate the value of a state if you're trying to maximize its value? And how do you calculate the value of a state if you're trying to minimize the value?

94:54 If you can do that, then we have an entire implementation of this min and max algorithm. So let's try it. Let's try and implement this max value function that takes a state and returns as output the value of that state if I'm trying to maximize the value of the state. Well, the first thing I can check for is to see if the game is over.

95:13 Because if the game is over, in other words, if the state is a terminal state, then this is easy. I already have this utility function that tells me what the value of the board is. If the game is over, I just check, did x win, did o win, is it a tie? And this utility function just knows what the value of the state is.

95:30 What's trickier is if the game isn't over. Because then I need to do this recursive reasoning about thinking, what is my opponent going to do on the next move? And I want to calculate the value of this state. And I want the value of the state to be as high as possible. And I'll keep track of that value in a variable called v.

95:48 And if I want the value to be as high as possible, I need to give v an initial value. And initially, I'll just go ahead and set it to be as low as possible. Because I don't know what options are available to me yet. So initially, I'll set v equal to negative infinity, which seems a little bit strange.

96:06 But the idea here is I want the value initially to be as low as possible. Because as I consider my actions, I'm always going to try and do better than v. And if I set v to negative infinity, I know I can always do better than that. So now I consider my actions. And this is going to be some kind of loop

96:23 where for every action in actions of state, recall actions as a function that takes my state and gives me all the possible actions that I can use in that state. So for each one of those actions, I want to compare it to v and say, all right, v is going to be equal to the maximum of v and this expression.

96:44 So what is this expression? Well, first it is get the result of taking the action in the state and then get the min value of that. In other words, let's say I want to find out from that state what is the best that the min player can do because they're going to try and minimize the score.

97:03 So whatever the resulting score is of the min value of that state, compare it to my current best value and just pick the maximum of those two because I am trying to maximize the value. In short, what these three lines of code are doing are going through all of my possible actions and asking the question,

97:19 how do I maximize the score given what my opponent is going to try to do? After this entire loop, I can just return v and that is now the value of that particular state. And for the min player, it's the exact opposite of this, the same logic just backwards. To calculate the minimum value of a state,

97:37 first we check if it's a terminal state. If it is, we return its utility. Otherwise, we're going to now try to minimize the value of the state given all of my possible actions. So I need an initial value for v, the value of the state. And initially, I'll set it to infinity because I

97:54 know I can always get something less than infinity. So by starting with v equals infinity, I make sure that the very first action I find, that will be less than this value of v. And then I do the same thing, loop over all of my possible actions. And for each of the results that we could get when the max player makes

98:11 their decision, let's take the minimum of that and the current value of v. So after all is said and done, I get the smallest possible value of v that I then return back to the user. So that, in effect, is the pseudocode for Minimax. That is how we take a gain and figure out what the best move to make

98:28 is by recursively using these max value and min value functions, where max value calls min value, min value calls max value back and forth, all the way until we reach a terminal state, at which point our algorithm can simply return the utility of that particular state. So what you might imagine is that this is going to start to be a long process,

98:49 especially as games start to get more complex, as we start to add more moves and more possible options and games that might last quite a bit longer. So the next question to ask is, what sort of optimizations can we make here? How can we do better in order to use less space or take less time

99:05 to be able to solve this kind of problem? And we'll take a look at a couple of possible optimizations. But for one, we'll take a look at this example. Again, returning to these up arrows and down arrows, let's imagine that I now am the max player, this green arrow. I am trying to make this score as high as possible.

99:23 And this is an easy game where there are just two moves. I make a move, one of these three options. And then my opponent makes a move, one of these three options, based on what move I make. And as a result, we get some value. Let's look at the order in which I do these calculations

99:40 and figure out if there are any optimizations I might be able to make to this calculation process. I'm going to have to look at these states one at a time. So let's say I start here on the left and say, all right, now I'm going to consider, what will the min player, my opponent, try to do here?

99:54 Well, the min player is going to look at all three of their possible actions and look at their value, because these are terminal states. They're the end of the game. And so they'll see, all right, this node is a value of four, value of eight, value of five. And the min player is going to say, well, all right,

100:09 between these three options, four, eight, and five, I'll take the smallest one. I'll take the four. So this state now has a value of four. Then I, as the max player, say, all right, if I take this action, it will have a value of four. That's the best that I can do, because min player

100:23 is going to try and minimize my score. So now what if I take this option? We'll explore this next. And now explore what the min player would do if I choose this action. And the min player is going to say, all right, what are the three options? The min player has options between nine, three, and seven.

100:40 And so three is the smallest among nine, three, and seven. So we'll go ahead and say this state has a value of three. So now I, as the max player, I have now explored two of my three options. I know that one of my options will guarantee me a score of four, at least. And one of my options will guarantee me a score of three.

100:57 And now I consider my third option and say, all right, what happens here? Same exact logic. The min player is going to look at these three states, two, four, and six. I'll say the minimum possible option is two. So the min player wants the two. Now I, as the max player, have calculated all of the information

101:12 by looking two layers deep, by looking at all of these nodes. And I can now say, between the four, the three, and the two, you know what? I'd rather take the four. Because if I choose this option, if my opponent plays optimally, they will try and get me to the four. But that's the best I can do.

101:28 I can't guarantee a higher score. Because if I pick either of these two options, I might get a three or I might get a two. And it's true that down here is a nine. And that's the highest score out of any of the scores. So I might be tempted to say, you know what? Maybe I should take this option because I might get the nine.

101:44 But if the min player is playing intelligently, if they're making the best moves at each possible option they have when they get to make a choice, I'll be left with a three. Whereas I could better, playing optimally, have guaranteed that I would get the four. So that is, in effect, the logic that I would use as a min and max player

102:02 trying to maximize my score from that node there. But it turns out they took quite a bit of computation for me to figure that out. I had to reason through all of these nodes in order to draw this conclusion. And this is for a pretty simple game where I have three choices, my opponent has three choices, and then the game's over.

102:18 So what I'd like to do is come up with some way to optimize this. Maybe I don't need to do all of this calculation to still reach the conclusion that, you know what, this action to the left, that's the best that I could do. Let's go ahead and try again and try to be a little more intelligent about how

102:34 I go about doing this. So first, I start the exact same way. I don't know what to do initially, so I just have to consider one of the options and consider what the min player might do. Min has three options, four, eight, and five. And between those three options, min says four is the best they can do

102:52 because they want to try to minimize the score. Now I, the max player, will consider my second option, making this move here, and considering what my opponent would do in response. What will the min player do? Well, the min player is going to, from that state, look at their options.

103:08 And I would say, all right, nine is an option, three is an option. And if I am doing the math from this initial state, doing all this calculation, when I see a three, that should immediately be a red flag for me. Because when I see a three down here at this state, I know that the value of this state is going to be at most three.

103:28 It's going to be three or something less than three, even though I haven't yet looked at this last action or even further actions if there were more actions that could be taken here. How do I know that? Well, I know that the min player is going to try to minimize my score. And if they see a three, the only way this

103:45 could be something other than a three is if this remaining thing that I haven't yet looked at is less than three, which means there is no way for this value to be anything more than three because the min player can already guarantee a three and they are trying to minimize my score.

104:01 So what does that tell me? Well, it tells me that if I choose this action, my score is going to be three or maybe even less than three if I'm unlucky. But I already know that this action will guarantee me a four. And so given that I know that this action guarantees me a score of four

104:17 and this action means I can't do better than three, if I'm trying to maximize my options, there is no need for me to consider this triangle here. There is no value, no number that could go here that would change my mind between these two options. I'm always going to opt for this path that gets me a four as opposed

104:35 to this path where the best I can do is a three if my opponent plays optimally. And this is going to be true for all the future states that I look at too. That if I look over here at what min player might do over here, if I see that this state is a two, I know that this state is at most a two

104:51 because the only way this value could be something other than two is if one of these remaining states is less than a two and so the min player would opt for that instead. So even without looking at these remaining states, I as the maximizing player can know that choosing this path to the left

105:09 is going to be better than choosing either of those two paths to the right because this one can't be better than three. This one can't be better than two. And so four in this case is the best that I can do. So in order to do this cut, and I can say now that this state has a value of four.

105:26 So in order to do this type of calculation, I was doing a little bit more bookkeeping, keeping track of things, keeping track all the time of what is the best that I can do, what is the worst that I can do, and for each of these states saying, all right, well, if I already know that I can get a four,

105:41 then if the best I can do at this state is a three, no reason for me to consider it, I can effectively prune this leaf and anything below it from the tree. And it's for that reason this approach, this optimization to minimax, is called alpha, beta pruning. Alpha and beta stand for these two values

105:59 that you'll have to keep track of of the best you can do so far and the worst you can do so far. And pruning is the idea of if I have a big, long, deep search tree, I might be able to search it more efficiently if I don't need to search through everything, if I can remove some of the nodes to try and optimize the way that I

106:15 look through this entire search space. So alpha, beta pruning can definitely save us a lot of time as we go about the search process by making our searches more efficient. But even then, it's still not great as games get more complex. Tic-tac-toe, fortunately, is a relatively simple game.

106:33 And we might reasonably ask a question like, how many total possible tic-tac-toe games are there? You can think about it. You can try and estimate how many moves are there at any given point, how many moves long can the game last. It turns out there are about 255,000 possible tic-tac-toe games

106:52 that can be played. But compare that to a more complex game, something like a game of chess, for example. Far more pieces, far more moves, games that last much longer. How many total possible chess games could there be? It turns out that after just four moves each, four moves by the white player,

107:09 four moves by the black player, that there are 288 billion possible chess games that can result from that situation, after just four moves each. And going even further, if you look at entire chess games and how many possible chess games there could be as a result there, there are more than 10 to the 29,000 possible chess games,

107:28 far more chess games than could ever be considered. And this is a pretty big problem for the Minimax algorithm, because the Minimax algorithm starts with an initial state, considers all the possible actions, and all the possible actions after that, all the way until we get to the end of the game.

107:45 And that's going to be a problem if the computer is going to need to look through this many states, which is far more than any computer could ever do in any reasonable amount of time. So what do we do in order to solve this problem? Instead of looking through all these states which

107:59 is totally intractable for a computer, we need some better approach. And it turns out that better approach generally takes the form of something called depth-limited Minimax, where normally Minimax is depth-unlimited. We just keep going layer after layer, move after move, until we get to the end of the game.

108:15 Depth-limited Minimax is instead going to say, you know what, after a certain number of moves, maybe I'll look 10 moves ahead, maybe I'll look 12 moves ahead, but after that point, I'm going to stop and not consider additional moves that might come after that, just because it would be computationally intractable

108:30 to consider all of those possible options. But what do we do after we get 10 or 12 moves deep when we arrive at a situation where the game's not over? Minimax still needs a way to assign a score to that game board or game state to figure out what its current value is, which is easy to do

108:47 if the game is over, but not so easy to do if the game is not yet over. So in order to do that, we need to add one additional feature to depth-limited Minimax called an evaluation function, which is just some function that is going to estimate the expected utility of a game from a given state.

109:04 So in a game like chess, if you imagine that a game value of 1 means white wins, negative 1 means black wins, 0 means it's a draw, then you might imagine that a score of 0.8 means white is very likely to win, though certainly not guaranteed. And you would have an evaluation function

109:21 that estimates how good the game state happens to be. And depending on how good that evaluation function is, that is ultimately what's going to constrain how good the AI is. The better the AI is at estimating how good or how bad any particular game state is, the better the AI is going to be able to play that game.

109:41 If the evaluation function is worse and not as good as it estimating what the expected utility is, then it's going to be a whole lot harder. And you can imagine trying to come up with these evaluation functions. In chess, for example, you might write an evaluation function based on how many pieces you have as compared

109:56 to how many pieces your opponent has, because each one has a value. And your evaluation function probably needs to be a little bit more complicated than that to consider other possible situations that might arise as well. And there are many other variants on Minimax that add additional features

110:12 in order to help it perform better under these larger, more computationally untractable situations where we couldn't possibly explore all of the possible moves. So we need to figure out how to use evaluation functions and other techniques to be able to play these games ultimately better.

110:29 But this now was a look at this kind of adversarial search, these search problems where we have situations where I am trying to play against some sort of opponent. And these search problems show up all over the place throughout artificial intelligence. We've been talking a lot today about more classical search problems,

110:45 like trying to find directions from one location to another. But any time an AI is faced with trying to make a decision, like what do I do now in order to do something that is rational, or do something that is intelligent, or trying to play a game, like figuring out what move to make, these sort of algorithms

111:00 can really come in handy. It turns out that for tic-tac-toe, the solution is pretty simple because it's a small game. XKCD has famously put together a web comic where he will tell you exactly what move to make as the optimal move to make no matter what your opponent happens to do.

111:14 This type of thing is not quite as possible for a much larger game like Checkers or Chess, for example, where chess is totally computationally untractable for most computers to be able to explore all the possible states. So we really need our AI to be far more intelligent about how

111:30 they go about trying to deal with these problems and how they go about taking this environment that they find themselves in and ultimately searching for one of these solutions. So this, then, was a look at search in artificial intelligence. Next time, we'll take a look at knowledge,

111:44 thinking about how it is that our AIs are able to know information, reason about that information, and draw conclusions, all in our look at AI and the principles behind it. We'll see you next time. ["AIMS INTRO MUSIC"]

112:14 All right, welcome back, everyone, to an introduction to artificial intelligence with Python. Last time, we took a look at search problems, in particular, where we have AI agents that are trying to solve some sort of problem by taking actions in some sort of environment, whether that environment is trying to take actions by playing moves in a game

112:31 or whether those actions are something like trying to figure out where to make turns in order to get driving directions from point A to point B. This time, we're going to turn our attention more generally to just this idea of knowledge, the idea that a lot of intelligence is based on knowledge,

112:45 especially if we think about human intelligence. People know information. We know facts about the world. And using that information that we know, we're able to draw conclusions, reason about the information that we know in order to figure out how to do something or figure out some other piece of information

113:01 that we conclude based on the information we already have available to us. What we'd like to focus on now is the ability to take this idea of knowledge and being able to reason based on knowledge and apply those ideas to artificial intelligence. In particular, we're going to be building what

113:16 are known as knowledge-based agents, agents that are able to reason and act by representing knowledge internally. Somehow inside of our AI, they have some understanding of what it means to know something. And ideally, they have some algorithms or some techniques they can use based on that knowledge that they know in order to figure out

113:34 the solution to a problem or figure out some additional piece of information that can be helpful in some sense. So what do we mean by reasoning based on knowledge to be able to draw conclusions? Well, let's look at a simple example drawn from the world of Harry Potter. We take one sentence that we know to be true.

113:51 Imagine if it didn't rain, then Harry visited Hagrid today. So one fact that we might know about the world. And then we take another fact. Harry visited Hagrid or Dumbledore today, but not both. So it tells us something about the world, that Harry either visited Hagrid but not Dumbledore, or Harry visited Dumbledore but not Hagrid.

114:10 And now we have a third piece of information about the world that Harry visited Dumbledore today. So we now have three pieces of information now, three facts. Inside of a knowledge base, so to speak, information that we know. And now we, as humans, can try and reason about this and figure out, based on this information, what additional information

114:28 can we begin to conclude? And well, looking at these last two statements, Harry either visited Hagrid or Dumbledore but not both, and we know that Harry visited Dumbledore today, well, then it's pretty reasonable that we could draw the conclusion that, you know what, Harry must not have visited Hagrid today.

114:44 Because based on a combination of these two statements, we can draw this inference, so to speak, a conclusion that Harry did not visit Hagrid today. But it turns out we can even do a little bit better than that, get some more information by taking a look at this first statement and reasoning about that.

114:59 This first statement says, if it didn't rain, then Harry visited Hagrid today. So what does that mean? In all cases where it didn't rain, then we know that Harry visited Hagrid. But if we also know now that Harry did not visit Hagrid, then that tells us something about our initial premise

115:16 that we were thinking about. In particular, it tells us that it did rain today, because we can reason, if it didn't rain, that Harry would have visited Hagrid. But we know for a fact that Harry did not visit Hagrid today. So it's this kind of reason, this sort of logical reasoning,

115:32 where we use logic based on the information that we know in order to take information and reach conclusions that is going to be the focus of what we're going to be talking about today. How can we make our artificial intelligence logical so that they can perform the same kinds of deduction,

115:47 the same kinds of reasoning that we've been doing so far? Of course, humans reason about logic generally in terms of human language. That I just now was speaking in English, talking in English about these sentences and trying to reason through how it is that they relate to one another.

116:03 We're going to need to be a little bit more formal when we turn our attention to computers and being able to encode this notion of logic and truthhood and falsehood inside of a machine. So we're going to need to introduce a few more terms and a few symbols that will help us reason through this idea of logic

116:18 inside of an artificial intelligence. And we'll begin with the idea of a sentence. Now, a sentence in a natural language like English is just something that I'm saying, like what I'm saying right now. In the context of AI, though, a sentence is just an assertion about the world in what we're going to call a knowledge representation language,

116:37 some way of representing knowledge inside of our computers. And the way that we're going to spend most of today reasoning about knowledge is through a type of logic known as propositional logic. There are a number of different types of logic, some of which we'll touch on. But propositional logic is based on a logic of propositions,

116:55 or just statements about the world. And so we begin in propositional logic with a notion of propositional symbols. We will have certain symbols that are oftentimes just letters, something like P or Q or R, where each of those symbols is going to represent some fact or sentence about the world.

117:12 So P, for example, might represent the fact that it is raining. And so P is going to be a symbol that represents that idea. And Q, for example, might represent Harry visited Hagrid today. Each of these propositional symbols represents some sentence or some fact about the world. But in addition to just having individual facts about the world,

117:32 we want some way to connect these propositional symbols together in order to reason more complexly about other facts that might exist inside of the world in which we're reasoning. So in order to do that, we'll need to introduce some additional symbols that are known as logical connectives.

117:48 Now, there are a number of these logical connectives. But five of the most important, and the ones we're going to focus on today, are these five up here, each represented by a logical symbol. Not is represented by this symbol here, and is represented as sort of an upside down V, or is represented by a V shape.

118:05 Implication, and we'll talk about what that means in just a moment, is represented by an arrow. And biconditional, again, we'll talk about what that means in a moment, is represented by these double arrows. But these five logical connectives are the main ones we're going to be focusing on in terms of thinking about how

118:20 it is that a computer can reason about facts and draw conclusions based on the facts that it knows. But in order to get there, we need to take a look at each of these logical connectives and build up an understanding for what it is that they actually mean. So let's go ahead and begin with the not symbol, so this not symbol here.

118:38 And what we're going to show for each of these logical connectives is what we're going to call a truth table, a table that demonstrates what this word not means when we attach it to a propositional symbol or any sentence inside of our logical language. And so the truth table for not is shown right here.

118:57 If P, some propositional symbol, or some other sentence even, is false, then not P is true. And if P is true, then not P is false. So you can imagine that placing this not symbol in front of some sentence of propositional logic just says the opposite of that. So if, for example, P represented it is raining,

119:20 then not P would represent the idea that it is not raining. And as you might expect, if P is false, meaning if the sentence, it is raining, is false, well then the sentence not P must be true. The sentence that it is not raining is therefore true. So not, you can imagine, just takes whatever is in P and it inverts it.

119:40 It turns false into true and true into false, much analogously to what the English word not means, just taking whatever comes after it and inverting it to mean the opposite. Next up, and also very English-like, is this idea of and represented by this upside-down V shape or this point shape.

119:58 And as opposed to just taking a single argument the way not does, we have P and we have not P. And is going to combine two different sentences in propositional logic together. So I might have one sentence P and another sentence Q, and I want to combine them together to say P and Q.

120:17 And the general logic for what P and Q means is it means that both of its operands are true. P is true and also Q is true. And so here's what that truth table looks like. This time we have two variables, P and Q. And when we have two variables, each of which can be in two possible states, true or false,

120:37 that leads to two squared or four possible combinations of truth and falsehood. So we have P is false and Q is false. We have P is false and Q is true. P is true and Q is false. And then P and Q both are true. And those are the only four possibilities for what P and Q could mean.

120:56 And in each of those situations, this third column here, P and Q, is telling us a little bit about what it actually means for P and Q to be true. And we see that the only case where P and Q is true is in this fourth row here, where P happens to be true, Q also happens to be true.

121:13 And in all other situations, P and Q is going to evaluate to false. So this, again, is much in line with what our intuition of and might mean. If I say P and Q, I probably mean that I expect both P and Q to be true. Next up, also potentially consistent with what we mean, is this word or, represented by this V shape, sort of an upside down and symbol.

121:38 And or, as the name might suggest, is true if either of its arguments are true, as long as P is true or Q is true, then P or Q is going to be true. Which means the only time that P or Q is false is if both of its operands are false. If P is false and Q is false, then P or Q is going to be false.

121:59 But in all other cases, at least one of the operands is true. Maybe they're both true, in which case P or Q is going to evaluate to true. Now, this is mostly consistent with the way that most people might use the word or, in the sense of speaking the word or in normal English, though there is sometimes when we might say

122:17 or, where we mean P or Q, but not both, where we mean, sort of, it can only be one or the other. It's important to note that this symbol here, this or, means P or Q or both, that those are totally OK. As long as either or both of them are true, then the or is going to evaluate to be true, as well.

122:36 It's only in the case where all of the operands are false that P or Q ultimately evaluates to false, as well. In logic, there's another symbol known as the exclusive or, which encodes this idea of exclusivity of one or the other, but not both. But we're not going to be focusing on that today.

122:53 Whenever we talk about or, we're always talking about either or both, in this case, as represented by this truth table here. So that now is not an and an or. And next up is what we might call implication, as denoted by this arrow symbol. So we have P and Q. And this sentence here will generally

123:13 read as P implies Q. And what P implies Q means is that if P is true, then Q is also true. So I might say something like, if it is raining, then I will be indoors. Meaning, it is raining implies I will be indoors, as the logical sentence that I'm saying there. And the truth table for this can sometimes be a little bit tricky.

123:38 So obviously, if P is true and Q is true, then P implies Q. That's true. That definitely makes sense. And it should also stand to reason that when P is true and Q is false, then P implies Q is false. Because if I said to you, if it is raining, then I will be out indoors. And it is raining, but I'm not indoors?

124:01 Well, then it would seem to be that my original statement was not true. P implies Q means that if P is true, then Q also needs to be true. And if it's not, well, then the statement is false. What's also worth noting, though, is what happens when P is false. When P is false, the implication makes no claim at all.

124:22 If I say something like, if it is raining, then I will be indoors. And it turns out it's not raining. Then in that case, I am not making any statement as to whether or not I will be indoors or not. P implies Q just means that if P is true, Q must be true. But if P is not true, then we make no claim about whether or not Q

124:42 is true at all. So in either case, if P is false, it doesn't matter what Q is. Whether it's false or true, we're not making any claim about Q whatsoever. We can still evaluate the implication to true. The only way that the implication is ever false is if our premise, P, is true, but the conclusion that we're drawing Q

125:02 happens to be false. So in that case, we would say P does not imply Q in that case. Finally, the last connective that we'll discuss is this bi-conditional. You can think of a bi-conditional as a condition that goes in both directions. So originally, when I said something like, if it is raining,

125:20 then I will be indoors. I didn't say what would happen if it wasn't raining. Maybe I'll be indoors, maybe I'll be outdoors. This bi-conditional, you can read as an if and only if. So I can say, I will be indoors if and only if it is raining, meaning if it is raining, then I will be indoors.

125:40 And if I am indoors, it's reasonable to conclude that it is also raining. So this bi-conditional is only true when P and Q are the same. So if P is true and Q is true, then this bi-conditional is also true. P implies Q, but also the reverse is true. Q also implies P. So if P and Q both happen to be false,

126:01 we would still say it's true. But in any of these other two situations, this P if and only if Q is going to ultimately evaluate to false. So a lot of trues and falses going on there, but these five basic logical connectives are going to form the core of the language of propositional logic,

126:17 the language that we're going to use in order to describe ideas, and the language that we're going to use in order to reason about those ideas in order to draw conclusions. So let's now take a look at some of the additional terms that we'll need to know about in order to go about trying

126:31 to form this language of propositional logic and writing AI that's actually able to understand this sort of logic. The next thing we're going to need is the notion of what is actually true about the world. We have a whole bunch of propositional symbols, P and Q and R and maybe others,

126:47 but we need some way of knowing what actually is true in the world. Is P true or false? Is Q true or false? So on and so forth. And to do that, we'll introduce the notion of a model. A model just assigns a truth value, where a truth value is either true or false, to every propositional symbol.

127:06 In other words, it's creating what we might call a possible world. So let me give an example. If, for example, I have two propositional symbols, P is it is raining and Q is it is a Tuesday, a model just takes each of these two symbols and assigns a truth value to them, either true or false.

127:25 So here's a sample model. In this model, in other words, in this possible world, it is possible that P is true, meaning it is raining, and Q is false, meaning it is not a Tuesday. But there are other possible worlds or other models as well. There is some model where both of these variables are true,

127:42 some model where both of these variables are false. In fact, if there are n variables that are propositional symbols like this that are either true or false, then the number of possible models is 2 to the n, because each of these possible models, possible variables within my model, could be set to either true or false

128:00 if I don't know any information about it. So now that I have the symbols and the connectives that I'm going to need in order to construct these parts of knowledge, we need some way to represent that knowledge. And to do so, we're going to allow our AI access to what we'll call a knowledge base.

128:18 And a knowledge base is really just a set of sentences that our AI knows to be true. Some set of sentences in propositional logic that are things that our AI knows about the world. And so we might tell our AI some information, information about a situation that it finds itself in, or a situation about a problem

128:38 that it happens to be trying to solve. And we would give that information to the AI that the AI would store inside of its knowledge base. And what happens next is the AI would like to use that information in the knowledge base to be able to draw conclusions about the rest of the world.

128:53 And what do those conclusions look like? Well, to understand those conclusions, we'll need to introduce one more idea, one more symbol. And that is the notion of entailment. So this sentence here, with this double turnstile in these Greek letters, this is the Greek letter alpha and the Greek letter beta.

129:09 And we read this as alpha entails beta. And alpha and beta here are just sentences in propositional logic. And what this means is that alpha entails beta means that in every model, in other words, in every possible world in which sentence alpha is true, then sentence beta is also true.

129:32 So if something entails something else, if alpha entails beta, it means that if I know alpha to be true, then beta must therefore also be true. So if my alpha is something like I know that it is a Tuesday in January, then a reasonable beta might be something like I know that it is January.

129:53 Because in all worlds where it is a Tuesday in January, I know for sure that it must be January, just by definition. This first statement or sentence about the world entails the second statement. And we can reasonably use deduction based on that first sentence to figure out that the second sentence is, in fact, true as well.

130:12 And ultimately, it's this idea of entailment that we're going to try and encode into our computer. We want our AI agent to be able to figure out what the possible entailments are. We want our AI to be able to take these three sentences, sentences like, if it didn't rain, Harry visited Hagrid.

130:28 That Harry visited Hagrid or Dumbledore, but not both. And that Harry visited Dumbledore. And just using that information, we'd like our AI to be able to infer or figure out that using these three sentences inside of a knowledge base, we can draw some conclusions. In particular, we can draw the conclusions here that, one,

130:48 Harry did not visit Hagrid today. And we can draw the entailment, too, that it did, in fact, rain today. And this process is known as inference. And that's what we're going to be focusing on today, this process of deriving new sentences from old ones, that I give you these three sentences, you put them

131:04 in the knowledge base in, say, the AI. And the AI is able to use some sort of inference algorithm to figure out that these two sentences must also be true. And that is how we define inference. So let's take a look at an inference example to see how we might actually go about inferring things in a human sense

131:23 before we take a more algorithmic approach to see how we could encode this idea of inference in AI. And we'll see there are a number of ways that we can actually achieve this. So again, we'll deal with a couple of propositional symbols. We'll deal with P, Q, and R. P is it is a Tuesday.

131:38 Q is it is raining. And R is Harry will go for a run, three propositional symbols that we are just defining to mean this. We're not saying anything yet about whether they're true or false. We're just defining what they are. Now, we'll give ourselves or an AI access to a knowledge base,

131:54 abbreviated to KB, the knowledge that we know about the world. We know this statement. All right. So let's try to parse it. The parentheses here are just used for precedent, so we can see what associates with what. But you would read this as P and not Q implies R. All right. So what does that mean?

132:13 Let's put it piece by piece. P is it is a Tuesday. Q is it is raining, so not Q is it is not raining, and implies R is Harry will go for a run. So the way to read this entire sentence in human natural language at least is if it is a Tuesday and it is not raining, then Harry will go for a run.

132:36 So if it is a Tuesday and it is not raining, then Harry will go for a run. And that is now inside of our knowledge base. And let's now imagine that our knowledge base has two other pieces of information as well. It has information that P is true, that it is a Tuesday. And we also have the information not Q, that it is not raining,

132:54 that this sentence Q, it is raining, happens to be false. And those are the three sentences that we have access to. P and not Q implies R, P and not Q. Using that information, we should be able to draw some inferences. P and not Q is only true if both P and not Q are true. All right, we know that P is true and we know that not Q is true.

133:18 So we know that this whole expression is true. And the definition of implication is if this whole thing on the left is true, then this thing on the right must also be true. So if we know that P and not Q is true, then R must be true as well. So the inference we should be able to draw from all of this

133:34 is that R is true and we know that Harry will go for a run by taking this knowledge inside of our knowledge base and being able to reason based on that idea. And so this ultimately is the beginning of what we might consider to be some sort of inference algorithm, some process that we can use to try and figure out

133:53 whether or not we can draw some conclusion. And ultimately, what these inference algorithms are going to answer is the central question about entailment. Given some query about the world, something we're wondering about the world, and we'll call that query alpha, the question we want to ask using these inference algorithms

134:09 is does KB, our knowledge base, entail alpha? In other words, using only the information we know inside of our knowledge base, the knowledge that we have access to, can we conclude that this sentence alpha is true? And that's ultimately what we would like to do. So how can we do that?

134:28 How can we go about writing an algorithm that can look at this knowledge base and figure out whether or not this query alpha is actually true? Well, it turns out there are a couple of different algorithms for doing so. And one of the simplest, perhaps, is known as model checking.

134:43 Now, remember that a model is just some assignment of all of the propositional symbols inside of our language to a truth value, true or false. And you can think of a model as a possible world, that there are many possible worlds where different things might be true or false, and we can enumerate all of them.

134:59 And the model checking algorithm does exactly that. So what does our model checking algorithm do? Well, if we wanted to determine if our knowledge base entails some query alpha, then we are going to enumerate all possible models. In other words, consider all possible values of true and false

135:17 for our variables, all possible states in which our world can be in. And if in every model where our knowledge base is true, alpha is also true, then we know that the knowledge base entails alpha. So let's take a closer look at that sentence and try and figure out what it actually means.

135:34 If we know that in every model, in other words, in every possible world, no matter what assignment of true and false to variables you give, if we know that whenever our knowledge is true, what we know to be true is true, that this query alpha is also true, well, then it stands to reason that as long as our knowledge base is true,

135:53 then alpha must also be true. And so this is going to form the foundation of our model checking algorithm. We're going to enumerate all of the possible worlds and ask ourselves whenever the knowledge base is true, is alpha true? And if that's the case, then we know alpha to be true.

136:09 And otherwise, there is no entailment. Our knowledge base does not entail alpha. All right. So this is a little bit abstract, but let's take a look at an example to try and put real propositional symbols to this idea. So again, we'll work with the same example. P is it is a Tuesday, Q is it is raining, R as Harry will go for a run.

136:29 Our knowledge base contains these pieces of information. P and not Q implies R. We also know P. It is a Tuesday and not Q. It is not raining. And our query, our alpha in this case, the thing we want to ask is R. We want to know, is it guaranteed? Is it entailed that Harry will go for a run?

136:49 So the first step is to enumerate all of the possible models. We have three propositional symbols here, P, Q, and R, which means we have 2 to the third power, or eight possible models. All false, false, false true, false true, false, false true, true, et cetera. Eight possible ways you could assign true and false to all of these models.

137:10 And we might ask in each one of them, is the knowledge base true? Here are the set of things that we know. In which of these worlds could this knowledge base possibly apply to? In which world is this knowledge base true? Well, in the knowledge base, for example, we know P. We know it is a Tuesday, which means we know that these four first four rows

137:32 where P is false, none of those are going to be true or are going to work for this particular knowledge base. Our knowledge base is not true in those worlds. Likewise, we also know not Q. We know that it is not raining. So any of these models where Q is true, like these two and these two here,

137:51 those aren't going to work either because we know that Q is not true. And finally, we also know that P and not Q implies R, which means that when P is true or P is true here and Q is false, Q is false in these two, then R must be true. And if ever P is true, Q is false, but R is also false,

138:15 well, that doesn't satisfy this implication here. That implication does not hold true under those situations. So we could say that for our knowledge base, we can conclude under which of these possible worlds is our knowledge base true and under which of the possible worlds is our knowledge base false.

138:32 And it turns out there is only one possible world where our knowledge base is actually true. In some cases, there might be multiple possible worlds where the knowledge base is true. But in this case, it just so happens that there's only one, one possible world where we can definitively say something about our knowledge base.

138:48 And in this case, we would look at the query. The query of R is R true, R is true, and so as a result, we can draw that conclusion. And so this is this idea of model check-in. Enumerate all the possible models and look in those possible models to see whether or not, if our knowledge base is true,

139:08 is the query in question true as well. So let's now take a look at how we might actually go about writing this in a programming language like Python. Take a look at some actual code that would encode this notion of propositional symbols and logic and these connectives like and and or and not and implication and so forth

139:26 and see what that code might actually look like. So I've written in advance a logic library that's more detailed than we need to worry about entirely today. But the important thing is that we have one class for every type of logical symbol or connective that we might have. So we just have one class for logical symbols, for example,

139:44 where every symbol is going to represent and store some name for that particular symbol. And we also have a class for not that takes an operand. So we might say not one symbol to say something is not true or some other sentence is not true. We have one for and, one for or, so on and so forth.

140:02 And I'll just demonstrate how this works. And you can take a look at the actual logic.py later on. But I'll go ahead and call this file harry.py. We're going to store information about this world of Harry Potter, for example. So I'll go ahead and import from my logic module. I'll import everything.

140:21 And in this library, in order to create a symbol, you use capital S symbol. And I'll create a symbol for rain, to mean it is raining, for example. And I'll create a symbol for Hagrid, to mean Harry visited Hagrid, is what this symbol is going to mean. So this symbol means it is raining.

140:39 This symbol means Harry visited Hagrid. And I'll add another symbol called Dumbledore for Harry visited Dumbledore. Now, I'd like to save these symbols so that I can use them later as I do some logical analysis. So I'll go ahead and save each one of them inside of a variable. So like rain, Hagrid, and Dumbledore, so you could call the variables anything.

141:03 And now that I have these logical symbols, I can use logical connectives to combine them together. So for example, if I have a sentence like and rain and Hagrid, for example, which is not necessarily true, but just for demonstration, I can now try and print out sentence.formula, which

141:22 is a function I wrote that takes a sentence in propositional logic and just prints it out so that we, the programmers, can now see this in order to get an understanding for how it actually works. So if I run python harry.py, what we'll see is this sentence in propositional logic, rain and Hagrid.

141:40 This is the logical representation of what we have here in our Python program of saying and whose arguments are rain and Hagrid. So we're saying rain and Hagrid by encoding that idea. And this is quite common in Python object-oriented programming, where you have a number of different classes,

141:57 and you pass arguments into them in order to create a new and object, for example, in order to represent this idea. But now what I'd like to do is somehow encode the knowledge that I have about the world in order to solve that problem from the beginning of class, where we talked about trying to figure out who Harry visited

142:14 and trying to figure out if it's raining or if it's not raining. And so what knowledge do I have? I'll go ahead and create a new variable called knowledge. And what do I know? Well, I know the very first sentence that we talked about was the idea that if it is not raining, then Harry will visit Hagrid.

142:31 So all right, how do I encode the idea that it is not raining? Well, I can use not and then the rain symbol. So here's me saying that it is not raining. And now the implication is that if it is not raining, then Harry visited Hagrid. So I'll wrap this inside of an implication to say,

142:49 if it is not raining, this first argument to the implication will then Harry visited Hagrid. So I'm saying implication, the premise is that it's not raining. And if it is not raining, then Harry visited Hagrid. And I can print out knowledge.formula to see the logical formula equivalent of that same idea.

143:10 So I run Python of harry.py. And this is the logical formula that we see as a result, which is a text-based version of what we were looking at before, that if it is not raining, then that implies that Harry visited Hagrid. But there was additional information that we had access to as well.

143:27 In this case, we had access to the fact that Harry visited either Hagrid or Dumbledore. So how do I encode that? Well, this means that in my knowledge, I've really got multiple pieces of knowledge going on. I know one thing and another thing and another thing. So I'll go ahead and wrap all of my knowledge inside of an and.

143:45 And I'll move things on to new lines just for good measure. But I know multiple things. So I'm saying knowledge is an and of multiple different sentences. I know multiple different sentences to be true. One such sentence that I know to be true is this implication, that if it is not raining, then Harry visited Hagrid.

144:03 Another such sentence that I know to be true is or Hagrid Dumbledore. In other words, Hagrid or Dumbledore is true, because I know that Harry visited Hagrid or Dumbledore. But I know more than that, actually. That initial sentence from before said that Harry visited Hagrid or Dumbledore,

144:22 but not both. So now I want a sentence that will encode the idea that Harry didn't visit both Hagrid and Dumbledore. Well, the notion of Harry visiting Hagrid and Dumbledore would be represented like this, and of Hagrid and Dumbledore. And if that is not true, if I want to say not that,

144:42 then I'll just wrap this whole thing inside of a not. So now these three lines, line 8 says that if it is not raining, then Harry visited Hagrid. Line 9 says Harry visited Hagrid or Dumbledore. And line 10 says Harry didn't visit both Hagrid and Dumbledore, that it is not true that both the Hagrid symbol and the Dumbledore

145:05 symbol are true. Only one of them can be true. And finally, the last piece of information that I knew was the fact that Harry visited Dumbledore. So these now are the pieces of knowledge that I know, one sentence and another sentence and another and another. And I can print out what I know just to see it a little bit more visually.

145:25 And here now is a logical representation of the information that my computer is now internally representing using these various different Python objects. And again, take a look at logic.py if you want to take a look at how exactly it's implementing this, but no need to worry too much about all of the details

145:40 there. We're here saying that if it is not raining, then Harry visited Hagrid. We're saying that Hagrid or Dumbledore is true. And we're saying it is not the case that Hagrid and Dumbledore is true, that they're not both true. And we also know that Dumbledore is true. So this long logical sentence represents our knowledge base.

146:01 It is the thing that we know. And now what we'd like to do is we'd like to use model checking to ask a query, to ask a question like, based on this information, do I know whether or not it's raining? And we as humans were able to logic our way through it and figure out that, all right, based on these sentences, we can conclude this and that

146:18 to figure out that, yes, it must have been raining. But now we'd like for the computer to do that as well. So let's take a look at the model checking algorithm that is going to follow that same pattern that we drew out in pseudocode a moment ago. So I've defined a function here in logic.py

146:32 that you can take a look at called model check. Model check takes two arguments, the knowledge that I already know, and the query. And the idea is, in order to do model checking, I need to enumerate all of the possible models. And for each of the possible models, I need to ask myself,

146:49 is the knowledge base true? And is the query true? So the first thing I need to do is somehow enumerate all of the possible models, meaning for all possible symbols that exist, I need to assign true and false to each one of them and see whether or not it's still true. And so here is the way we're going to do that.

147:08 We're going to start. So I've defined another helper function internally that we'll get to in just a moment. But this function starts by getting all of the symbols in both the knowledge and the query, by figuring out what symbols am I dealing with. In this case, the symbols I'm dealing with are rain and Hagrid and Dumbledore,

147:24 but there might be other symbols depending on the problem. And we'll take a look soon at some examples of situations where ultimately we're going to need some additional symbols in order to represent the problem. And then we're going to run this check all function, which is a helper function that's basically going to recursively call itself

147:42 checking every possible configuration of propositional symbols. So we start out by looking at this check all function. And what do we do? So if not symbols means if we finish assigning all of the symbols. We've assigned every symbol a value. So far we haven't done that, but if we ever do, then we check.

148:03 In this model, is the knowledge true? That's what this line is saying. If we evaluate the knowledge propositional logic formula using the model's assignment of truth values, is the knowledge true? If the knowledge is true, then we should return true only if the query is true. Because if the knowledge is true, we want the query

148:22 to be true as well in order for there to be entailment. Otherwise, we don't know that there otherwise there won't be an entailment if there's ever a situation where what we know in our knowledge is true, but the query, the thing we're asking, happens to be false. So this line here is checking that same idea

148:38 that in all worlds where the knowledge is true, the query must also be true. Otherwise, we can just return true because if the knowledge isn't true, then we don't care. This is equivalent to when we were enumerating this table from a moment ago. In all situations where the knowledge base wasn't true, all of these seven

148:56 rows here, we didn't care whether or not our query was true or not. We only care to check whether the query is true when the knowledge base is actually true, which was just this green highlighted row right there. So that logic is encoded using that statement there. And otherwise, if we haven't assigned symbols yet,

149:15 which we haven't seen anything yet, then the first thing we do is pop one of the symbols. I make a copy of the symbols first just to save an existing copy. But I pop one symbol off of the remaining symbols so that I just pick one symbol at random. And I create one copy of the model where that symbol is true.

149:34 And I create a second copy of the model where that symbol is false. So I now have two copies of the model, one where the symbol is true and one where the symbol is false. And I need to make sure that this entailment holds in both of those models. So I recursively check all on the model where the statement is true

149:52 and check all on the model where the statement is false. So again, you can take a look at that function to try to get a sense for how exactly this logic is working. But in effect, what it's doing is recursively calling this check all function again and again and again. And on every level of the recursion, we're

150:09 saying let's pick a new symbol that we haven't yet assigned, assign it to true and assign it to false, and then check to make sure that the entailment holds in both cases. Because ultimately, I need to check every possible world. I need to take every combination of symbols and try every combination of true and false

150:28 in order to figure out whether the entailment relation actually holds. So that function we've written for you. But in order to use that function inside of harry.py, what I'll write is something like this. I would like to model check based on the knowledge. And then I provide as a second argument what the query is,

150:46 what the thing I want to ask is. And what I want to ask in this case is, is it raining? So model check again takes two arguments. The first argument is the information that I know, this knowledge, which in this case is this information that was given to me at the beginning. And the second argument, rain, is encoding the idea of the query.

151:07 What am I asking? I would like to ask, based on this knowledge, do I know for sure that it is raining? And I can try and print out the result of that. And when I run this program, I see that the answer is true. That based on this information, I can conclusively say that it is raining, because using this model checking algorithm,

151:27 we were able to check that in every world where this knowledge is true, it is raining. In other words, there is no world where this knowledge is true, and it is not raining. So you can conclude that it is, in fact, raining. And this sort of logic can be applied to a number of different types of problems, that if confronted with a problem where

151:47 some sort of logical deduction can be used in order to try to solve it, you might try thinking about what propositional symbols you might need in order to represent that information, and what statements and propositional logic you might use in order to encode that information which you know.

152:03 And this process of trying to take a problem and figure out what propositional symbols to use in order to encode that idea, or how to represent it logically, is known as knowledge engineering. That software engineers and AI engineers will take a problem and try and figure out how to distill it down

152:19 into knowledge that is representable by a computer. And if we can take any general purpose problem, some problem that we find in the human world, and turn it into a problem that computers know how to solve as by using any number of different variables, well, then we can take a computer that is able to do something

152:35 like model checking or some other inference algorithm and actually figure out how to solve that problem. So now we'll take a look at two or three examples of knowledge engineering and practice, of taking some problem and figuring out how we can apply logical symbols and use logical formulas

152:52 to be able to encode that idea. And we'll start with a very popular board game in the US and the UK known as Clue. Now, in the game of Clue, there's a number of different factors that are going on. But the basic premise of the game, if you've never played it before, is that there are a number of different people.

153:06 For now, we'll just use three, Colonel Mustard, Professor Plumb, and Miss Scarlet. There are a number of different rooms, like a ballroom, a kitchen, and a library. And there are a number of different weapons, a knife, a revolver, and a wrench. And three of these, one person, one room, and one weapon,

153:22 is the solution to the mystery, the murderer and what room they were in and what weapon they happened to use. And what happens at the beginning of the game is that all these cards are randomly shuffled together. And three of them, one person, one room, and one weapon, are placed into a sealed envelope that we don't know.

153:38 And we would like to figure out, using some sort of logical process, what's inside the envelope, which person, which room, and which weapon. And we do so by looking at some, but not all, of these cards here, by looking at these cards to try and figure out what might be going on. And so this is a very popular game.

153:56 But let's now try and formalize it and see if we could train a computer to be able to play this game by reasoning through it logically. So in order to do this, we'll begin by thinking about what propositional symbols we're ultimately going to need. Remember, again, that propositional symbols are just some symbol,

154:13 some variable, that can be either true or false in the world. And so in this case, the propositional symbols are really just going to correspond to each of the possible things that could be inside the envelope. Mustard is a propositional symbol that, in this case, will just be true if Colonel Mustard is inside the envelope,

154:33 if he is the murderer, and false otherwise. And likewise for Plum, for Professor Plum, and Scarlet, for Miss Scarlet. And likewise for each of the rooms and for each of the weapons. We have one propositional symbol for each of these ideas. Then using those propositional symbols, we

154:49 can begin to create logical sentences, create knowledge that we know about the world. So for example, we know that someone is the murderer, that one of the three people is, in fact, the murderer. And how would we encode that? Well, we don't know for sure who the murderer is. But we know it is one person or the second person or the third person.

155:09 So I could say something like this. Mustard or Plum or Scarlet. And this piece of knowledge encodes that one of these three people is the murderer. We don't know which, but one of these three things must be true. What other information do we know? Well, we know that, for example, one of the rooms

155:27 must have been the room in the envelope. The crime was committed either in the ballroom or the kitchen or the library. Again, right now, we don't know which. But this is knowledge we know at the outset, knowledge that one of these three must be inside the envelope. And likewise, we can say the same thing about the weapon,

155:42 that it was either the knife or the revolver or the wrench, that one of those weapons must have been the weapon of choice and therefore the weapon in the envelope. And then as the game progresses, the gameplay works by people get various different cards. And using those cards, you can deduce information.

155:59 That if someone gives you a card, for example, I have the Professor Plum card in my hand, then I know the Professor Plum card can't be inside the envelope. I know that Professor Plum is not the criminal, so I know a piece of information like not Plum, for example. I know that Professor Plum has to be false.

156:18 This propositional symbol is not true. And sometimes I might not know for sure that a particular card is not in the middle, but sometimes someone will make a guess and I'll know that one of three possibilities is not true. Someone will guess Colonel Mustard in the library with the revolver

156:34 or something to that effect. And in that case, a card might be revealed that I don't see. But if it is a card and it is either Colonel Mustard or the revolver or the library, then I know that at least one of them can't be in the middle. So I know something like it is either not Mustard

156:51 or it is not the library or it is not the revolver. Now maybe multiple of these are not true, but I know that at least one of Mustard, Library, and Revolver must, in fact, be false. And so this now is a propositional logic representation of this game of Clue, a way of encoding the knowledge that we

157:11 know inside this game using propositional logic that a computer algorithm, something like model checking that we saw a moment ago, can actually look at and understand. So let's now take a look at some code to see how this algorithm might actually work in practice. All right, so I'm now going to open up a file called Clue.py, which

157:30 I've started already. And what we'll see here is I've defined a couple of things. To find some symbols initially, notice I have a symbol for Colonel Mustard, a symbol for Professor Plum, a symbol for Miss Scarlett, all of which I've put inside of this list of characters. I have a symbol for Ballroom and Kitchen and Library

157:45 inside of a list of rooms. And then I have symbols for Knife and Revolver and Wrench. These are my weapons. And so all of these characters and rooms and weapons altogether, those are my symbols. And now I also have this check knowledge function. And what the check knowledge function does is it takes my knowledge

158:03 and it's going to try and draw conclusions about what I know. So for example, we'll loop over all of the possible symbols and we'll check, do I know that that symbol is true? And a symbol is going to be something like Professor Plum or the Knife or the Library. And if I know that it is true, in other words,

158:20 I know that it must be the card in the envelope, then I'm going to print out using a function called cprint, which prints things in color. I'm going to print out the word yes, and I'm going to print that in green, just to make it very clear to us. If we're not sure that the symbol is true,

158:35 maybe I can check to see if I'm sure that the symbol is not true. Like if I know for sure that it is not Professor Plum, for example. And I do that by running model check again, this time checking if my knowledge is not the symbol, if I know for sure that the symbol is not true. And if I don't know for sure that the symbol is not true,

158:55 because I say if not model check, meaning I'm not sure that the symbol is false, well, then I'll go ahead and print out maybe next to the symbol. Because maybe the symbol is true, maybe it's not, I don't actually know. So what knowledge do I actually have? Well, let's try and represent my knowledge now.

159:12 So my knowledge is, I know a couple of things, so I'll put them in an and. And I know that one of the three people must be the criminal. So I know or mustard, plum, scarlet. This is my way of encoding that it is either Colonel Mustard or Professor Plum or Miss Scarlet. I know that it must have happened in one of the rooms.

159:31 So I know or ballroom, kitchen, library, for example. And I know that one of the weapons must have been used as well. So I know or knife, revolver, wrench. So that might be my initial knowledge, that I know that it must have been one of the people, I know it must have been in one of the rooms,

159:49 and I know that it must have been one of the weapons. And I can see what that knowledge looks like as a formula by printing out knowledge.formula. So I'll run python clue.py. And here now is the information that I know in logical format. I know that it is Colonel Mustard or Professor Plum or Miss Scarlet.

160:06 And I know that it is the ballroom, the kitchen, or the library. And I know that it is the knife, the revolver, or the wrench. But I don't know much more than that. I can't really draw any firm conclusions. And in fact, we can see that if I try and do, let me go ahead and run my knowledge check function on my knowledge.

160:24 Knowledge check is this function that I, or check knowledge rather, is this function that I just wrote that looks over all of the symbols and tries to see what conclusions I can actually draw about any of the symbols. So I'll go ahead and run clue.py and see what it is that I know.

160:42 And it seems that I don't really know anything for sure. I have all three people are maybes, all three of the rooms are maybes, all three of the weapons are maybes. I don't really know anything for certain just yet. But now let me try and add some additional information and see if additional information, additional knowledge,

160:57 can help us to logically reason our way through this process. And we are just going to provide the information. Our AI is going to take care of doing the inference and figuring out what conclusions it's able to draw. So I start with some cards. And those cards tell me something. So if I have the kernel mustard card, for example,

161:16 I know that the mustard symbol must be false. In other words, mustard is not the one in the envelope, is not the criminal. So I can say, knowledge supports something called, every and in this library supports dot add, which is a way of adding knowledge or adding an additional logical sentence to an and clause.

161:35 So I can say, knowledge dot add, not mustard. I happen to know, because I have the mustard card, that kernel mustard is not the suspect. And maybe I have a couple of other cards too. Maybe I also have a card for the kitchen. So I know it's not the kitchen. And maybe I have another card that says that it is not the revolver.

161:54 So I have three cards, kernel mustard, the kitchen, and the revolver. And I encode that into my AI this way by saying, it's not kernel mustard, it's not the kitchen, and it's not the revolver. And I know those to be true. So now, when I rerun clue.py, we'll see that I've been able to eliminate some possibilities.

162:12 Before, I wasn't sure if it was the knife or the revolver or the wrench. If a knife was maybe, a revolver was maybe, wrench is maybe. Now I'm down to just the knife and the wrench. Between those two, I don't know which one it is. They're both maybes. But I've been able to eliminate the revolver, which

162:27 is one that I know to be false, because I have the revolver card. And so additional information might be acquired over the course of this game. And we would represent that just by adding knowledge to our knowledge set or knowledge base that we've been building here. So if, for example, we additionally got the information

162:46 that someone made a guess, someone guessed like Miss Scarlet in the library with the wrench. And we know that a card was revealed, which means that one of those three cards, either Miss Scarlet or the library or the wrench, one of those at minimum must not be inside of the envelope.

163:02 So I could add some knowledge, say knowledge.add. And I'm going to add an or clause, because I don't know for sure which one it's not, but I know one of them is not in the envelope. So it's either not Scarlet, or it's not the library, and or supports multiple arguments. I can say it's also or not the wrench.

163:21 So at least one of those needs a Scarlet library and wrench. At least one of those needs to be false. I don't know which, though. Maybe it's multiple. Maybe it's just one, but at least one I know needs to hold. And so now if I rerun clue.py, I don't actually have any additional information just yet.

163:38 Nothing I can say conclusively. I still know that maybe it's Professor Plum, maybe it's Miss Scarlet. I haven't eliminated any options. But let's imagine that I get some more information, that someone shows me the Professor Plum card, for example. So I say, all right, let's go back here, knowledge.add, not Plum.

163:57 So I have the Professor Plum card. I know the Professor Plum is not in the middle. I rerun clue.py. And right now, I'm able to draw some conclusions. Now I've been able to eliminate Professor Plum, and the only person it could left remaining be i