The game seems pretty trivial. Just arrange for the program to play in the corners, then complete 'three in a row' if it can. Probably the system will never lose and will win quite often.
Yes, I could have done that.
---
I explain that in the version I'm working on, the computer starts with no information about noughts and crosses and no built-in ideas about how to play.
Faced with a blank board there are nine possible places to put its first 'X'. It has no reason to prioritise one over another, so it therefore generates nine possible board positions.
For each of these, it doesn't know where its opponent will place its first 'O', so that's eight possibilities it has to consider. It's now juggling a tree of depth two with 72 options.
The process repeats. No win or loss can occur until the fifth move (3 'X's and 2 'O's) by which time the tree has branched to 15,120 possible boards. Most positions are still in-play though.
Lacking a priori insight, the program has to apply a combination of things. Looking ahead, say, to depth 5, it can score future boards where it wins very positively, and positions where it loses very negatively. Ongoing positions it has to judge more heuristically, creating a 'how good is this for me?' score.
Then it has to somehow back-up these terminal scores which are maybe five or more moves out, bringing them back so that they give guidance for the very next move.
Effectively, the computer is asking itself: what next move maximises my chances to being on a road which ends up with a win, despite my opponent trying to thwart me on every turn?
This is the famous 'minimax' algorithm.
So plenty of apparatus to put together before the first cross gets entered in the first game.
I'm almost there.
---
Once the apparatus of tree generate-and-test has been written and debugged, it can easily be extended to interactions which are less trivial than noughts and crosses.
Automated Theorem Provers and Expert Systems also build trees and evaluate nodes against success criteria. The difference is that the trees they build are not adversarial, so no minimax.
But a conversation planning system is more like a two-player game.
My goal of a smarter chatbot with inference and conversational direction is still very firmly in my mind .. although it's a way off.
Re: "Smarter chatbot..." together with an interest in a mathematical framework, in my studies I have encountered a subject called "Rough Set" Theory (q.v.). Here the idea is to encapsulate the inevitable incompleteness in real data, in a set theoretic manner allowing deductions as can been seen from the WP article.
ReplyDeleteYou will also see there that Applications include Machine Learning.
Remarkably I did not uncover this whilst searching for Machine Learning topics, but trying to understand an idea in Quantum Logic! I was surprised to see the amount of material on Rough Sets and its applications.