6-2. Optimizing Minimax Search

Remember when we had our simple five-move isolation board? And we searched it to end-game? We found that player one would always win unless it moved to one of the center positions first. >> I see where you’re going. The question is whether our evaluation function of #my_moves predicts which branches will lead to a … Read more

So, here are the values that I got. There’s not much variation here, but there’s a number of good choices. You can see three branches that have a value of 2. Our computer player will take the one on the left automatically, so we’ll probably take this move to start with

Now try filling out the values for the entire Minimax tree. Again, using the number of my moves evaluation function. Propagate the numbers to the top of the Minimax tree. Since we can’t fit the entire level three tree here, we’ll use this abbreviated version instead. A link to the full tree has been provided … Read more

The bottom level is easy to compute. It’s just the number of moves available to player O. Then the second level from the bottom is a max level. So, we take the max at each branch here. Then the top level of the subtree is the min level and we end up with a 2.

For this mini max sub-tree, fill in the values. Assuming an evaluation function of number of my moves or the number of moves possible for player O. Fill in the numbers starting at the bottom and then propagate them up to the top of the tree.

Okay, great, but what do we do when we get to level nine in our mini-max tree? >> That’s when things really get interesting. We want to evaluate the goodness of a node at level nine based on how much we expect it to lead to a win for our computer player. Can we create … Read more

Many problems in artificial intelligence are exponential in time or space, or both. In fact, NP hard problems are so common in AI that researchers joke half seriously that AI is the study of finding clever hacks to exponential problems. Often when a clever hacker is finally found, or when computers finally get fast enough … Read more

Waiting for a computer game player to make a turn is no fun. After two seconds of waiting, a human player is likely to start thinking of other things. We really need a way to choose a move quickly. >> Well, we can’t search to end game but how can we search? >> Let’s assume … Read more

Let me introduce a special guest student from a previous class, Malcolm Haynes. Hi Malcolm. >> Hi Thad. >> When working on the five by five isolation game in the class, you believed you managed to search to end game. >> That’s right. But when we talked about branching factor earlier, we said it would … Read more

Here’s the answer. We haven’t made any changes to the left side of the tree, so as before, the same 4 node will be pruned. On the right side, you can see that we’ve switched the two branches. We evaluated this branch and got a 4, so we know that in the min node above, … Read more

Let’s consider the same tree as the previous quiz. Is there a way to re-order the leaf nodes of the tree in order to prune as many nodes as possible? You’ll find a link to the original version in the instructor notes below this video. Refer to that tree and fill in the values here … Read more

Here we can print this node right here. If we only knew the 11, this max level here would be 11 or greater. However, even if the value was greater than 11, the next node up would still take the five senses of mean level. That means that we actually don’t need to check the … Read more

Now that we’ve filled in the tree, which nodes can be pruned with Alpha-Beta? So go through and click any of the check boxes for nodes or branches that you think would be pruned by the Alpha-Beta algorithm.

Alpha-beta is a pruning technique that allows us to ignore whole sections of the game tree, but still get the same answer as with minimax. >> So you’re saying that alpha-beta never changes the answer, but is more efficient than minimax? >> Precisely, often it is much more efficient. Let’s take another look at the … Read more

Let’s talk about a different evaluation function. Let’s use number of #my_moves minus the number of my #opponents_moves. I really like variants of this function for simple isolation games. The point of isolation is to illuminate the opponent’s moves. #my_moves- #opponents_moves causes the computer player to seek moves with the most options while trying to … Read more

The number of opponent moves would actually do the opposite of what we want. It would label boards as good where our opponent has a large number of moves when we actually want to isolate them and prevent them from moving. Number of squares remaining doesn’t reflect the goodness of the board. It’s constantly decreasing … Read more

Now let’s think about some other potential evaluation functions for isolation. Here we have some options. Number of opponent_moves. So similar to the number of my_moves, this is the number of moves your opponent has available. Number of squares_remaining, which is the number of empty squares left on the board. Number of squares_remaining minus number … Read more

So what do we do? >> Well, perhaps we should include a check in the evaluation function to see if a partition is formed by the next move. And if so, start counting the number of moves left to each player. >> That sounds like a good idea, but how much is it going to … Read more

Here’s the answer. We’ll start at the bottom and propagate the bottoms up. The first level from the bottom is a max level, so we’ll take the max of each of our leaf nodes. Next, we have a min level, so we’ll take the min of each of the values we just found. Finally, the … Read more

One remaining challenge in making our computer player are situations where it is obvious to a human player that the game will be decided in the next move, but that the computer player cannot search far enough into the future to figure out the problem. This situation is called the horizon effect. Take a look … Read more