Tuesday, February 1, 2011

Intelligent Computer Chess, Part I



In this multi-part article, I will describe the learning and behaving mechanisms of Animal, a chess learning program. Even though I have been working on it for many years, Animal is not yet ready to be released because I am still doing research on its brain. As you can guess, the brain is the tricky part. In this post, I describe the essential philosophy behind Animal's brain mechanism.

Click to Enlarge
The Tree of Knowledge

Animal is a chess learning computer program that uses a spike-driven neural network for learning and behaving. Unlike traditional computer chess programs, Animal does not conduct an extensive search of the game tree. Rather, Animal pretty much learns to play chess the way we do, through trial and error. As it plays, it uses a hierarchical tree of knowledge (TOK) to store various temporal patterns in memory. Each branch of the tree represents a specific pattern and can be recalled (activated) every time the pattern is encountered. The TOK is not just used for storing learned patterns, however. Animal also uses the TOK for making predictions about possible outcomes. This predictive ability is the basis of Animal's intelligence.

Temporal Learning

In Animal's universe, an event is a phenomenon or a change in some sensed property. Animal's learning mechanism is strictly driven by change. Animal's sensors, for example, do not detect that there is a particular chess piece at a particular square position on the board. Rather, they detect whether or not a chess piece has moved from/to a particular position. Upon detecting an event, a sensor will generate a signal or spike. A spike is a temporary marker that alerts a receiving processor (spiking neuron) in Animal's brain (spiking neural network) that an event just occurred. Animal uses many sensors that generate a constant stream of spikes.

Universal Intelligence

One of the most surprising aspects of Animal's brain is that the provenance of a spike is completely irrelevant to the learning mechanism. That is to say, whether a spike was caused by the motion of a pawn or a bishop is unimportant. The temporal relationships between the spikes are all that is required for learning. In fact, Animal's learning mechanism does not care about chess, tic-tac-toe, or any other environment. Animal needs only to be presented with a stream of sensory events to discover the temporal patterns and learn to recognize them.

Animal uses both sensors and effectors to interact with its environment. As with sensors, Animal's brain does not care about the destination of its motor signals. It uses whatever effectors it is given. This universality is what gives Animal's learning mechanism its power. Once the brain is perfected, it can be used in any type of situation where intelligence is required. Just plug in an appropriate set of sensors and effectors and watch it learn and behave intelligently.

Coming Up

In Part II, I will go over sensors and the temporal learning mechanism in greater detail.

See Also:

The Brain: Universal Invariant Recognition


Bill said...

I would be very surprised if this approach worked. It is a strange choice to model the moves (state changes) rather than the state of the board. This causes an undesireable many-to-one correspondence in the search space, i.e. many different moves will result in the same board state. With your choice of representation, you can't properly recognize these invariants, which will make generaliazation difficult if not impossible.

Louis Savain said...

Hi Bill,

Thanks for the comment. Let me respond by saying that Animal's brain does get a sense of the state of the board by recording what it sees in its working (short term) memory. Like humans, Animal's short term memory can retain up to seven items at a time (this is metaphorically coded as the seven eyes of God or the seven branch menorah in Jewish and Christian Kabbalistic texts. Seven items may not sound like a lot but each one of them can encompass a huge quantity of information depending on how high up the tree of knowledge working memory happens to be located at any given time. The TOK provides for a tremendous amount of knowledge compression and information reuse.

As I will explain in my next installment in this series (sorry for the delay in posting), Animal has what I call an Eye, a 3x3 array of visual sensors. As the eye moves on the board, a stream of signals is continually sent to the neural network. This way, the network gets a sense of where all the pieces are even if they are not moving. The motion of the Eye is what generates the signals.

Note that, even though there are specific visual sensors for each piece, Animal's neural network is not "told" what the sensory signals represent. Representations are not coded in the network. Animal must learn the various temporal signatures as it matures. A huge number of invariant pattern recognition branches are automatically created in the tree of knowledge during learning. These branches store patterns or temporal signatures that may represent (to us, that is) various pieces, positions or moves. We can find out what features they represent by observing which branches of the tree become active when presented with certain board positions. This is not unlike the way cognitive scientists use MRI scans to observe various areas of the brain.

Hang in there.