Author: Uri Blass
Date: 15:53:03 05/16/04
Go up one level in this thread
On May 16, 2004 at 18:06:44, Will Singleton wrote: >On May 16, 2004 at 15:25:23, Uri Blass wrote: > >>On May 16, 2004 at 12:39:48, Will Singleton wrote: >> >>>On May 16, 2004 at 08:30:48, Uri Blass wrote: >>> >>>>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). >>> >>>That's what I do. Easy and quick. >> >>I do not find it as easy. >>The problem is that I do not know a special function to do a binary search in a >>file and I do not like to try to write a special function for that purpose. >> >>There is bsearch that performs a binary search of a sorted array but I need to >>perform a binary search of a sorted file because I do not like to remember all >>the book in RAM. >> >>I start generating the book by doing qsort that performs a quick sort of an >>array. >> >>Now I need to copy the array to a file and I think that Crafty's solution is >>both faster and simpler than writing a special function to perform a binary >>search on a file even in case that the book is book of positions and moves and >>not book of positions like Crafty's book so alternatives 2 and 3 seems better >>for me and I think that 3 is the best alternative but before I try it I prefer >>to read what other people do. >> >>Uri > >Just write the function, it's not hard. I'll send you mine if you want. Thanks I still wait to hear how other do it. I may try to write a function to do a binary search but there are 2 reasons that I still did not do it: 1)Maybe there is some library function for binary search in files that I can use and I do not want to waste time of reinventing the wheel. 2)I have reasons to think that another idea is better because in a binary search you need to look at different places in the file and you start at the middle of the file(even if I search in the file than binary search does not seem to me a good idea and binary search is good when you have no idea at which part the position is). I believe that you can get practically a good guess of the right place to search based on the hash key and later better guess based on the result because I believe that the hash keys distribute uniformly(I did not check it). It means that if the first 20 bits of the hash key are 764 then it may be a good idea to look at the place that is after (764/2^20) of the file. 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.