Author: Roger D Davis
Date: 14:02:47 03/03/05
Go up one level in this thread
On March 03, 2005 at 15:55:06, Steven Edwards wrote:
>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.
Impressive stuff...keep coding...can't wait to see it play. :)
Roger
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.