Computer Chess Club Archives


Search

Terms

Messages

Subject: Symbolic: Status report 2005.07.13

Author: Steven Edwards

Date: 20:16:05 07/13/05


Symbolic: Status report 2005.07.13

Only a few improvements to Symbolic were made in the past couple of weeks as
much time has been spent on health issues.  The relatively good news is that my
cardiac difficulties aren't as bad as they might have been and so no surgery is
planned.  My cats are quite thankful for this as no one else is going to supply
them with belly rubs and tuna fish.

The only major change to Symbolic has been the restructuring of the
CandidateSelector knowledge sequencer.  This is the Lisp routine called once per
search and it is responsible for returning an analysis to its Lisp caller
SelectCandidateNode.  It controls the progressive nature of the cognitive
search, and this needs a few paragraphs for an explanation.

The first item is a new data structure, the FrontNodes.  This is a list of open
position tree nodes where further analysis is needed.  These are often leaf
nodes, but not always.  And not all leaf nodes are in this front list.

The second item is the basic quantum of the cognitive search, the "Selector
Cycle".  A selector cycle consists of a single cycle of the Selector knowledge
sequencer.  Each call to Selector includes a position tree search node
(indicated by the PST cursor and treated as a local root node) and an effort
parameter (this tells the subsequent routines hard much effort to expend).  For
example, the very first Selector call has the cursor pointed at the root
position and the effort set at a minimum (zero).  The Selector sequencer's job
is to attach an analysis to the position tree search node that was given as a
local root.  It does this by calling various other sequencers including the
Planner and the various Explorers.  The interesting endpoints (if any) of the
freshly grown (or re-grown) local position tree are recorded for possible
reconsideration later via posting on the FrontNodes list.

To have a claim for psychological realism, the cognitive search must exhibit
both progressive deepening and progressive widening.  The CandidateSelector
sequencer has an outer effort loop and an inner Selector loop that makes this
happen.

The outer loop starts with an effort value of zero that's increased once per
outer iteration completion.  At the top of the outer loop, the FrontNodes list
is set to contain a single element, the root node of the position search tree.
The top of the loop also calculates how many Selector cycles maximum are to be
tried for the given effort level; this bound is (2 exp effort).  The outer
effort loop exits with the first of: time exhaustion, or a sufficiently certain
analysis at ply zero.  The incremental increase in the effort value tend to
cause more thorough analysis (e.g., more aggressive planning and more sub
variations tried at each node) and so contributes to progressive widening.

The inner Selector loop runs up to the (2 exp effort) Selector cycles on
interesting position tree nodes taken from the FrontNodes list using a constant
effort value.  The available nodes are ranked according to interest and one of
the best is picked each time through the Selector loop.  Inner loop termination
occurs with the first of: time exhaustion, per effort loop cycle count,
FrontNodes list exhaustion, or a sufficiently certain analysis at ply zero.  The
exponentially increasing numbers of Selector cycles tend to cause deeper and
sometimes wider analysis and so contributes to progressive deepening.

So, the cognitive search mimics human search by executing one chunk (not one
move) of planning/exploring after another, hopping from one part of the tree to
anther revisiting plans and nodes with increasing effort, progressing in both
width and depth, reducing global uncertainty, and selecting a top level move in
the available time.  I know of no other two person game program that searches in
this way.  Unless there's already a name for it, I'm going to call it the P
search (P = Progressive).

--------

More to come.



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.