Octavius

CHESS PLAYING ARTIFICIAL INTELLIGENCE

PREFACE

In 1999 I researched chess playing ANNs (artificial neural networks) and found nothing, no-one had attempted it, and many said it wasn't possible. It was early days for ANNs.

So I designed one myself - "Octavius". Back then I was using a computer with a Pentium 166MHz and 32Mb RAM. It was slow going! ANN training is very time consuming.

In the time that I made Octavius available I received encouraging feedback and communication from University of California in Santa Cruz, Karpov Chess Institute in Germany and Sao Paulo University in Brazil. Thanks especially to Alexander Aguiar for his support, encouragement and feedback. 

A few years later I was one of eight international competitors in the Loebner Prize Artifical Intelligence Competition held at the London Science Museum. This lead to writing a chapter for Springer (which included a section on "Octavius").

Springer - Parsing the Turing Test.

Springer - Parsing the Turing Test Chapter, "How not to Imitate a Human Being."

NOTE: This software exists purely for archival and educational purposes. Although perfectly usable, the documentation is terse and the software is no longer supported.

INTRODUCTION

How does an ANN [artificial neural network] work?

An ANN is an implementation of "connectionist" architecture. A connectionist architecture seeks to loosely emulate the workings of a biological brain and is characterized by having a large number of very simple neuron-like processing elements, a large number of weighted connections between these elements, parallel distributed control, and an emphasis on learning internal representations automatically. The weights connecting each neuron encode the knowledge of the network.

A simulated neuron is a node connected to other nodes via links that approximate to axon-synapse-dendrite connections. Each link is associated with a weight. The connecting weight multiplied by the neuron's output determines the nature and strength of one node's influence on another: a large positive weight corresponds to strong excitation, and a small negative weight corresponds to weak inhibition. 

How does Octavius work?

Octavius is classified as a feed-forward network: a board image generation algorithm converts a chess position into a sequence of rational numbered inputs (within the range of -1 to 1, or 0 to 1) which are fed into the neural network. These inputs are then propagated forward through the neural network resulting in a specific numerical evaluation. It is then simply a matter of choosing the move which results in the best positional evaluation.   

How does Octavius learn?

A human who learns how to play chess begins with the basics: the movement of the pieces, the relative value of the pieces, threats, traps and discovered checks etc.

Octavius attempts to gain an understanding of chess through a positional analysis of master and grand master games. His training is based on the assumption that any position reached during such games must be positionally superior to any alternatively available position during that game.

The theory is that through exposure to master and grand master games Octavius will be able to deduce the rules and tactics of chess heuristically via positional interpolation. This top-down method is precisely the reverse of the human bottom-up approach.

OVERVIEW

CHESS BOARD

Play indicators - These are found at the top right of the chess board and indicate who is to play (white or black) and also indicate if the current player is in 'CHECK' or 'CHECKMATE'.
Castling indicators - Also at the top right, these check boxes cannot be altered and simply indicate whether white/black has the option of king/queen-side castling.
Reverse Board - This will rotate the board to give Black's view.
Play Vs Octavius - This will ask Octavius to make a move. Use the "Autoplay" flag in "Settings" if you want Octavius to assume the role of the opponent and respond automatically.
Self Play - Octavius will play against himself for the desired number of moves. 
Reset - This will reset the chess board back to the starting position. 
Take Back Move - Takes back the last played move.
Game Scroll Bar - Use the scroll bar at the bottom of the form to move through the positions in a game.

To move a piece simply click and drag it to it's destination.

To bring up the "Edit Board" menu right-click any square on the chess board. This will allow you to add/remove pieces and to change the chess font. 

EVALUATIONS

Best Move Indicator - Located below the "List Evaluations" button, this will show the best move so far and it's evaluation.
Sort - This will sort the evaluation list once all evaluations have been made.
List Evaluations - This will list and evaluate all possible moves.

If you are currently playing Octavius, and the "Evaluations" form is visible, it will automatically list the evaluations. 

OUTPUT NODES

This form will automatically and dynamically graph the behavior of the neural network's output nodes during play and training. This form can be resized to suit the user.

The red circle indicates the highest valued output node. Use the J and L keys to highlight any particular output node and see it's current value. During training, the graph is only periodically updated between backpropogations - at any time you can right-click the graph to see the current state of the output nodes. 

PGN

Load - This will prompt the user for a PGN file to be loaded and displayed on the "Chess Board".
Copy PGN to Session - This button will copy the current PGN game to the next available session-slot to be used during a training session.
Game Scroll Bar - Use this bar to access a game within the current PGN file.
Information Window - This displays all the raw PGN game information.

DEFINE FONT

Add - Adds a font to the Chess Fonts list from the Available Fonts list.
Remove - Removes a font from the Chess Fonts list.
Use Font - Redraws the Chess Board using the selected Chess font.
Load Definition - Loads a Chess Font definition.
Save Definition - Saves a Chess Font definition.

Use the Font Definition area to type in the corresponding characters and to correctly configure the font. There are many nice chess fonts easily available on the internet. 

ANN (ARTIFICIAL NEURAL NETWORK)

Output Nodes Indicator - Found to right, indicates the number of output nodes in the current neural network.
Output Mode Indicator - Found top right, indicates the output mode of the current neural network. Output modes are "THRESHOLD", "RAW" and "HIGH-NODE". 
Load - Loads a neural network (*.ann): the default path is <installation directory>/ANN. 
Save As - Saves the current neural network.
New - Creates a new neural network.
View ANN Log File - View the Log File associated with the current neural network.
View ANN Information - A summary indicating the number of nodes and connections present in the current neural network.
View Image Graph - Open the "Image Graph" form.
Autosave ANN each Epoch - The current neural network will be automatically saved at the end of the training epoch.
Autosave ANN each Session - The current neural network will be automatically saved at the end of each PGN game session within each training epoch.
Load Training Set - Load a predefined training set (*.trn): the default path is <installation directory>/Training.
Save Training Set - Save the current training set.
Train non-PGN moves - All other legal moves during each position of a PGN game session will be trained using the "BackProp Default" parameters.
Re-enforce PGN mode - Training in each position of a PGN game session will alternate between a non-PGN valid move ("default") and the PGN move ("target").
Number of Training Epochs - The number of times to repeat the entire training session.
Session - A PGN game. Right-click the session to bring up the "Edit Session" menu. Also, left-click the session to simply add/remove a PGN game. Use the PGN form to select the desired game and copy it to a session using either the PGN form  copy button or the ANN form copy button.
BackProp Default - The default positions are defined as those positions resulting from a valid non-PGN move during each position within a PGN game. Simplistically, these positions are "bad" positions. Set the operator (<=,=>,<,>,=) and the value parameter to define the conditional test upon the ANN evaluation during backpropogation learning.    It is vital that you take into consideration the evaluation method. The default method ("threshold") will total the number of output nodes which reach or exceed their activation threshold (.9). The "raw values" method will total the activation levels of each output node. The "highest output node" method will add the index of the highest output node to the actual value of the highest output node. Also, using "highest output node" and "raw values" the "=" parameter works as a bracket between the value specified and the integer part of that value plus .999999. Thus, if the test is "=1.5" then an evaluation of 1.5 to 1.99... will satisfy this condition. 
BackProp Target - The target positions are defined as all those positions which are reached during the PGN game session. Simplistically, these positions are "good" positions. Set the operator (<=,=>,<,>,=) and the value parameter to define the conditional test upon the ANN evaluation during backpropogation learning. See "BackProp Default" for further information.
Alpha - This is the momentum rate of learning to be used during backpropogation.
Copy - This will copy all the session information (except for the PGN game) to all sessions below.
Reset - This will reset all session information, removing all PGN games.    
Start/STOP Training - This will start/stop the current training session.

BOARD IMAGE GRAPH

Chess Piece Icons/check boxes - Left-click the piece icon to see the piece activation matrix of that particular piece and only that particular piece. To see superimposed multiple piece activations, click the desired check boxes and then click the "graph" button.
Select All - Selects all piece check boxes.
Deselect All - Deselects all piece check boxes.
Merge Piece Values - Will merge all selected piece activation matrices into a single matrix. Use the "sum" option button to add the activation values or the "average" option button to calculate the mean activation value.
Display Image for White/Black - Displays the piece activation matrix for white or black.
Merge Images - Merges the current piece activation matrices for white and black with enemy pieces being converted to negative values.
Mark Out-Of-Range Inputs - Out of range inputs (<-1 and >1) will be marked with a red circle.
Show Grid - Shows the underlying activation plane using dashed lines where the activation value would equal zero.
Include Drop-Lines - A height indicator: draws vertical lines linking the activation values to to the underlying grid.
Add Noise - Adds noise to all activation values (see "Settings").
Graph - Re/draw the graph.

Use I-J-K-L keys to navigate over the activation surface and to highlight nodes and their values. Each piece activation matrix is combined to create the ANN board image in it's entirety which is fed into the ANN's input nodes. The complete board image generation algorithm is beyond the scope of this document. 

SETTINGS

Use Capture Evaluation - Capture evaluation is a simplified version of material evaluation where only positions which result from a capture are analysed.
Use Material Evaluation - Full material analysis using a minimax alpha-beta tree search.
Depth - The ply-depth of the analysis.
Weight - This weight is multiplied by the result of the material analysis before adding it to the neural network analysis. With the weight parameter set at 1, material is valued as pawn:+/-1, knight & bishop:+/-3, rook:+/-5, queen:+/-9.
Use Opening Book During Play - Octavius will select a move whenever possible from a pre-defined database of openings.
Autoplay - Rather than having to press the "Play Vs Octavius" button on the "Chess Board" every time you want Octavius to move, you will simply have to press the "Play Vs Octavius" button once.
Autosave settings with ANN - Every time the .ann file is saved, the associated settings file will be saved automatically too.
Load Settings - Load a "settings" (*.set) file.
Save Settings - Save the current settings as a "settings" (*.set) file.
Learning Rate - Learning rate of the neural network. It is beyond the scope of this documentation to explain the exact influence of this parameter.
Add Noise - Noise is added to the input nodes. Useful during training to prevent over-fitting.
Use Negative Input For Opponents - All input nodes which contain data derived from the opponents board image are multiplied by -1.
Average Piece Influences - For neural networks which combine piece activations for each square on the chess board. The default is to sum the influences. Use this check box to average piece influences.
Use Raw Output - An evaluation is generated by summing the raw values of all output nodes.
Use Highest Output Node - An evaluation is generated by taking the value of the highest output node and adding it to the index of the highest output node. By switching off both "Use Raw Output" and "Use Highest Node" the output method becomes the default which is "threshold". In "threshold" mode all output nodes which reach or exceed their activation threshold (.9) are valued as 1, all other nodes are valued as zero. These values are then totaled.
Post Invert Output Node 1 - Used in "High-Node" output mode. If output node 1 is the highest node, then the evaluation becomes 2 - the activation level of output node 1. E.g. if output node is the highest with a level of .75 then the evaluation becomes 1.25 (2-.75).
High-Node Salience - Each level of the slider (except "none") represents the number of times for each backpropogation that the highest node is increased while all other nodes are flattened.
Move Activation Overrides Piece Activation - If a piece of a certain type can move to a square occupied by a piece of the same colour and type then the piece activation matrix will be set at "Move Activation(1)" instead of "Piece Activation".
Piece Activation - The activation value assigned to the piece activation matrix when a piece exists on the square in question.
Move Activation (0..4) - The activation value assigned to a destination square where a piece is able to move to. The indexes represent how many pieces of the same type and colour can move to the destination square. "Move Activation(0)" represents an empty square. "Move Activation(4)" is a special case which specifically refers to pawn captures. If you are unsure about these settings then play with them and use the "Board Image Graph" form to see the results.