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