Author: Dan Newman
Date: 02:02:24 04/22/99
Go up one level in this thread
On April 20, 1999 at 11:00:08, James Robertson wrote: >I have become dissatisfied with the way my program searches for moves in it's >book; it simply takes too long. How do other programs do this? If I look at the >Crafty bookmaking code, I see stuff about "clusters". What does this mean? How >do EXchess, or Comet or other programs search their books? > >Thanks for any help! >James As I understand it, Crafty's book generating code clusters together positions that have the same parent position. This drastically reduces head motion when searching for positions arising out of the current position. The OS will also snarf up more of the file than you initially ask for and this will also save a lot of time since many of the positions will already be in memory when you look for them. The way Bob does this is to associate a key with each book entry that is constructed partly from the position's hashcode and partly from the parent's hashcode so that when he sorts the entries those that have the same parent position will tend to be close together (the low order bits being from the parent). (What I don't yet understand about this trick arises from the fact that positions can and do have more than one parent. So how can you properly accumulate win/loss/draw counts for each position if the position occurs multiple times in the book, each time with a different key? I would assume each of these should have the same win/loss/draw counts, learn value, or whatever.) What I do is simply use the position hashcode and sort the positions into clusters that have the same last N bits. (I think this organization works quite a bit slower than Crafty's because I have to grab whole clusters of entries all over the disk -- one for each position -- whereas Crafty needs to look only at one cluster.) The way I get at the clustered entries is to have a table of 2**N offsets into the book entries so that I can get to these clusters more or less instantly -- this table is stored at the head of the book file. (I think Bob does the same thing.) Then I just linearly search the cluster for the proper entry. A binary search should be somewhat faster, but I haven't tried that yet. Anyway, I suspect I'm limited to something like 5 or 10 moves/s with my scheme. -Dan.
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.