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
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