9 – Testing Evaluation Functions

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

8 – Testing the Evaluation Function Part 2 Solution

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

7 – Testing the Evaluation Function Part 2

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

30 – Thad’s Asides

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

3 – Depth-Limited Search

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

29 – Solving 5×5 Isolation

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

28 – Alpha-Beta Pruning Quiz 2 Solution

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

27 – Alpha-Beta Pruning Quiz 2

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

26 – Alpha-Beta Pruning Quiz 1 Solution

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

24 – Alpha-Beta Pruning

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

23 – Evaluating Evaluation Functions

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

22 – Good Evaluation Functions Solution

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

21 – Good Evaluation Functions

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

2 – Minimax Quiz Solution

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

19 – Horizon Effect

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