Author: Steven Edwards
Date: 16:20:24 04/21/04
Symbolic: Status report 2004.04.21 Not much new functionality has been added to Symbolic in the past few weeks. Instead, I've been waging the War Against Kruft by cleaning up various inconsistencies and unused code that have made their way into the project. An embarrassingly large amount of source got deleted. Also, both the C++ and the Lisp source have had a naming convention reorganization that helps me remember how all the functions and data hang together. One of the reasons for the renovation is a change in referencing position and move objects. My initial idea was to have nearly all position and move data represented in Lisp as named symbols with property lists holding attributes. This worked, and still works, but using this technique slows down the selection process quite a bit by adding many, many new symbols that fill up the binding structures (AVL trees, one for each frame in the evaluation stack). Now, only the (single) search tree and its individual nodes will have named symbols and high access use of their property lists, and nearly all position and move objects will be represented only by values and not global scope named symbols. The one area that did get some new functionality was the set of chess specific Lisp sequencing control intrinsics. These are various new forms of do loops that take combinations of position values, bitboards, and colors as a loop sequence definition and automatically bind an index variable and execute the loop body. It turns out that this chess specific approach is much faster than the analogous Lisp technique of creating an explicit index value list and using the dolist intrinsic. Testing with the sixteen bootstrap pattern recognizers shows a threefold speed increase, and the program currently uses only a small fraction of its processing time budget of 200 ms per node. Currently, I'm working on adding the Trapped pattern recognizer, similar to the Immobile pattern recognizer in Paradise. It is different in part because it will use bitboards to quickly check the existence and the safety of potential flight squares. I may also be adding patterns for Discovery and XRay instances. Another development topic is designing operators that work on instance databases generated by the recognizers and matchers. One needed functions is to quickly determine the set differences between two instance databases; this is used to see how well a move or sequence of moves has met a plan subgoal. I've been using the BWTC suite for testing Symbolic. Because Symbolic doesn't yet have a real search, it solves only the mate in one and the mate in two problems. But the test is still useful as in about an hour on a 400 MHz machine it helps build confidence of crash resistance. Soon, I hope to start implementing the planning mechanism that will tackle checkmating attacks and defences of longer mates. Symbolic's cognitive search, the process that takes over when no simple, fast replies are avaliable, is goal directed. It has a single top level goal, SelectCandidate, that starts the search. (This is similar to the Threat goal in the production system in Paradise.) To work on BWTC (and future opponents), I'm adding the second level goals of MateAttack and MateDefend. These work by directing the pattern machinery to produce king hunt plans and to guide node expansion. The idea is that these are simple enough to show the validity of the overall design and help guide the way for future goal and plan definitions. The road is long and my stride is slow. But I'm certain that I'm going in the right direction.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.