9 – Sloppy Isolation Expectimax

Let’s use a simple six move isolation game board to illustrate the ideas. We’ll add green circles to show probability nodes. It’s O’s turn and it has four possible moves. The first node we’ll explore is the one where O tries to go to the left most top position. But if it tries, it will … Read more

8 – Sloppy Isolation

To show how probabilistic games work, I’ve invented a version of isolation called Sloppy Isolation. In this game, players may not actually move where they intended. For example, if our player is trying to go to here, it only has an 80% chance of hitting the square intended. There’s a 10% chance the player will … Read more

7 – Probabilistic Games

What if I want to make a computer player for a stochastic game, like Backgammon? >> Well, in Backgammon, your moves are limited each turn based on the roles of two dice. Since you can’t know the result of the dice ahead of time, it would seem at first that you can’t do a game-tree … Read more

6 – 3-Player MAX-MAX-MAX Pruning Solution

Here’s the answer. The first branch on the left is simple. We pick the option where player two has the best score. On the middle branch, we’ll start with the first leaf node on the left. Player two is only concerned with maximizing their own score. So we know they will choose a node where … Read more

5 – 3-Player MAX-MAX-MAX Pruning

Fill in the value ranges for this three player game tree and select which branches an be pruned. The maximum combined score is 9. In this situation that means that the sum of all three scores is less than or equal to 9. Since we are using alpha beta, you can enter an exact number … Read more

4 – 3-Player Alpha-Beta Pruning

The next question is whether alpha beta can work with multi-player games. >> Well according to a paper by Korff, pruning can work as long as sum of the values the players’ evaluation functions has an upper bound and each player’s value, you have lower bound. >> Well for our number of mine moves evaluation … Read more

2 – 3-Player Games Quiz

Fill in the values of this three-player game tree, which alternates levels between players. The values of each node are in the order, player one score, player two score, and player three score. Each agent tries to maximize their own score, so will propagate up the values based on which agent’s move it is.

10 – Expectimax Alpha-Beta Pruning

At the beginning of this section, we gave a challenge question. Let’s go over it carefully now. The leftmost branch’s value is calculated by multiplying 0.1 times the minimum value which is 8, plus 0.5 times the minimum value of the next branch, which is 5, plus 0.4 times 8. The sum of that is … Read more

1 – 3-Player Games

What about three player games like 3-player isolation? >> What’s 3-player isolation? >> It’s the same as normal isolation, but with three players trying to be the last to move. >> So do the players form alliances against each other? >> They can, but there can be only one winner in the end. >> That … Read more

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