Author: Steven Edwards
Date: 10:52:53 08/13/05
Symbolic: Status report 2005.08.13
I haven't been able to spend much time at the keyboard the past month or so, but
I have been able to accomplish a few minor tasks and one major task:
Task 1: Symbolic's toolkit got a new routine that efficiently counts the moves
in a position without the overhead of move generation. Also, a related routine
was coded that quickly detects whether or not there is at least one move
available in a position; this is done without even the overhead of counting. It
is a bit surprising to see the number of places in the code where the above
routines can be used productively. These functions were also made available to
Symbolic's Lisp code directly via ChessLisp intrinsics.
Testing of the above was done using the toolkit's movepath enumeration routines.
("Movepath enumeration" is a synonym for "perft".) Running movepath
enumeration from the initial position and without a transposition table now
takes about 125 clock cycles per movepath, a rate of about 8 MHz on a 1 GHz
machine. This is almost six times faster than Crafty's perft, although
undoubtedly the movepath enumeration speed in Crafty could be similarly
improved.
Task 2: Overall pattern instance management has been improved to better
facilitate adding new instance kinds and to support commentary. This has
resulted in new code that is perhaps one percent slower but has a much more
intuitive collection of interfaces. A similar change was made to knowledge
sequencer management.
Task 3: The data interface between Symbolic's Lisp code and the toolkit has been
changed from a property list to an association list. This interface had been
the last property list used in the project. The idea behind the change was to
make the whole system a bit more uniform and very slightly more efficient.
Also, for reasons that take too long to explain, the change makes it easier to
restart Symbolic's Lisp code interactively without having to manually command
recycling of storage used by prior invocations.
Although the significant chunk of code in the ChessLisp interpreter that handles
property list operations is now dormant, it was not a waste of time to implement
this support. First, it helped enable testing of the interpreter using textbook
Lisp samples. Second, it's possible that property lists in Symbolic might make
a comeback if a new use is discovered for them.
Task 4: Cross platform testing uncovered an operational dependency of the
toolkit's NextSq bitboard scanner when assembly language assists were used in
conjunction with a PowerPC as the target platform. Unlike all other
configurations, the above assembly/PPC combination had the squares ouput by
NextSq in reverse file order (i.e., the sawtooth anomaly). Fixing this problem
in turn caused a couple of other hidden assumptions of file square order to
appear, and these also were squashed.
Task 5: Whenever the bitboard support code is adjusted, I re-enable Symbolic's
rotated bitboard support via compile time option and run some benchmarks. And
as in the past, using rotated bitboards causes an average two percent slowdown
on movepath enumeration tests. Although using rotated bitboards surely causes
significantly fewer instructions to be executed, the resulting overhead of the
increased memory bandwidth requirement eats all the savings and then some. Most
likely, this tradeoff could go the other way if I were using somewhat more
modern hardware.
Task 6: And here is the major task; I've managed to design and implement a
general pattern matching scheme based on the predicate calculus and using
instance variables. This included the development of a production language
(similar in spirit to the pattern language in Wilkins' MacLisp program
Paradise), complete with a compilation phase for improved run time performance.
The pattern matcher is in some respects a close relative of a Prolog
interpreter. It understands constants, variables, and expressions; plus, it
can perform an implicit depth first search through an instance space.
An example may be better than a long winded explanation. Here's an actual
working tactical production in Symbolic's production language:
(Production PnOverworkedDefender
(Name "Overworked Defender")
(Comment "Find a defender that can't be in two places at the same time.")
(Needs PnBasic)
(Declare
(InstVar $AMan0 IkMan (ActMover IsNotKing HasSimpleCaptures))
(InstVar $PMan0 IkMan (PasMover IsNotKing IsAttacked HasSingleDefender))
(Satisfy (Attacks $AMan0 $PMan0))
(InstVar $Move0 IkMove (IsSimpleCapture))
(Satisfy (= (QFrSq $Move0) (QAtSq $AMan0)))
(Satisfy (= (QToSq $Move0) (QAtSq $PMan0)))
(InstVar $AMan1 IkMan (ActMover HasSimpleCaptures))
(Exclude (eq? $AMan0 $AMan1))
(InstVar $PMan1 IkMan (PasMover IsNotKing IsAttacked HasSingleDefender))
(Exclude (eq? $PMan0 $PMan1))
(InstVar $Move1 IkMove (IsSimpleCapture))
(Exclude (eq? $Move0 $Move1))
(Satisfy (= (QFrSq $Move1) (QAtSq $AMan1)))
(Satisfy (= (QToSq $Move1) (QAtSq $PMan1)))
(InstVar $PMan2 IkMan (PasMover IsDefending))
(Satisfy (and (neq? $PMan0 $PMan2) (neq? $PMan1 $PMan2)))
(Satisfy (and (Defends $PMan2 $PMan0) (Defends $PMan2 $PMan1)))
(Exclude (CanAttackFrTo $PMan2 (QAtSq $PMan0) (QAtSq $PMan1)))
(TempVar $Gain0 (ExValue3 $PMan0 $AMan0 $PMan1))
(Satisfy (plus? $Gain0))
)
(Actions
(Post IkOverworkedDefender
(
(AMan0 $AMan0)
(AMan1 $AMan1)
(PMan0 $PMan0)
(PMan1 $PMan1)
(PMan2 $PMan2)
(Move0 $Move0)
(Move1 $Move1)
(Gain0 $Gain0)
))
)
)
When the above is applied to the position:
[D] 4k3/8/8/3n4/8/2p1n3/8/1N2K1B1 w - - 0 1
The matcher quickly produces the two instances of the OverworkedDefender
pattern:
OverworkedDefender wBg1 wNb1 bNe3 bPc3 bNd5 Bxe3 Nxc3 +0.920
OverworkedDefender wNb1 wBg1 bPc3 bNe3 bNd5 Nxc3 Bxe3 +1.000
From these, Symbolic's planner can (someday soon, I hope) formulate two simple
plans with the PVs:
1. Bxe3 Nxe3 2. Nxc3
and
1. Nxc3 Nxc3 2. Bxe3
And these can be verified by the plan explorer to see if they are really valid.
So the program effectively performs a three ply search that looks at only six
nodes, just as a human might do in the above case.
The older productions have been re-written using the new format and appear to
survive testing.
Paradise had about two hundred tactical productions. I'm guessing that Symbolic
will need about two thousand tactical and positional productions in its library
to be a well rounded tournament player of master strength, so there is a great
deal of more work needed. But it is not an impossible task, just a long one.
--------
Questions:
Is it feasible or even possible to construct a Huge Plan Catalog with a separate
production for each potentially useful plan template?
Can a significant number of plans be constructed via high level productions that
assemble subplans produced by earlier executed, lower level productions?
Can production specifications be organized via a non cyclic, hierarchical
dependency graph? If not, some productions may have to be run more than once;
how can this be controlled to avoid unneeded processing?
Is it reasonable to rank productions using a cost to benefit ratio? If so,
could such a ratio be used to selectively activate productions based on how much
time is available for a search?
How might it be possible to partially automate the process of writing
productions?
Can the productions be automatically evaluated for merit? If so, is it
reasonable to have a feedback loop to implement a simple form of program self
adaptation?
If multiple developers shared the same production language and instance
structure, could there be a distributed effort for the writing of productions?
--------
More to come. The probable near term topics are all related to Symbolic's
productions and the production system framework. A major uncertainty at this
point is manner by which productions ultimately generate and post plans.
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.