Minimax with a method search that applies the minimax algorithm of the text to find winning strategies for games. Also define classes of states for games as defined below.
Game states are to be represented using the same representation as in Assignment 1, except that you needn't define an estimator. Instead, you need to define a boolean-valued findValue method that returns true if a goal state (that is, a terminal state) is a winning state for the player whose move it is, and false otherwise. You may assume that games cannot end in a tie. The findValue method may return any value if it is invoked on a state that is not a goal state. This change has been reflected in the State interface provided to you for this assignment -- that is, the State interface now contains a findValue method instead of an Estimator method. All of the game states that you define must implement the new State interface.
In the Minimax class, your search method may assume that all state spaces are finite and-or trees, so that no estimator is necessary, and so that detecting repeated states is not strictly necessary. It may also assume that all goal states are worth the same value to the winning player, so that the findValue method returns all that's worth knowing about a goal state.
The search method is to take a state as argument, and return a winning strategy for the first player in the form of an and-or tree. If there is no winning strategy for the first player, then the method is to return null.
Your search algorithm should use short circuit evaluation (the analog of alpha-beta pruning) to avoid generating states that can't be part of a winning strategy.
An and-or tree is simply an ordered tree, where each node is either an and node or an or node. A simple implementation is available from the class web site. Typically and nodes and or nodes appear on alternating levels, although this is not required by the definition and the implementation does not enforce this constraint. However the and-or trees returned by search should have this property. To interpret an and-or tree as a strategy for the first player, that player may choose any child of an or node, but must deal with all children of an and node. So from the first player's point of view, the root is an or node.
You may check your search method on the OneOrTwoState class that is available on the class web site. The game simply begins with a pile of sticks of a given size, and players alternate taking exactly one or two sticks from the pile. The player who takes last stick, thus leaving an empty pile, is the winner. Note that states don't represent whose move it is; the states that you define need not represent this information either. Also note that a winning strategy for this game is to leave, if possible, a number of sticks that is a multiple of 3.
As in Assignment 1, your state classes will need a version of the toString method that is more informative than the one that is inherited from the Object class, so that the winning strategy can be deduced by a human from the solution tree.
The arguments that each constructor needs should be clear from the description below of the corresponding problem; you may also look at the test class A2.java to double check.
Please use Java 5.0 for this assignment, if at all possible. I will also accept submissions in Scheme, but in this case you are responsible for translating the Java code that I am providing into Scheme.
For the given problems I am primarly concerned that you can use the minimax algorithm. I am less concerned about having the most efficient possible implementation for states, so I will deduct for inefficiency only in the case of gross inefficiency.
As always, any of your Java classes may have extra methods or variables in addition to those that are required by the assignment.
You are to test your program with the test class A2.java available from the class web site. You are to turn in both hard and soft copies of all of your code (but not A2.java, unless you modify it) as well as a hard copy of the results of your testing. Your code should include the Minimax class as well as the three classes that are described below with their corresponding problems. The Minimax class is worth 40 points; the others are worth 20 points each. Instructions for turning in the soft copy of your code will be given in class.
OneOrTwoState, except that the player who takes the last stick loses.
Note that the following is a winning strategy for Nim, whenever it is possible: after your move, make sure that the sizes of the three piles, represented in binary, have an even number of 1 bits in each bit position. So for example, leaving piles of sizes 3, 2, and 1 would be consistent with this strategy, since the bit representations 11, 10, and 1 would have 2 1's in each bit position. But leaving piles of sizes 9, 8 and 3 would not be, since the bit representations 1001, 1000, and 11 would together have only a single 1 in the second position from the right.