Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Game Playing
Exercise 1. Adversarial search
Why does search in game playing programs always proceed forward from the current position rather than
backward from the goal?
Exercise 2 (Homework). Minimax and alpha-beta
Consider the following game in which the evaluation function values for the MAX player are shown at the
leaf nodes. MAX wants to maximize the evaluation function, while its opponent MIN wants to minimize
the same evaluation function. The first player is MAX, and hence the root node corresponds to MAX.
a) In the figure above, fill in the backed-up values that are computed by the minimax algorithm for all the
nodes. Show with an arrow the move that MAX should choose.
b) Assume that we now use the alpha-beta algorithm and that the children are visited left-to-right (i.e. in
normal order). In the following figure, show all intermediate bounding values at each node as they get
updated and cross all the branches that would be pruned. (Make sure you cross out branches, not nodes!)
Show with an arrow the move that MAX should choose.
Exercise 3. Alpha-beta algorithm
Consider the following game tree where MAX is the first player. The evaluation values from the first
player’s point of view are shown below the leaves.
a) Assume that the nodes are examined in normal order, i.e. left-to-right. Compute the final backed-
up values using the alpha-beta algorithm and show your answer by writing the intermediate and
final values at the nodes in the tree. Show with an arrow the move the first player should choose.
b) The same question as a) but now assume that the nodes are examined in right-to-left order.
Exercise 4. Minimax applied to 3-player games
Consider a 3-player, perfect information game with 3 players, A, B, C. Based on the information specific
to each player, we have 3 specific evaluation functions, fA, fB, fC associated with each player respectively.
These functions indicate the estimated value of a board position with respect to that player. For example
fA(n) = -5 means that position n is not good for player A, whereas fA(n)=100 means that position n looks
very good for player A.
Consider the following game tree, where each triplet at the leaf nodes represents (fA, fB, fC). Backup the
values for each player’s turn using minimax and show the optimal move for player A.