Author: Steven Edwards
Date: 12:55:06 03/03/05
Symbolic: Status report 2005.03.03
Automated matches between Symbolic's toolkit and Gnuchess have been used to test
the toolkit's time allocation and check for gross programming errors that might
only show up in an extended tournament environment. These matches are run by
xboard and are useful for keeping the machinery busy. With relatively fast time
controls like G/120+12, the toolkit can manage about a 40% score against
Gnuchess. But in a recent series of games at a G/3600 time control, the toolkit
has done a bit better with a 60+% score. Here's a part of the match log:
2005.02.28 00:58:42 Run finish
2005.02.28 00:58:42 Ponderings: 2387 successes: 1078 rate: 0.451613
2005.02.28 00:58:42 Game count: 29
2005.02.28 00:58:42 Win/Lose/Draw: [14 7 8]
2005.02.28 00:58:42 Scoring rate: 0.62069
This was intended as a 100 game match, but some unknown bug in Gnuchess caused
it to terminate unexpectedly in an KPK position in the 29th game. This behavior
has been seen a number of times before and I think it may be related to an
iteration limit overflow fault with draw detection. Compared with Gnuchess,
Symbolic and Crafty are more reliable; I don't have any recent memory of either
hanging during xboard mediation.
Why does the toolkit perform better at longer time controls? Most likely, this
is because of the relatively high overhead the toolkit encounters at the start
of each search doing root position analysis. But it's only once per search, and
so its overall impact is decreased as the allocated time per move is increased.
--------
I re-read the mid 1970s paper "Plans, goals, and search strategies for the
selection of a move in chess" by Church and Church. In the paper, the authors
describe a program that plays speed chess; each search involves selecting a goal
and then selecting a move that best meets the intent of the goal. Remarkably,
the program played reasonable moves using only a one ply search. More
remarkably, the program was implemented on a DEC pdp12 minicomputer, a twelve
bit CPU and a whopping 8K of memory. Having once spent time coding for the
machine's close cousin, a pdp8/e, I can appreciate the cleverness demonstrated
by the program's authors.
However, the plans and goals of the program are so rudimentary that they are
hardly deserving of the names. There are only a few different plans/goals, and
the related move generation and evaluation routines are quite simple. Yet the
performance is impressive, and this is due in large part to the various "whole
board" matrix operations the program performed to select a move based on global
considerations. From their work, I've decided to duplicate and extend their
matrix functionality in Symbolic's ChessLisp source. My guess is that this will
provide a faster way to accomplish certain pre-planning tasks than using a more
general production system as seen in Wilkins' Paradise program. (Of course, a
production system may be used for those tasks that are best met using pattern
recognition.) In Symbolic, the rough equivalent of the above program's
multi-purpose matrix data type is the "SymBoard", a base type that includes a 64
element vector and several associated routines.
The first Lisp subsystem built using the SymBoard type is the target tracker
facility. A tracker is a Lisp object that assigns a unique ID to each chess man
that is used to track that man throughout the dynamic scope of a plan. Each man
in the current ("now") position can be tracked to a unique origin square in a
starting ("org") position. This capability is required to maintain a positive
identification of men that remains invariant across move sequences. It a
solution to the classical frame problem within the context of man location.
Also, tracking also supports distinguishing among multiple men of the same color
and piece kind. With tracker support, an enemy man can run but it can't hide.
A tracker has two very fast access routines used by Symbolic's planner and
explorer knowledge sources. The first access routine takes a tracker target ID
and returns the target's current square (nil if the target has been captured);
the second takes the index of an occupied square and returns the target ID of
the occupant. A piece created via pawn promotion inherits the target ID of its
precursor pawn. A tracker also has an internal do/undo memory that simplifies
external dependencies.
Testing of the tracker facility shows that, on a 700 MHz machine, it takes the
ChessLisp interpreter about 150 usec to update the tracker with a move and about
100 usec to undo an update. These numbers include the automated Lisp storage
reclamation; the result is that the facility is quick enough to be almost
unnoticeable in the context of a program with a (targeted) five nodes per second
tree search rate.
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.