Why your state sequence might be different and how you can check it ------------------------------------------------------------------- (Nim and Coin-strip examples are below) The reason that your sequence of states for a game may be different than mine is because for a given state, there may be multiple moves which are optimal. Which one you select will determine the sequence of states returned. For example, suppose you do a minimax search on the Nim state '(1 1). Max will lose this game. The children of this node are (0 1) and (1 0). Both will evaluate to -1. If you examine them in the order that I just gave them, and you take the first lowest value (i.e. you don't update the "best move" unless a move is better, rather than updating if "as good or better"), then your procedure will return: (-1 ((0 0) ((0 1) ((1 1) ())))) another valid (optimal) game played from the same start state is: (-1 ((0 0) ((1 0) ((1 1) ())))) One way you can check your answer is that every state in the sequence returned should have the same value if you run a minimax search on that state. However, remember that the players switch --- minimax on (1 1) should return -1, but minimax on (0 1) or (1 0) should return +1. You'll have to convert this value so that it is consistent with the perspective of the same player. I suppose that this is not a completely foolproof method because if there is an error in your evaluation function, then your answer could look consistent but would still be wrong. For the Nim and Coin-strip games, it should be pretty easy to detect if your evaluation function is incorrect. Don't forget that you can play against your minimax procedure using the play-nim or play-coin functions. There are start states for these games where one player, if playing optimally, can always win. (minimax '(1 4 2) nim-gc nim-end?) Evaluated 1047 children. ;Value 1: (1 ((0 0 0) ((0 2 0) ((0 3 0) ((0 4 0) ((1 4 0) ((1 4 2) ()))))))) (minimax '(2 3 3 2) nim-gc nim-end?) Evaluated 248098 children. ;Value 2: (-1 ((0 0 0 0) ((0 0 0 1) ((0 0 1 1) ((0 0 3 1) ((0 1 3 1) ((0 3 3 1) ((1 3 3 1) ((1 3 3 2) ((2 3 3 2) ())))))))))) (minimax '(5 5) nim-gc nim-end?) Evaluated 9230 children. ;Value 3: (-1 ((0 0) ((0 2) ((0 3) ((0 4) ((1 4) ((1 5) ((2 5) ((4 5) ((5 5) ())))))))))) (minimax '(2 4 6 8) coin-gc coin-end?) Evaluated 8453 children. ;Value 4: (-1 ((1 2 3 4) ((1 2 3 5) ((1 2 4 5) ((1 2 4 6) ((1 2 5 6) ((1 2 5 7) ((1 2 6 7) ((1 2 6 8) ((1 3 6 8) ((1 4 6 8) ((2 4 6 8) ())))))))))))) (minimax '(2 8) coin-gc coin-end?) Evaluated 255 children. ;Value 5: (1 ((1 2) ((1 3) ((2 3) ((2 8) ()))))) (minimax '(3 4) coin-gc coin-end?) Evaluated 12 children. ;Value 6: (-1 ((1 2) ((1 3) ((2 3) ((2 4) ((3 4) ()))))))