Author: Steven Edwards
Date: 16:55:24 05/19/04
Symbolic: Status report 2004.05.17 [Posted two days late] The ChessLisp interpreter gained support for simple vectors as an altenative to the existing and much more general multiple dimension array support. The motivation is to make Symbolic's Lisp source a bit tighter and also more efficient. -------- Earlier, Symbolic's Lisp source had only a single global variable with a lengthly property list that handled parameter transmission duty and also some working storage items. Since the caller (the C++ routine interfacing ChessLisp with the toolkit) never accesses the working storage items, I've removed them from the global symbol property list; they are now global variables accessable throughout the Lisp source. (They are easily spotted in the source due to a special naming convention.) Having global variables is rarely a good idea, but here it works reasonably well as their count is few and their semantics are simple. A side benefit is a runtime efficiency boost gained by removing property list access overhead. -------- I've implemented a blackboard style cache mechanism local to each node in the search tree. This cache is an array, indexed by (potential) descendent move, that contains data about attributes of the move and its (potential) subnode. The idea here is to store the results of calculations generated (and used) by the knowledge sources that are local to the node so that: 1) values aren't calculated until (and if) they actually get used, 2) no same calculation is performed more than once, and 3) subnode generation can sometimes be skipped if sufficient and convincing information can be retrieved from the cache. There's a lot of potential savings here as generating a subnode is a fairly costly action in Symbolic. The knowledge source processors assume that all of the many property values included for each node are fully calculated and defined by the node creation intrinsic ExpandNode. In some cases, only a single attribute (e.g., a tablebase probe result) is needed, and it's much cheaper to skip the subnode creation in that case. So now there's a speedup and a reduction in the node count. -------- A basic Knowledge Source Manager (KSM) has been implemented. Also, about eight or so KSes have been written and tested; these include the top level KsCandidateSelector, the KsBookSelector, and the KsTablebaseSelector. At this point, Symbolic retains all of its prior functionality for quick/certain move replies, but it now uses the KSM and the KS family to produce those responses. Currently, there are from three to nine KS calls for each move selection. The KSM has a debug trace that outputs a line of data for each KS invocation that is also indented according to the nesting level. The KSM also keeps track of some KS statistics, and these appear in the summary narration. Getting all of the above done involved a lot of time doing code massage, but the result presents a good foundation for future development. -------- Upcoming work will be on KsSurveyor, KsPlanner, KsExplorer, and KsSelector knowledge sources. KsSurveyor produces a list of action items (an agenda of sorts) that describe interesting features (e.g., hung pieces, region control metrics, and potential targets) as identified by the pattern matching subsystem. KsPlanner takes the action item list and uses it along with the plan library and the pattern matching subsystem to produce a list of plans. KsExplorer takes a list of plans and tries to verify them via search; it returns an analysis for each plan exploration. The above are tied together by the general purpose KsSelector, and as might be guessed, there is a lot of direct and indirect recursion among all of them. KsSelector itself is first called by KsCandidateSelector when no quick/certain reply can be found by KsQuickSelector. KsSelector can also be called at interior nodes as needed. -------- The road is long and sometimes, like the past few weeks, it's two steps back then three steps forward. Hopefully I'll get the surveyor/planner/explorer system right the first time through and can then move on to adding chess knowledge to the pattern and plan libraries.
This page took 0.01 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.