Computer Chess Club Archives




Subject: Re: BookLearning Under the Microscope!!!

Author: Robert Hyatt

Date: 13:24:48 08/31/98

Go up one level in this thread

On August 31, 1998 at 13:13:07, Robert Henry Durrett wrote:

>(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
>(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.

very likely right.  The only "commercial" group I know about is the Fritz
effort, and they reported that they basically took the ideas inside Crafty
and added them to Fritz...  There probably aren't a lot of different approaches
available, when you think about it, because adding or deleting book lines is
not exactly a broad area of computer chess.  :)

>	(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.

Note that the best way to provide variety is to simply take existing games from
the network and build a book from them, updating from time to time to be sure to
have recent theory available.  But lots of these games have blunders or severe
mistakes, and that's the purpose of "learning" as I have implemented it... to
cull moves automatically that I used to have to cull by hand in Cray Blitz...

>(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.
>(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
>(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.

this is doable, but the time-frame for such learning would be very slow... ie
you would cull a line after playing and losing...  But you really need to do
more than that, because the last choice you made in book might not be the move
that lost.. it could have been a couple of choices back from there...  which is
what makes it interesting...

>(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.03 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.