Author: Steven Edwards
Date: 11:05:13 03/08/05
Symbolic: Status report 2005.03.08
A review of the existing ChessLisp source for the support of pattern matching,
the IDB (Instance Data Base), and plan representation has shown that
positionally dependent parameters in the lists that link these together are
adding too much complexity. To allieviate this, I've redesigned the various
linking mechanisms to now be Lisp association lists.
In ChessLisp, just as in Lisp, an association list is a mechanism for binding
values to symbols. Each element in an association list is Lisp cons pair. The
Lisp car of the pair is (usually) a symbol (i.e., a tag), and the Lisp cdr of
the pair is the symbol's (tag's) value. Unlike Lisp vectors or simple lists,
the elements in an association list are position independent. Having such
independence along with the means for labeled access removes a significant chunk
of the semantic load on the programmer during development. Other Lisp
mechanisms for symbol binding in aggregate objects include property lists and
Lisp defstructs. The former requires an additional symbol to act as an anchor
and the latter was not implemented in ChessLisp.
Regular Lisp has several primitive functions for accessing association lists.
These include: acons (constructor), assoc (element fetch), rassoc (reverse
association element fetch), and pairlis (another constructor). ChessLisp has
all of the above primitives, plus several more I've added: tassoc (test if an
association tag exists), vassoc (fetch the value of the indicated tag), nassoc
(insert/update new association), alv-push (push a new value onto the list that
is the value of the indicated tag), and avl-pop (reverse of avl-push).
A programming convention in Symbolic is that each association list is
initialized by the association list factory routine:
(defun MakeAL (MyIsA)
"Return a newly constructed association list with the given IsA symbol."
(cons 'IsA MyIsA))
Because each association list in Symbolic has an IsA binding, it is possible to
have general debugging and display routines that operate on these lists. Also,
if needed, diagnostic tags can be added at list creation time that define the
list generation ordinal, the caller of the factory, and other potentially
revealing information.
A more specific association factory is the one that creates an analysis result:
(defun MakeAnalysis (MyMVs MyScore MyIsCert)
"Return a newly constructed analysis."
(let ((Result (MakeAL 'Analysis)))
(nassoc 'MVs Result MyMVs) ;; The predicted variation
(nassoc 'Score Result MyScore) ;; The expectation
(nassoc 'IsCert Result MyIsCert) ;; The certainty indication
Result))
Of course, an association list may have subsidiary association lists as
associated values, and this is required for the morle complex association lists
that represent pattern matches (instances).
--------
An IDB (Instance Data Base) is a collection of instances and is (usually)
attached to a node in Symbolic's position tree. Each instance is an association
list that is the result of a pattern matching operation. Pattern matching is
performed by productions (each a snippet of Lisp code) that access an IDB and on
occasion, some non IDB objects. An IDB is represented as a list of two equal
length vectors and indexed by the pattern enumeration type. For each pattern
type, the first vector contains an integer giving the total instances (so far)
generated for that IDB; the second vector contains the instances for the
pattern. This top level vector organization is used in the hope that grouping
instances together by pattern type will lead to greater pattern matching
efficiency.
An IDB can be considered as a communal blackboard where the productions read and
write facts, suggestions, guesses, plans, results, and other chess items of
interest. There will usually be an IDB attached to the root node of the
position tree and also at each node where extensive work (e.g., planning) needs
to be performed. Also, an instance in an IDB may refer to a different IDB; this
is a means by which results may be shared at different times in a search and
also by different searches.
--------
At the current time, an instance is created by the factory:
(defun MakeInstance (MyPsi MyPoster)
"Return a newly constructed instance for the given pattern symbol index."
(let ((Result (MakeAL 'Instance)))
(nassoc 'Pattern Result (vref PatternSymbolVec MyPsi))
(nassoc 'Psi Result MyPsi)
(nassoc 'Poster Result MyPoster)
(nassoc 'Ordinal Result nil) ;; Actual value filled in when attached to an
IDB
(nassoc 'Commentary Result (MakeAL 'Commentary)) ;; Actual value(s) filled
in later
Result))
Instances for different pattern types will have different association tag sets
although certain tag symbols will be present in all instances and have the same
meanings. The exact pattern type set definition is still under development.
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.