Asking a different question

A run around the Internet will find several references to attempts to play noughts and crosses using neural networks. Reading between the lines it was clear than none we found were claiming any great success and most seemed to be tackling the problem in the same manner that we had. While we were not hoping for a perfect playing neural net we did hope for something as good as the MENACE simulation.

Our Internet review came up with two interesting papers by Chellapilla and Fogel dealing in the most part with the challenge of evolving neural networks to play the game of draughts (checkers in some parts of the world). One interestingly also dealt with some experiments with noughts and crosses playing neural networks. You can download the papers from ***** REFERENCE ***** and other locations or take a look at David Fogel’s later book “Blondie 24” which is an accessible account of the development of a neural network that was very capable at playing their chosen game..

Chellapilla and Fogel used a different technique to apply their neural networks to draughts. They presented the neural networks with game board positions and used them to assess the relative worth of each position – they did not ask directly for a move selection. I would also hazard that some of the rules of the game helped advance the development of their networks. A key rule that they had to see their neural networks followed was the one that demands that if a player is in a position to take an opponents piece then he must do so. If you read their papers you will see that things were a bit more complex than that but this provoked an interesting thought.

Suppose we changed the question we expected our neural networks to answer to “which of these new positions do you prefer?” from what was in effect “How do you rank the playing positions available?” Plus we decided to push things a bit and say that the game now had a new rule – if a win was possible with the next move then that was the move to be chosen. In many ways this was closer to the task the MENACE simulation machine was set and mirrored some of the approach taken by Chellapilla and Fogel although for hopefully obvious reasons we restricted the search forward to a single ply (see our page on Minimax and Alpha-Beta pruning)..

We applied this new game playing strategy by making a simple change to the layout of our neural networks – now there was only a single output neuron. Each possible game position that was open to the neural network player was presented in turn to the input neurons and the “valuation” of that playing position read from the output neuron. The highest valuation was used to make the neural network’s move. We tried out the new strategy with neural networks pitted against our game playing algorithm and in another tournament where neural network played neural network.

The improvement in the standard of play was immediate. The difference in the question we “asked” of the neural networks was subtle but important. It required a bit more work from the software managing the game play but it was clear that our evolving networks were much better at assessing differences between combinations of positions than they were at selecting individual play options. Plus the new game “rule” ensured that they did not snatch defeat from the jaws of victory at early stages in their evolutionary development – they evolved to become winners!

Further Work

Since our early experiments we have been applying neural networks to real life tasks where “assessments” are required and where multiple inputs need to be “adjusted” to arrive at them. One key area of research (and practical output) has been to do with analyses where multiple simultaneous judgements of input data are required to feed back and refine the original incoming data set. This approach throws up some new challenges – do you have multiple neural networks processing the separate data elements or do you apply a larger network and hope sections of it “specialise” in the main but share resources where required?

If you are interested in applying artificial neural networks to “zero sum” or other games then it is clear that an algorithm to search ahead in a game an appropriate number of ply using a neural network to asses alternate board (or what have you) positions should be a viable approach and could well result in a pleasing software opponent. Not only that but your opponent could turn out to be much more capable than one that relied upon processing power above all else. How about linking one up to one of the “dreaded” Microsoft Agents to provide speech and general visual interaction?

Conclusion

Artificial neural networks are simple to construct in program code although their application requires some thought and experimentation to obtain optimal results. The evolution of neural networks is a viable development method that shows a lot of promise although more traditional training regimes are at least as applicable in many circumstances.

[ Home] [About Us] [Systems] [Software Review]