Author: Scott Gasch
Date: 14:13:20 06/12/01
Go up one level in this thread
Hi, I've read a couple of posts about books today and been a little confused as to what other people are doing. I'll describe my scheme here, feel free to comment. Hope someone finds it useful. My book is all on-disk. It's probed only before calling search. I stop probing after I miss N times (N = 7, I think. But its arbitrary). The speed of keeping the book in memory would be nice... I think it would be cool to hit such an "in-memory" book during search too... but my memory is just too small and my book too big. The book file structure is simply an array of entries sorted by position signature. Each entry contains a signature, a next move, game result information, and a bitvector of flags (disabled line, deleted line, play only this line, etc...). So one drawback of my book code is that if there are N book moves in position P, there are also N book entries... P+M1, P+M2...P+MN. I don't really care about this though. The alternative is to have one entry with many moves in it... but this is messy becasue either you have a variable sized entry or you waste empty move slots when there are not many book moves in a position. The probing operation consists of binary searching in the book file and selecting a next move. Using a formula based on "winningness" and "popularity" I assign a weight to each book move in a position (ones I think are lame get weight=0) and then select randomly (higher weights = higher chance of selection). The book code can be switched into "tournament" mode also where it always plays the "heaviest" move. This makes engine play predictable, though, so I only do it when I am watching it play / when its in a tournament game / when I am trying to leech rating points from ChesterX. ;) Therefore I don't understand Bob's issues with transposition. If the game goes e4 e5 Nf3 a6 Bb5, because my signature has side-to-move in it and is based on present position and next move, this would be a book miss. This position has never been seen in a GM game and the engine would simply search and pick off the B. I do book learning at the end of a game that can be learned from (result to an appropriately rated opponent -- win vs. higher or same, loss vs. same or lower, draw vs. same in a non-bullet time control) by running down my list of moves and updating the result fields in the appropriate book entries, if found. The worst thing about my book format is this: its hard to add new position-move entries once the book is built. This is becasue, of course, the whole book needs to be ripple-shifted in order to open a hole for the new position and keep the book in sorted order. My book is about 60Mb right now so the process is too slow to add new book lines on the fly. The book is initially constructed by parsing PGN files, playing the game on a board data structure, and then sticking the position-move pairs into a linear-probing hash. I use a huge hash and when it gets very full, strain out positions with only one appearance. At the end of PGN processing I simply sort the hash and write it to disk. Hope this help. Also, I'm interested in comments / ideas / questions. Scott
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.