Insomnia - and New Year Resolution

It's been a while since I lay awake at 3.30 in the morning puzzling over an algorithm.

I had figured my journey with Common Lisp could start with a simple mini-project. How about programming Noughts and Crosses (I believe Americans call this tic-tac-toe)?

I teased Alex (Java developer, currently studying Scala, sceptical about recursion on grounds of efficiency).

"How many different kinds of algorithm can you think of to play noughts-and-crosses?"

My wife is annoyed when I do this: spending prior time thinking it through, then pretending to spontaneity.

Alex thought about it.

"You could have a big look-up table to store the optimal best move."

Damn, never thought of that one!

"OK, so here are my three suggestions:

1. A rule database which tells the system what to do next
2. A tree-search program, using minimax
3. A learning program, adjusting weights on possible moves through experience."

---

When I first started learning about AI, years ago, I was puzzled by two things.

• How do you get a computer system to behave in a cunning, responsive, flexible, creative and intelligent way at all? My programs hitherto had simply trundled their way through humdrum computations.


• Secondly, being as in the end it all comes down to programming, where does ordinary code development stop and AI start?

Intuitively, I tend to place the line at heuristic search. You go to search when you don't have an algorithm to hand (be it ever so clever) which just solves the problem.

Heuristic search is flexible, surprising, opportunistic, creative and curiously human-like.

Just like your sat-nav (A*).

---

The space of possible Noughts and Crosses board positions is bounded above by nine factorial, 362,880. It will be less than that because many games terminate before filling all nine squares. There are also symmetries which compact the search space.

Wikipedia tells us:

"When considering only the state of the board, and after taking into account board symmetries (i.e. rotations and reflections), there are only 138 terminal board positions. Assuming that X makes the first move every time:

• 91 distinct positions are won by (X)


• 44 distinct positions are won by (O)


• 3 distinct positions are drawn (also known as a cat's game)."

Still, it's a pretty large look-up table.

So my first thought was that you should create the entire tree of all possible Noughts and Crosses games which could then be transformed into a look-up table. I guess at this point, the distinction between the table and a set of rules is rather in the noise.

An obvious thought is to chunk: to create higher-level features such as "in the centre", or "at a corner", or "a cross/nought at three corners with an empty space between each of them along an edge".

This is how people think, and it exploits both symmetries and the logic of the gameplay. It also sounds complicated: a viable game strategy needs many more such features.

---

I was thinking about this as the owls hooted and the odd snuffling thing perambulated around our house. I came to two conclusions:

- It's important to explicitly list the win-states (there are eight + extra forced-win states).

- The AI system should examine each board position (as it is about to play) and check two things:

• Is there a winning next move for me?


• If not, is there an opponent winning next move which I can block?

This seems to require a two-ply lookahead.

You wouldn't get perfect play with such a shallow search, but the evaluation function just described is good, and I think you would get at least competence.

I also think it would also be interesting to implement a full minimax search algorithm - just for the experience of doing so. That would give you perfect gameplay.

Noughts and Crosses is a pretty trivial game, but the principles involved in playing it are also implicated in very sophisticated games. So it's a kind of laboratory test bed.

---

My thinking is therefore this.

Start by writing some Noughts and Crosses players in Common Lisp as a learning experience. (It's been years since I programmed in Lisp and I've forgotten the functions and their syntax - in any event, I was using Franz Lisp).

Then rewrite Winston and Horn's Propositional Calculus Resolution Theorem Prover.

I'm getting a tiny bit bored with the Propositional Calculus, which only lets you solve toy problems, but it's a good place to study search/inference strategies like set-of-support and hyper-resolution without the complexities of unification.

Next, bring J. A. Robinson's Hyper-Resolution Theorem Prover into the twenty-first century.

Finally, use his system as an inference engine for a chatbot, mirroring what the Replika system will be doing with their neural-net machine-learning engine sometime in the New Year.

It's a promising plan - but there again, I'm not so good with New Year resolution.