Author: Duncan Roberts
Date: 09:15:36 01/11/05
Go up one level in this thread
On January 11, 2005 at 11:00:00, Andrew Williams wrote: >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 may I ask if you were planning on trying out uri's excellent idea ? thank you duncan
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.