Author: Andrew Williams
Date: 04:01:38 06/20/00
Go up one level in this thread
On June 20, 2000 at 01:18:03, Will Singleton wrote: >On June 19, 2000 at 21:10:56, William Bryant wrote: > >>Not having a computer science background, I wonder how people organize their >>opening book to make move lookup efficient. >> >>I have heard that people index by hash signature. Do you then clusture all the >>subsequent moves together, or are they spread out throught the table? >> >>What means do you use to index into the table? >> >>In general I am looking for a general or specific discussion of how to oraganize >>the data of an opening book and accessess it efficiently. >> >>You can guess, this is next on my to do list and I could use some >>recommendations, instructions, suggestions, or even a step by step manuel, >> "Opening Books for Dummies". >> >>Thanks in advance, >> >>William >>wbryant@ix.netcom.com > > >There are many resources for opening book methods on the web and elsewhere. My >opening book is rather basic, so I have nothing to offer directly. However, you >might want to check the homepages of the various programmers here, perhaps check >out all the links available from this site and the many others. If that fails, >I recall Andrew Williams having posted a succinct intro to opening book design, >which I saved but haven't had time to examine in detail. And there's always the >many book articles in the ICCAJ which cover the subject nicely. Maybe Andrew >will post his article again. > >Will Hi Will Here's the stuff you were referring to. I'll put it on my web page if I ever get ten minutes to myself. Andrew Creating the book ================= PostModernist's opening book is made up of games from Dann Corbit's site. I process the pgn file and create what I call a "binary" book, which consists of records with the following information: * Hash key (same as the one I use for my hash table) * WhiteWins (ie how many times has this position occurred in games which were eventually won by White). * BlackWins (see above) * Draws (see above) I convert the pgn file(s) using the following process: 1 Read in a game. 2 Keep track of the result (white won, black won or draw). 3 Starting from the beginning of the game I do this: 3a Generate the hash key for this position. 3b Create a new book record for this position. (or if the position is already in the book, I just update the existing book record. 3c Depending the result of the game, I increment the appropriate field in the record. 3d Read the next move in the current game and go back to 3a. 4 When I've completely processed one game, I read in the next game and go back to step 1. Once this process is complete, I have an opening book which consists of a set of positions that have occurred in the games from which I created the book. For each position, I know how many times White won, how many times Black won and how many times the game was drawn. The positions are indexed by the 64-bit hash key. Using the book ============== Suppose PM is playing White. It does this: 1 Generate all the moves from the starting position. 2 For each move do this: 2a Make the move on the board. 2b Generate the hash key for the resulting position. 2c Look in the opening book for the position. 2d If the position is present in the book, create a "score" for the position based on the WhiteWins, BlackWins and Draws fields. At the moment, I use WhiteWins+Draws as the score (assuming PM is playing White of course). 2e Keep a record of the move and score. 2f Unmake the move. 2g Get the next available move (from those generated in 1) and go to 2a. 3 Once these steps are done, I have a list that looks like this: Book move: b3 score: 104 Book move: c4 score: 2180 Book move: d3 score: 26 Book move: d4 score: 11191 Book move: e4 score: 14800 Book move: f4 score: 115 Book move: g3 score: 235 Book move: Nh3 score: 2 Book move: Nf3 score: 3105 I then use a random number to select amongst these options In step 2d, you can be quite creative about how to score the positions. eg assuming PM is playing White, I exclude any position where WhiteWins+Draws < 1.5*BlackWins. For many reasons, using these frequencies is not a foolproof way to select moves in the opening. Therefore, some programs (most?) also include a SearchScore field in their book records, which reflects the score for the program if the position is actually searched (as opposed to selected by frequency). This raises two problems: (a) When do you fill in this field? (In the description above, you would NEVER search the position if you've got frequency information in the book). (b) How can you compare frequency scores with search scores? Bob Hyatt wrote an article about book learning in a recent issue of ICCAJ which answers both these questions.
This page took 0.01 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.