Computer Chess Club Archives


Search

Terms

Messages

Subject: BookLearning Under the Microscope!!!

Author: Robert Henry Durrett

Date: 10:13:07 08/31/98


I. RELATED BULLETINS:
(a)	Re: Please Explain the Book Learning Feature of Chess Engines
posted Saturday, August 29, 1998 9:47 PM to r.g.c.c. by Bob Hyatt
(b) Re: Middlegame Dilemma: Variety Vs Strength? Posted by Serge Desmarais on
August 30, 1998 at 07:50:27 on CCC
(c) Re: How Do Chess Engines Treat Tabyias???  [last paragraph only] Posted by
Serge Desmarais on August 31, 1998 at 05:19:33 on CCC

II. GENERAL OBSERVATIONS
(1)	Thanks to Bob Hyatt, the computer code for Crafty is available for study so
that skilled computer programmers [like Serge Desmarais] can examine the code
and deduce the algorithms codified in Crafty and maybe deduce the underlying
theory behind Crafty's code.  Bob also provides some of this information in the
c source file "learn.c."  As noted by Bob Hyatt and others, this type of
information, unfortunately, is not available for commercial chess engines.  What
a pity!  The commercial programs may do things entirely differently from the way
Crafty does it, but we'll never know.
	(2)	After reading the three referenced bulletins, I now have the impression
that "booklearning" [Is this the same as "autolearning"?] is used for one of the
following purposes:
(a) Creating, modifying, or expanding an opening book.  This may be the book
provided with the chess-playing program or it may be one provided/created by the
user.  Generally, but not necessarily, the purpose would be to come up with a
book which was better for some purpose.
(b) Providing variety in the play of the chess-playing program, during the phase
of the game where that program is still in it's book.
(c) Some combination of the above two.
(3) If the purpose was solely to create, modify, or expand an opening book, then
the quality of the resultant book would depend on the intended use of the book,
the quality of the games used, and the degree of sophistication or quality of
the implemented method for "booklearning."  For example, if one were to start
with a small book and then play or enter many games with booklearning enabled,
then a large book might be produced.  Whether or not the resulting book would be
any good or not would depend on the quality of games used, and the quality of
the method used for booklearning.  If a very good sophisticated booklearning
method were used, then the end product might be good even if the games used were
relatively poor.  On the other hand, if a simple unsophisticated booklearning
method were used, but the games played &/or entered were of outstanding quality,
then the end product might still be good.  Ideally, you would use both:  an
outstanding booklearning method and an outstanding collection of games.
(4) If the purpose was solely to provide variety in the play of the
chess-playing program, during the phase of the game where that program is still
in it's book, then it would not be necessary to add or delete chess positions at
all from the initial database.   See below for a method for doing this.
(5) If a chess-playing program had already exhausted it's options for varying
the play against a given opponent, then it would become necessary to expand or
otherwise modify the book to achieve any additional variety.
III. BOOKLEARNING TO ACHIEVE VARIETY:
(1)	Due to the limited space available for bulletins, I will provide only a
thumbnail sketch here.
(2) A book can be implemented as a collection of elements where each element
consists of a "position" plus some other information including a list of the
positions [in the collection] from which the given position can be reached in
one legal move, a list of the positions [in the collection] which can be reached
from the given position in one legal move, an evaluation of the given position,
a number representing "probability of being played," etceteras.  In this case, a
"position" would include information as to which pieces were on which squares,
whose move it is, whether or not the kings have moved, and similar information.
[The initial position and the leaf positions would be similar but with their
information slightly different.]
(3) Similarly, a chess game can be represented as a similar collection of such
elements, where certain criteria must be met.
(4) A "complete book" created from a collection of games could be defined as a
tree such that each leaf is associated with only one game in the original
collection of games from which the tree was constructed.
(5) One could define a "pruned book" as being one in which one or more of the
elements in the original book had been deleted.
(6) An "opening repertoire" can be created by suitable pruning.  For example, if
a strong opening repertoire for White were desired, one could prune the original
complete book by deleting all leaf positions in which Black had achieved full
equality or better, and by also removing all branches associated with the
removed leaves.  As a second example, if it were desired to create a White
opening repertoire which offered a handicap to the chess-playing program's
opponent, then only those leaves which gave Black a small advantage would be
retained, and all the rest of the leaves removed, along with their associated
branches.
(7) Given an "opening repertoire" constructed in the above manner, then variety
could be achieved without adding new positions by simply jumping from one leaf
to another from one game to the next.  There is not sufficient space here to
present an algorithm for doing so, but it should be obvious that a strategy
could be implemented to achieve maximum variability.
(8) Note that, in the general case, the initial position [or the current or
starting position] is connected to a given leaf by one or more "paths", where a
path is an ordered sequence of the elements {roughly, "positions"} discussed
above.  This could be seen by pruning the tree [book] to remove all elements not
in at least one path between the starting position and the leaf.  Hence,
additional variety can be achieved by varying the paths, even to the same leaf.
(9) After all of the leaves and alternative paths have been exhausted, then
additional variety would be achieved by modifying the opening repertoire.
I probably have used as much space as allowed, so will quit here.  But, there is
a lot more that can be said.



This page took 0.02 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.