Author: Andrew Williams
Date: 08:00:00 01/11/05
Go up one level in this thread
On January 11, 2005 at 09:49:08, Steve Maughan wrote:
>I'm starting to think about adding an opening book to Monarch and I'd appreciate
>advice or insights than anyone may have. There seems to be (at least) two ways
>to internally manage the opening book information:
>
>1) For each position store the Hash Value and weight for all candidate moves.
>Monarch would then probe for each possible move to see if it finds a match;
>playing a weighted random move from the ones it finds. This has a couple of
>advantages - firstly it's relatively simple and handles transpositions. There
>are two possible problems that I see. Firstly, the transposition may be silly
>e.g. take the following game:
>
>[Event "?"]
>[Site "?"]
>[Date "2005.01.11"]
>[Round "?"]
>[White "?"]
>[Black "?"]
>[Result "*"]
>
>1. d4 e6 2. Bg5 Nf6? *
>
>The move 2. Bg5 is an error and black can win with 2... Qxg5. However 2...Nf6
>takes black back into the book. I guess you'd get around this by only playing
>moves if the root position is also in the book - so this may be a minor
>disadvantage. Any comments?
>
Ignore it.
>The second disadvantage is that if you have 30 possible moves and you're doing a
>binary search of a large opening book this may take about 20 probes per
>candidate move. This would mean about 600 probes per position - this seems a
>lot to me (although I have little experience in this matter). I guess it would
>be reduced if Monarch first probes the root position and then only go on to
>probe the candidate moves if the root position is found. Can anyone comment of
>the time / cost of probing the hash table this many times for each position?
>
Suppose it's the starting position and PM is playing White. What PM does is:
(1) Generate all moves (there will be 20 of course).
(2) ForEach move:
(2a) Make the move on the board (and thereby generate the hash key for the
new position)
(2b) Look in the binary book file for a record with that hash key
(there will be 1 or 0 records for each hash key)
(2c) Get the scoring information from the record it finds. The scoring
information is created when the book is constructed. It records the
number of white wins, draws and black wins that were found in the big
set of games that were used to create the binary book.
(2d) Unmake the move
(3) Generate a random number and choose between the moves identified in (2),
weighted by the score; the better the move the more chance of choosing it.
(4) Make the selected move in the game.
PM is a bit more complicated than that, because it also has a preferred book,
which is used to force it to favour certain openings over others. The "scores"
in the preferred binary book are not based on the results of games, but rather
on scores *I* choose. I annotate moves with !! or ?? etc to force the behaviour.
In extreme situations, I can use this to solve your "first disadvantage" above,
although not the particular situation you mention.
>2) The second possible opening book format would store the hash value of the
>root position along with some form of linked list of candidate moves. This
>would reduce the number of probes but would add complexity to the internal
>structure. I think YACE uses this format.
>
>Are there any other methods? What have I missed? What do you recommend?
>
>Thanks,
>
>Steve Maughan (Monarch)
Cheers
Andrew
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.