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.