Wednesday, January 25, 2017

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 ...

1 comment:

  1. So is it : "Minimax Depth 4 solves 3X3 noughts and crosses" but Depth 3 might not? The "Infant's Brain" Challenge, of course, is to determine how they can succeed without calculating a complete tree/solution. Although there are errors, in general settings the (advanced) Infant performance is superior... I am not sure that ANNs are really helping understand this, as you remarked after that earlier book review.

    ReplyDelete

Comments are moderated. Keep it polite and no gratuitous links to your business website - we're not a billboard here.