Tuesday, February 22, 2011

Intelligent Computer Chess, Part III

Part I, II, III, IV, V, VI, VII, VIII, IX

Abstract

In Part II, I wrote that most of Animal's sensors reside in its movable eye, a 3x3 array of cells in computer memory. Every location in the array contains multiple sensors, two for every piece type. Two sensors are needed because sensors must detect complementary/opposite phenomena. One type detects when a given piece moves to a location in the eye and the other detects when the piece moves out of the location. In all, there are 24 piece sensors altogether in every one of the 9 array locations, 12 for black and 12 for white. In this post, I describe the first layer of Animal's neural network, the retina and I explain how Animal uses the retina to detect movement.

Signal Separation

The retina is the first layer of Animal's neural network. That is to say, it is the layer that receives signals directly from the sensors. This is where Animal automatically learns how to detect movements in its visual field. The retinal layer is populated by special cells called a signal separation neurons (SSN). A mature SSN only has two input synapses called a predecessor and a successor as shown below.


An important rule is that the two input synapses must receive different streams of signals generated by different sensors. The way an SSN works is very simple: if the successor synapse receives a signal exactly one cycle (based on a global clock) after the predecessor, the SSN fires, i.e., emits a discrete signal. The reason that it is called a signal separation neuron is that it separates a signal from the discrete stream arriving at its successor synapse, depending on whether the signal arrives right after a different signal in a separate stream.

Another way to look at it is that an SSN is a gate that opens at the right times to channel certain signals in a sensory stream into a prepared path for further processing. In this light, an SSN should be seen as a filtration device that picks out certain signals in a stream while discriminating against others. The gate keeper is the predecessor synapse.

Learning in an SSN

Initially, the output of every visual sensor splits into multiple branches that make single successor connections with SSNs in the retina. During learning, Animal has a special algorithm called the Searcher which, among other things, is responsible for making random predecessor connections between the visual sensors in the eye and multiple target SSNs in the retina. In other words, every immature SSN has a single successor synapse and a great number of predecessor synapses. There is a fierce competition that takes place among predecessor synapses during learning.

Every predecessor synapse is given a low initial strength. Every time a signal arrives at a predecessor synapse, it is weakened by a small amount. If a predecessor synapse receives a signal exactly 1 cycle before the arrival of the successor signal, the predecessor synapse is strengthened by a relatively large amount. The first predecessor synapse to reach a predetermined strength (maturity level) is the winner. Immediately thereafter, all the losing predecessor synapses are disconnected and the SSN is considered mature. The amounts that I now use for weakening and strengthening  are such that a correlation is considered valid if it happens at least once in every 10 tries. I use 10 for the initial strength of a predecessor synapse, 1 for weakening and 10 for strengthening.

Learning to Detect Motion

Click to Enlarge
Looking at the figure above, suppose the white pawn on the far left in the center of the eye (circle) moves up one square. The negative white pawn sensor in the center of the eye will fire at the instant the pawn leaves that square. During the next cycle, the pawn will arrive at the adjacent square above and the positive white pawn sensor in that eye location will fire as a result. If the two sensors are connected to the predecessor and successor synapses of an SSN in the retina, the SSN will fire to indicate that a pawn has moved up one square.

Meanings in Movements

It is not necessary for a pawn to move in order for Animal to learn how to detect pawn movements. If the eye can move, the same effect will ensue. Initially, Animal's eye is given a random motion in order to create signals and correlations that can be learned by the retina. However, not all correlations are simple motions from one location to another. As the eye moves, signals are generated by many sensors in the array. Animal can thus detect what I call contextual movements such as a knight moving next to a rook or a pawn next to a bishop. Soon after starting, the retina discovers hundreds of correlations or types of motion. These signals have meanings by virtue of their temporal patterns. They can form various sequences that can be learned and stored in Animal's tree of knowledge or TOK.

Feedback Loops

Normally, signals from the retina should undergo further processing in a special looping layer that detects correlations over multiple fixed time scales. This would be true if I were designing the eye and visual system of a real world robot. Multiple time scale correlations can be found by feeding the output signals of a layer back into its input side. Each successive feedback loop discovers and detects deeper correlations such as edges, lines, curves, etc. My hypothesis is that this is what the various areas of the visual cortex of the brain do. In other words, the brain's visual cortex uses massive feedback for visual learning. However, such a looping layer is not necessary in our case because Animal's visual sensors are pretty high level to begin with.

Coming up

In Part IV, I will introduce the principles behind the TOK, a hierarchical temporal structure that comprises Animal's memory and primary learning and prediction mechanism.

See Also:

The Brain: Universal Invariant Recognition

5 comments:

tbcpp said...

So how does this differ in processing time/memory requirements from a brute-force model?

Louis Savain said...

tbcpp wrote:

So how does this differ in processing time/memory requirements from a brute-force model?

I can only provide an estimate since I don't know the requirements of the brute force model. It is safe to assume that they vary exponentially depending on how far down the move tree (how many plies) the search algorithm is told to search. There are two aspects of Animal's brain that make it extremely efficient and fast.

-The first is that there is a tremendous amount of information reuse in the tree of knowledge (TOK). Almost all the growth in the TOK happens in the beginning of the learning process.

-The second is that, once Animal has been adequately trained, its behavior becomes a simple matter of recognizing board patterns and reacting accordingly.

Based on the above, I estimate that Animal's memory requirements will be no more than 1/10 of those of a brute force program of similar strength. Time wise, there will be no comparison because Animal's reaction time for moving a piece will be nearly instantaneous.

Bill said...

Time wise, there will be no comparison because Animal's reaction time for moving a piece will be nearly instantaneous.

What do you think human chess masters are doing with their brain time when they think about a move? Their moves are not instantaneous. I believe there is an imagination element to playing chess that is analogous to a tree search.

Your architecture of direct response seems more appropriate for something like handwriting recognition, which a straight-up perception problem. Chess has adversarial and strategic dimensions that seem beyond the reach of a system like Animal.

I am curious why you chose this problem, and how you would define its success or failure?

Louis Savain said...

Bill wrote:

What do you think human chess masters are doing with their brain time when they think about a move? Their moves are not instantaneous. I believe there is an imagination element to playing chess that is analogous to a tree search.

Actually, experts and masters are adept at playing very fast chess. When a human player recognizes a well-understood pattern, he or she does not hesitate to make a move. It is only when the consequences of a move are insufficiently known that the player will spend time to analyze the move. I expect Animal to do likewise as it learns.

Your architecture of direct response seems more appropriate for something like handwriting recognition, which a straight-up perception problem.

Well, I disagree that Animal's brain architecture is designed solely for direct response. Animal can learn from its mistakes and will spend time analyzing unfamiliar board positions. However, my stance is that, once a position has been sufficiently studied, there is no longer a need to do so every time it is encountered. In time, the problem becomes similar to a handwriting or face recognition type problem.

Chess has adversarial and strategic dimensions that seem beyond the reach of a system like Animal.

I don't think so. Good strategy is based on the ability to predict the probability of long-term outcomes. Animal's main brain structure, the tree of knowledge, is expressly designed to make predictions (I'll explain the tree of knowledge in my next post).

The adversarial aspect of chess can be learned just like everything else. Animal has a reward/punishment system that works directly with its prediction mechanism. This forces it to seek beneficial goals and avoid "unpleasant" outcomes. Indeed, it will be up to the human trainer to discipline or reward Animal into a desired behavior.

I am curious why you chose this problem, and how you would define its success or failure?

If I had adequate resources, I would rather work on real world intelligent robots, preferably a multi-pedal robot with a full set of sensors and manipulators. I chose chess because all it requires from me (other than a theory of intelligence and time) is a computer and some programming skills, which I am fortunate enough to have. Unfortunately I don't have nearly as much time as I would like. Hopefully, that will change eventually.

At this point, if I can get Animal to learn to just recognize legal and illegal moves on its own from scratch, I would consider the project a run away success and a revolutionary breakthrough. After that, getting it to play a decent game would be easy.

Bill said...

Very interesting!