Friday, November 16, 2012

tic-tac-toe

My daughters have made a little tic-tac-toe game.  Its a little 3x3 board, played with 3 coloured stones each.  You take turns to place stones and try and get 3-in-a-row, as in tic-tac-toe.  But when you make your forth move onwards, as you have only three stones, you move a stone…

And, as I was playing against them, I began to brute-force it in my head…  well, you would too!

Of course I had difficulty stopping thinking about this little game, and ended up seeking closure by implementing a Python solver in my lunch-break.

It was very clensing coding.  Its nice to return to noddy, pure problems sometimes.  My biggest hurdle was making sure I canonicalise the board so that rotations and mirrorings are not mistaken for new positions.  I opted for a simple generator that produced all mirrorings and rotations and simply checked to see if any of them had been seen before.

My code run first time!  No typos, and seeming to be doing what I wanted, and from random inspection of outputted board positions to next moves, it seemed correct.

There are 744 boards and 4361 moves.

But how would you visualise it?  Sounds like a job for graphviz!  It was simplicity itself to just change my printouts to print a dot file instead.

And then dot chewed on it for half an hour and then seg-faulted.

I tried other graphviz tools (which treat the graph as undirected), but was unhappy with their output:

I asked for help on StackOverflow.

And a chap kindly showed me a zoomed-out layout that works:

At that ridiculous zoom, there’s a definite pattern there…

Only problem is, whilst I can get graphviz to generate that chart, I can’t view it!

The image is a monster.  PNG 20380x16854, 59.73MB compressed …

I hit swap as soon as I try and view it in all the image viewers I can find.

I mulled the problem a bit and imagined simplifying the problem.  You could, for example, start pruning pointless moves and those moves that allow the opponent to immediately win and so on.

But distilling the winning moves seems like a cop-out.  These days, big data shouldn’t be scary!

I considered making my own image-manipulation code.  But that quickly gets into making your own layout engine too, and … well, I welcome anyone who can master graphviz and has more RAM than I :)

Notes

  1. ryanrapini said: relevant xkcd…. xkcd.com/832
  2. williamedwardscoder posted this

 ↓ click the "share" button below!