Author: Landon Rabern
Date: 14:43:26 06/12/01
Go up one level in this thread
On June 12, 2001 at 17:13:20, Scott Gasch wrote: >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 What kind of collision resolution method do you use for your hash table?
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.