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

Monday, February 14, 2011

Intelligent Computer Chess, Part II

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

Abstract

In Part I, I described Animal's brain as a spiking neural network driven by discrete signals called spikes. These are generated either by sensors in response to changes in the environment or by other neurons for various operational purposes. Animal's learning mechanism is universal because it consists entirely of discovering the temporal relationships that exists in a stream of discrete sensory signals, regardless of their provenance. Animal stores its learned temporal patterns in a hierarchical tree of knowledge (TOK) in computer memory. Animal's intelligence derives from its ability to use the TOK to make predictions about possible outcomes and act accordingly. In today's post, I describe Animal's sensory mechanism. But first, a few words on the philosophy behind temporal learning.

Temporal Learning

A spike is a discrete signal, a temporal marker that indicates that some environmental property has just changed. Its lifetime is very short. It is the length of time it takes for it to be generated, transmitted and received. A sensor is a cell that generates a spike when it detects a phenomenon, i.e., a change in some environmental property. An example of a phenomenon is the sudden onset or offset of illumination on a retinal cell. Animal's neural network is not programmed with any hard coded indication as to what the environmental properties are. It uses the same principle (algorithm or program if you wish) to process all incoming spikes regardless of their source.

The beauty of the learning approach used in Animal is that the information carried by a discrete sensory signal is solely a function of its temporal correlations with other signals, i.e., whether or not it arrived before, after or concurrently with one or more other signals. The assumption is that there is a logic in the environment such that changes will generate unique recurring temporal patterns that can be learned or captured by the network.

The Eye, Invariant Recognition and Attention

Most of Animal's sensors are contained in its eye, a 3x3 array that can move around on the chess board. In each of the nine locations of the eye there are multiple sensors, one for every chess piece. The eye also has sensors that detect the gripper used by the opponent and Animal's own gripper. These sensors can detect whether or not a gripper is holding a piece.

Click to Enlarge

If the eye could not move, Animal's brain would be completely blind unless the user uses his gripper to handle or move a piece across Animal's field of vision. I suppose that I could have designed a fixed visual sensor array as big as the entire board. However, I wanted to demonstrate two capabilities that I think are essential to intelligence. The first is Animal's invariant recognition ability: Animal must be able to recognize that a chess piece seen in one corner of the eye is still the same piece after the eye moves and the piece is located at, say, the center of the eye. Secondly, I wanted to give the human observer a sense of what Animal is thinking about, that is, what it is paying attention to at any one time. This is why Animal's eye is represented on the board as a moving circle.

Complementary Sensors

Complementarity is one of the fundamental principles of Animal's brain. One of the things that gives meaning to the signals generated by Animal's sensors is that they all come in complementary types. In other words, if there is a sensor that detects when a pawn has moved out of a given location in the eye, there must also be a sensor that detects when a pawn has moved to that location. It is for this reason that there are two types of sensors for every chess piece. I have also added complementary sensors to detect such things as the eye moving left, right, down and up. In addition, there are visual sensors for game-ended, game-started, check, checkmate, your-turn, my-turn, etc. These are sensors that are designed to detect special markers that appear on the board when appropriate. The markers are strictly controlled by the board's logic, not Animal's brain.

Coming Up

In Part III, I will describe the first neuron layer in Animal's brain, the retina. This is where Animal's brain detects movements, directions and other fixed correlations.

See Also:

The Brain: Universal Invariant Recognition

Tuesday, February 1, 2011

Intelligent Computer Chess, Part I

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

Abstract

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