6-4. Extending Minimax Search

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

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

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

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

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

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

Each agent tries to maximize its own score, so we propagate up the values based on which agent’s move it is. We start with agent 3’s level. Here agent 3 has a choice between a 1 and a 2, so it’ll choose the 2. Then it has a 3 and a 4, so it’ll choose … Read more

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.

Here’s the answer. We can prune these nodes and these branches. The final answer is 5.2.

What nodes can be pruned in this probabilistic game tree? Check the boxes for nodes or even full branches that could be pruned. Then find expected values of each remaining node. You can enter an exact number or a range, like less than or equal to 4.

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

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