Author: Ed Trice
Date: 06:01:51 05/16/04
Go up one level in this thread
One thing you can do is stratify the different types of information you intend to store into different tables, rather than lump information together and complicate the lookup. Example: Each position takes up N bytes per entry, learning information takes up M bytes per entry, annotations or notes can take up a varying length per position, etc. Construct your book database in such a way that you refer to all of the information by index. Translate your position into a unique index, Q. You can find the information you seek by probing each table at byte [(Q-1)* the size per entry]. Disk space is cheap. This technique is cheap. But if you ever change the format of your data (adding or removing different types of information that you want to store) you only need to add or remove tables (easy), or just change the "size per entry" parameter when performing a lookup after you do a data conversion to the newer format. >Suppose that you have a book of 2^20 positions. >Suppose that you need in average 16 bytes for every position(to store >positions,moves and some more information like learning value for every move). > >I do not like the idea to store only positions in book and I think that the the >job of making all moves in book positions to find more book moves can be done in >the time of creating the book. > >I can think of 3 ways to find if a position is in book > >1)To do a binary search in the file that has the positions(Disadvantage:you do >more searches in the file relative to other ways and you basically need to probe >the file 20 times only to find if a position is in book). > >2)To have a special file that has the exact place that you need to search based >on the last 20 bits of the hash key(disadvantage if you add a single position to >your book you may need to change almost 2^20 numbers in this file because if the >place of one position is changed the place of all positions after it is changed) > >3)Not to have a special file of the exact places but to know the right place to >search because you know that your book has 96 bytes for every 20 bits of the >hash key when usually part of the bytes have meaningless 0's. > >Distadvantage:Your book is bigger than neccesary(96 Mbytes instead of 16 Mbytes) >and there is a risk that it is not going to be enough to store all the positions >and moves(the main problem is not having many positions with the same last 20 >bits in the hash key but having many moves for the same position that can >increase the bytes that you need for one position significantly if you need 4 >bytes for every move). > >Uri
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.