6-1. Search in Multiagent Domains

In order to propagate wins and losses up the game tree, to the point where a computer player can make a decision, we need to start at the bottom of the tree. Let’s start with the left side of the tree. In the left-most branch, O wins. In the next branch over, O never gets … Read more

With terminal node in our game tree. With a +1 if our computer player wins and a -1 if it loses. We’ve used squares to indicate the terminal nodes and put their scores inside them. We are going to assume that our opponent x is really smart and will always play to win. In other … Read more

In most situations in this game tree our computer player O wins. But in a few situations,the game ends with our opponent X winning at level five. If our computer player makes a poor choice for its first move, X can win no matter what O does. Clearly we never want our computer player to … Read more

Let’s keep expanding the nodes in order until we have fully expanded level three of our tree. As we see, some nodes have two children, others have three. Even so, we see that the exponential growth of the children makes it increasingly difficult to display the full tree on the screen at once. In level … Read more

Okay, so remember that the pieces can move like a queen in chess, but can not pass through positions that have been previously played. Also, when a piece is moved it doesn’t leave a trail like the game snake, but just the last position is marked as impassable. So here are those resulting child nodes. … Read more

Shelly, why don’t we have a quick quiz on isolation? >> Sure. So for each of these board states, assuming it’s O’s turn, select the valid positions to which O can move

Now let’s use a simple two by three version of isolation to illustrate how to make a game tree that shows all the moves possible during a game. We will use this game tree to select moves which give the best guarantee of winning. Consider any field spot on the game board as unavailable. We … Read more

Okay, after playing with five by five isolation for a bit. The average branching factor seems to be about 8. So we now get an estimate of 8 to the 25th nodes. >> That’s about 10 to the 22nd nodes. >> Great, that means we only have to wait for around 1.2 million years to … Read more

Let’s dive in and start with something fun. Let’s teach you the rules of isolation, the example game we will be using. Shelly and I will play a game of isolation on a five by five board. I’ll be O and move first. O gets to place its piece anywhere on the game board. I’ll … Read more

What if we do average branching factor instead? >> That sounds like a good idea but, how do we do that? >> Just try it out. >> Sure, why not? I always say do the simple thing first and only add intelligence when necessary. Let’s write a quick computer game player that moves randomly and … Read more

We can approximate the number of nodes MINIMAX will need to visit using the formula b to the power of d.

How many nodes do you think the Minimax algorithm will need to visit in the game tree? Here’s some choices where b is the average branching factor, and d is the average depth. So we have bd, d to the power of b, d squared, and b to the power of d. Pick what you … Read more

While the center position has 16 spaces in which it can move, most other positions have 12 or less. As the game plays, we will have less and less spaces our player can move. >> That means we can make a better estimate on how many nodes we have right? >> Yep, okay, we know … Read more

Assuming that the opponent is not in the way, the center position has a maximum potential moves with 16. Two vertically up. Two diagonally to the right. Two horizontally to the right. Two diagonally down to the right. Two down vertically. Two diagonally down to the left. Two to the left horizontally. And two diagonally … Read more

Select the position on the board with the maximum number of options to move next once the piece is limited to moving like a queen in chess. In other words, the third move in the game. Assume that the first move would not block you.

So far we’ve worked with an isolation board with only five possible moves. In searching to end game caused huge game trees that were hard to show on the screen. How bad will it get with an interesting game board? Well let’s pull up the five by five board Shelly and I were playing on. … Read more

Thanks, Shelly. Now we can see that our computer player loses in only two branches, assuming otherwise perfect play. All our computer player has to do is choose any of the other branches and it will win.

Here are the rest of the values for the tree. [BLANK_AUDIO]

Shelly, I think I’ve talked for too long. It seems time for a quiz. >> I agree, so Thad filled in the left side of this tree, try to fill in the rest of the values on the right side.

Your goal in this lesson is to design an AI that is smarter than yourself. At least in playing a real game. Now granted, a single game is a very limited context. But making a program that can play a game better than you can is an exciting introduction to AI. It’s the way I … Read more