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