My noughts and crosses program finally works!

Oh the euphoria which strikes the programmer when that final bug has been defeated and the program actually works!

It's been a long road: the philosophical meditation, the success implementing a random opponent and finally getting the minimax player to work.

And it's as cunning as a fox!

My previous post has the boring, but necessary code. Be impressed.

My next project is this Israeli Resolution Theorem Prover - to thoroughly understand it, and bend it to my will.

---

Noughts and crosses seems such a simple game. But it's anything but when your game-strategy is tree search.

Take this board position, X to move.

CL-USER 5 >    (setf b '(X 1 2 3 X 5 O 7 O))

(X 1 2 3 X 5 O 7 O)

CL-USER 6 >    (print-board b)

     X | 1 | 2
     3 | X | 5
     O | 7 | O

Plainly X has to move to 7, otherwise it's game over. If X does so, and O incompetently fails to move to 1, then X wins. Otherwise, it's mostly a draw.

---

Here is what the minimax algorithm (playing X) produces from:

CL-USER 7 >   (setf mx-tree (txminimax (xtree 'X 'X (mknode b 9 T) *depth*) t) )

CL-USER 8 >  (pprint mx-tree)

This tree:

(((X 1 2 3 X 5 O 7 O) 9 0)
 ((((X X 2 3 X 5 O 7 O) 1 -32)
   ((((X X O 3 X 5 O 7 O) 2 32)
     ((((X X O X X 5 O 7 O) 3 -32)
       ((((X X O X X O O 7 O) 5 -32) NIL) (((X X O X X 5 O O O) 7 -32) NIL)))
      (((X X O 3 X X O 7 O) 5 -32)
       ((((X X O O X X O 7 O) 3 0) NIL) (((X X O 3 X X O O O) 7 -32) NIL)))
      (((X X O 3 X 5 O X O) 7 32) NIL)))
    (((X X 2 O X 5 O 7 O) 3 32)
     ((((X X X O X 5 O 7 O) 2 32) NIL)
      (((X X 2 O X X O 7 O) 5 -32)
       ((((X X O O X X O 7 O) 2 0) NIL) (((X X 2 O X X O O O) 7 -32) NIL)))
      (((X X 2 O X 5 O X O) 7 32) NIL)))
    (((X X 2 3 X O O 7 O) 5 32)
     ((((X X X 3 X O O 7 O) 2 32) NIL)
      (((X X 2 X X O O 7 O) 3 -32)
       ((((X X O X X O O 7 O) 2 -32) NIL) (((X X 2 X X O O O O) 7 -32) NIL)))
      (((X X 2 3 X O O X O) 7 32) NIL)))
    (((X X 2 3 X 5 O O O) 7 -32) NIL)))
  (((X 1 X 3 X 5 O 7 O) 2 -32)
   ((((X O X 3 X 5 O 7 O) 1 0)
     ((((X O X X X 5 O 7 O) 3 -32)
       ((((X O X X X O O 7 O) 5 -2) NIL) (((X O X X X 5 O O O) 7 -32) NIL)))
      (((X O X 3 X X O 7 O) 5 -32)
       ((((X O X O X X O 7 O) 3 -2) NIL) (((X O X 3 X X O O O) 7 -32) NIL)))
      (((X O X 3 X 5 O X O) 7 0)
       ((((X O X O X 5 O X O) 3 0) NIL) (((X O X 3 X O O X O) 5 0) NIL)))))
    (((X 1 X O X 5 O 7 O) 3 32)
     ((((X X X O X 5 O 7 O) 1 32) NIL)
      (((X 1 X O X X O 7 O) 5 -32)
       ((((X O X O X X O 7 O) 1 -2) NIL) (((X 1 X O X X O O O) 7 -32) NIL)))
      (((X 1 X O X 5 O X O) 7 0)
       ((((X O X O X 5 O X O) 1 0) NIL) (((X 1 X O X O O X O) 5 4) NIL)))))
    (((X 1 X 3 X O O 7 O) 5 32)
     ((((X X X 3 X O O 7 O) 1 32) NIL)
      (((X 1 X X X O O 7 O) 3 -32)
       ((((X O X X X O O 7 O) 1 -2) NIL) (((X 1 X X X O O O O) 7 -32) NIL)))
      (((X 1 X 3 X O O X O) 7 0)
       ((((X O X 3 X O O X O) 1 0) NIL) (((X 1 X O X O O X O) 3 4) NIL)))))
    (((X 1 X 3 X 5 O O O) 7 -32) NIL)))
  (((X 1 2 X X 5 O 7 O) 3 -32)
   ((((X O 2 X X 5 O 7 O) 1 32)
     ((((X O X X X 5 O 7 O) 2 -32)
       ((((X O X X X O O 7 O) 5 -2) NIL) (((X O X X X 5 O O O) 7 -32) NIL)))
      (((X O 2 X X X O 7 O) 5 32) NIL)
      (((X O 2 X X 5 O X O) 7 -2)
       ((((X O O X X 5 O X O) 2 0) NIL) (((X O 2 X X O O X O) 5 -2) NIL)))))
    (((X 1 O X X 5 O 7 O) 2 32)
     ((((X X O X X 5 O 7 O) 1 -32)
       ((((X X O X X O O 7 O) 5 -32) NIL) (((X X O X X 5 O O O) 7 -32) NIL)))
      (((X 1 O X X X O 7 O) 5 32) NIL)
      (((X 1 O X X 5 O X O) 7 -32)
       ((((X O O X X 5 O X O) 1 0) NIL) (((X 1 O X X O O X O) 5 -32) NIL)))))
    (((X 1 2 X X O O 7 O) 5 -32)
     ((((X X 2 X X O O 7 O) 1 -32)
       ((((X X O X X O O 7 O) 2 -32) NIL) (((X X 2 X X O O O O) 7 -32) NIL)))
      (((X 1 X X X O O 7 O) 2 -32)
       ((((X O X X X O O 7 O) 1 -2) NIL) (((X 1 X X X O O O O) 7 -32) NIL)))
      (((X 1 2 X X O O X O) 7 -32)
       ((((X O 2 X X O O X O) 1 -2) NIL) (((X 1 O X X O O X O) 2 -32) NIL)))))
    (((X 1 2 X X 5 O O O) 7 -32) NIL)))
  (((X 1 2 3 X X O 7 O) 5 -32)
   ((((X O 2 3 X X O 7 O) 1 32)
     ((((X O X 3 X X O 7 O) 2 -32)
       ((((X O X O X X O 7 O) 3 -2) NIL) (((X O X 3 X X O O O) 7 -32) NIL)))
      (((X O 2 X X X O 7 O) 3 32) NIL)
      (((X O 2 3 X X O X O) 7 0)
       ((((X O O 3 X X O X O) 2 2) NIL) (((X O 2 O X X O X O) 3 0) NIL)))))
    (((X 1 O 3 X X O 7 O) 2 32)
     ((((X X O 3 X X O 7 O) 1 -32)
       ((((X X O O X X O 7 O) 3 0) NIL) (((X X O 3 X X O O O) 7 -32) NIL)))
      (((X 1 O X X X O 7 O) 3 32) NIL)
      (((X 1 O 3 X X O X O) 7 2)
       ((((X O O 3 X X O X O) 1 2) NIL) (((X 1 O O X X O X O) 3 2) NIL)))))
    (((X 1 2 O X X O 7 O) 3 0)
     ((((X X 2 O X X O 7 O) 1 -32)
       ((((X X O O X X O 7 O) 2 0) NIL) (((X X 2 O X X O O O) 7 -32) NIL)))
      (((X 1 X O X X O 7 O) 2 -32)
       ((((X O X O X X O 7 O) 1 -2) NIL) (((X 1 X O X X O O O) 7 -32) NIL)))
      (((X 1 2 O X X O X O) 7 0)
       ((((X O 2 O X X O X O) 1 0) NIL) (((X 1 O O X X O X O) 2 2) NIL)))))
    (((X 1 2 3 X X O O O) 7 -32) NIL)))
  (((X 1 2 3 X 5 O X O) 7 0)
   ((((X O 2 3 X 5 O X O) 1 0)
     ((((X O X 3 X 5 O X O) 2 0)
       ((((X O X O X 5 O X O) 3 0) NIL) (((X O X 3 X O O X O) 5 0) NIL)))
      (((X O 2 X X 5 O X O) 3 -2)
       ((((X O O X X 5 O X O) 2 0) NIL) (((X O 2 X X O O X O) 5 -2) NIL)))
      (((X O 2 3 X X O X O) 5 0)
       ((((X O O 3 X X O X O) 2 2) NIL) (((X O 2 O X X O X O) 3 0) NIL)))))
    (((X 1 O 3 X 5 O X O) 2 32)
     ((((X X O 3 X 5 O X O) 1 32) NIL)
      (((X 1 O X X 5 O X O) 3 -32)
       ((((X O O X X 5 O X O) 1 0) NIL) (((X 1 O X X O O X O) 5 -32) NIL)))
      (((X 1 O 3 X X O X O) 5 2)
       ((((X O O 3 X X O X O) 1 2) NIL) (((X 1 O O X X O X O) 3 2) NIL)))))
    (((X 1 2 O X 5 O X O) 3 32)
     ((((X X 2 O X 5 O X O) 1 32) NIL)
      (((X 1 X O X 5 O X O) 2 0)
       ((((X O X O X 5 O X O) 1 0) NIL) (((X 1 X O X O O X O) 5 4) NIL)))
      (((X 1 2 O X X O X O) 5 0)
       ((((X O 2 O X X O X O) 1 0) NIL) (((X 1 O O X X O X O) 2 2) NIL)))))
    (((X 1 2 3 X O O X O) 5 32)
     ((((X X 2 3 X O O X O) 1 32) NIL)
      (((X 1 X 3 X O O X O) 2 0)
       ((((X O X 3 X O O X O) 1 0) NIL) (((X 1 X O X O O X O) 3 4) NIL)))
      (((X 1 2 X X O O X O) 3 -32)
       ((((X O 2 X X O O X O) 1 -2) NIL) (((X 1 O X X O O X O) 2 -32) NIL)))))))))

All to conclude that:

CL-USER 9 >    (setf nodes (mapcar #'car (tree-children mx-tree)))

(((X X 2 3 X 5 O 7 O) 1 -32) ((X 1 X 3 X 5 O 7 O) 2 -32) ((X 1 2 X X 5 O 7 O) 3 -32) ((X 1 2 3 X X O 7 O) 5 -32) ((X 1 2 3 X 5 O X O) 7 0))

CL-USER 10 >    (pprint nodes)

(((X X 2 3 X 5 O 7 O) 1 -32)
 ((X 1 X 3 X 5 O 7 O) 2 -32)
 ((X 1 2 X X 5 O 7 O) 3 -32)
 ((X 1 2 3 X X O 7 O) 5 -32)
 ((X 1 2 3 X 5 O X O) 7 0))

CL-USER 11 >    (choose-mx-move mx-tree)

7

Yep, it successfully searched that whole tree to discover that any move other than 7, it's toast.

Plainly whatever toddlers are doing in their little infant brains, it's not minimax ...