Due: Wednesday, April 15th at the beginning of class

Problem 1: Compute the minimax value of each node in the tree below. Squares represent max nodes and circles represent min nodes.

Problem 2: Show the operation of alpha-beta pruning on the tree shown below. Show the (alpha, beta) windows passed to each node as the tree is traversed, the values returned from each node, and which branches are pruned.

Problem 3: Show the operation of negascout on the tree from Problem 2. Show the (alpha, beta) window passed to each node, the values returned from each node, and which branches are pruned.

Problem 4: Repeat Problem 3, but change the 6 in the next-to-last leaf to 10.

Problem 5: Kismet is a dice game similar to Yahtzee. Examine the rules of Kismet and determine the information that affects strategy, assuming that the goal is to maximize one's average score over many games. Try to keep your information to as little as necessary.

Problem 6: Consider the following game: the player flips two dimes with different dates and then has the option of reflipping none, one, or both. After the reflip, if both dimes are tails then the player wins the dimes back plus a nickel. Otherwise the player wins the newest dime that shows heads. Draw the graph for this game (use a whole sheet of paper to make the drawing more clear) and determine the average winnings when following the optimal strategy for this game.