Author: Steven Edwards
Date: 12:51:38 03/14/05
Symbolic: Status report 2005.03.14 For those who have tuned in late, here's a brief recap of the Symbolic project: Symbolic is divided into three parts. The first part is a rather stable chess programming toolkit composed of about 62K lines of C++ source that implements all of the classes needed to implement a conventional chess playing program. The second part is a reasonably stable Lisp interpreter composed of about 28K lines of C++ source that uses the toolkit and provides an execution environment for the ChessLisp programming language. The third part of Symbolic is its ChessLisp source, now about 4K lines long and growing. The ChessLisp source implements a cognitive search based on pattern recognition and planning. The effort is inspired in part by earlier work by David Wilkins (his 1980 MacLisp program Paradise) and also by psychological research related to human chess playing. The approach is radically unlike any chess playing program of the past twenty five years. How will Symbolic conduct a cognitive search? The high level answer is related to a traditional Lisp programming technique: instead of solving a problem directly in one step, first construct a program to solve the given instance of the problem and then execute the constructed program. Symbolic has a Planner module that constructs a plan; Symbolic's Explorer module then executes the plan. To effectively perform the search, the Planner and Explorer are mutually recursive and call each other as needed at various positions in the search. At the highest level, Symbolic's Selector module calls the Planner and the Explorer on the root position iteratively with monotonically increasing effort as time permits, or until a sufficiently certain result is formed. The current work effort is focussed on the pre-planning pattern matching tasks. Within this effort, the concentration is on producing pre-plan pattern instances suitable for generating plans for checkmating attacks. When this is completed, work will then be done on Symbolic's Planner and Explorer. Soon after, the first non-trivial cognitive searches will be attempted on the BWTC test suite. At the current sloth-like rate of development it will likely take several months of calendar time to complete the above. -------- The program's ChessLisp source for representing Author and Analysis constructs has been changed to use association lists instead of position dependent parameter lists. Similar changes were made for representing input and output values of the various KSes (Knowledge Sources). The trade here is a significant gain in encapsulation for a very slight loss in run time efficiency. All of these changes are now being tested. There would be little or no need for such re-work if I had implemented the Lisp defstruct primitive in ChessLisp. But I already had a couple of hundred Lisp primitives and one has to draw the line somewhere. After all, this is an AI project, not a Lisp project. -------- The productions (the main accessors of the Instance Data Bases) have been organized into sets. The first set, called "First", includes a half dozen or so simple productions that initialize an IDB by posting instances of chess values like the current position and hash history so that later pattern matching need refer only to the IDB and not to external values. This first set of productions has two production sequencing routines. One is called during normal execution and takes only one parameter, the node of interest in the position search tree. The second sequencer is a routine used only during testing that runs the same productions using an interactively supplied set of chess values. All of the productions in the first set are very simple and fast. The second set of productions, called "Early", has a single sequencing routine. This group includes about a dozen productions that reference the instances posted by the first set and in turn match patterns for basic chess concepts for Man, Move, EnPrise, and Pin among others. Some of the instances produced are fairly long and include an association value binding for just about every fact that might prove useful in later analysis. These two sets are run, unconditionally, on each position search tree node that requires planning activity. The hope is that only a small fraction, perhaps one tenth, of all such position search tree nodes need an attached IDB. This estimate is based in part on the results of Wilkins' Paradise program. And as in Paradise, Symbolic's production processing will be the main CPU user. Running the two production sets on a 700 MHz PowerPC takes a relatively long time: about 90 msec for a complicated position like BWTC0031. This preliminary timing figure represents an improvement factor of better than one hundred over Paradise. (Recall: Paradise ran on a DEC pdp10 mainframe, a very capable machine of its day, but that day was twenty five years ago.) That 90 msec number is a bit close to the target budget of an average of 200 msec per position search tree node. Furthermore, as more productions (several hundred) are added, that 90 msec figure will surely grow. If the eventual IDB production sequencing time for a static analysis reaches a full second, but is run only at one of ten nodes, then that leaves half the average CPU per node budget for other search activity. -------- A third set of productions, the MateAttack group, is now under consideration. These productions will contain the knowledge needed to suggest mating attack move sequences and then build plans around them. There is a lot of work here and it will be difficult as it's the first topically specific group attempted with no previous such group available for design guidance. Unlike the first two sets, the MateAttack group will include an effort value parameter; the larger the specified effort, the more extensive the attempts to produce mating attack plans. Most other production sets will have the same effort parameter. The idea is to start the move selection process with a small effort value, and then re-run the search with successively larger values as time permits. This is a very important distinction between Paradise and Symbolic; Paradise made only one, fixed effort attempt to construct plans at a search node. If the right plan wasn't generated or wasn't sufficiently specified, then the search failed. Compared with Paradise, Symbolic's method is somewhat more psychologically realistic as it mimics the human behavior of revisiting previously considered plans via progressive deepening. Suggesting mating attack moves is a tricky problem. It is very important to always, or nearly always, suggest a successful move if one is available. Also, it is rather important not to suggest moves that would ultimately be unsuccessful to avoid the dreaded combinatorial explosion. I have several ideas on how to do this within Symbolic's progressive deepening framework, and I'll write about them in future reports. -------- Symbolic's Lisp source now has a hash map facility. This is a pair of binary trees, one for each color and keyed by position hash. The hash map is used to associate hashes with nodes in the position search tree to quickly detect transpositions. Also, it may be the case that some positions may be generated without an associated node (or before the node is generated), and these can be stored in the map along with other values (a form of memo caching). A hash map is used instead of a transposition table because Symbolic can't allow the possibility that an entry might be overwritten. The hash map facility has been stress tested by connecting it to a simple movepath enumeration (i.e., a perft function) and using it to count the number of unique positions along with the movepaths. Considering the initial array position, the unique position counts for the entire tree for various depths are: 0/1, 1/21, 2/421, 3/5783, and 4/77796. The ChessLisp interpreter runs the movepath enumeration test with complete terminal position generation using about 5 msec per position. This includes all overhead for the target tracker, the hash map, and the automated storage reclamation. -------- One of the subprojects recently completed is the development of what I call a Scout object. A Scout is implemented in ChessLisp as an association list containing a target tracker, a position value, and some pushdown stacks to hold state history. There are several usages for a Scout; one of them will be in the productions in the MateAttack set that help suggest initial and secondary attacking moves. The idea here is to support a light weight scouting mechanism to answer questions about moves such as "how many replies", "is an interposition forced", "can a defender be deflected", and "how many flight squares have been removed". My thought is to have a separate Scout attached to each IDB and have the production sets share it to answer questions (and confirm guesses) about the associated position.
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.