Author: David Mitchell
Date: 01:44:43 05/20/04
Go up one level in this thread
On May 17, 2004 at 05:44:55, Uri Blass wrote: >On May 17, 2004 at 04:17:45, David Mitchell 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). >>> >>>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 >> >>Just was reading this in the paper on Rookie 2.0. Lots of info on Rookie's >>program, but the simple answer is that yes, it stores all positions in it's >>opening book. Biggest advantage is to easily allow transpositions back into some >>book line, after an unusual move by the opponent, and to allow easy programming >>of the book learning feature. > >I think that tranpositions can be calculated in the time of creating the book. >I think that for learning there should be additional file that has >(position,father,move,father,move...) format so after you lose a game you reduce >the learning value of every move of a relevant father. > >I prefer to think about the task of making book not as one very complicated task >but as task that there are steps for impeovement. > >When I work I want to see progress and in the way that is suggested by Rookie2.0 >or Crafty you need first to do a lot of work only to have a book that you can >tranpose back into some book line(for example after 1.d4 e6 when you have only >2.c4 in your game but you have 1.e4 e6 2.d4 in your games). > > >In the way that I suggest you can start with book that does not know about this >tranposition stuff and later add it. > >You first have only (position,move) book and you can start with simple learning >by reducing the learning value of (position,move) that leaded to a loss so you >will not learn to avoid tranposition but it is better than no learning. > >Later you can improve your book and your learning by adding the additional >information that I describe. > > >> >>To cut down on size, Rookie color adjusts all positions, regardless of whose >>turn it is to move, as if it were white's turn to move, adjusting the board if >>necessary. > > >I also thought about this idea but I think that as first implementation I will >have a book without it. > > Along with the position itself, Rookie 2.0 keeps data on the >>percentage of games won from this position by the side to move, and the number >>of times this position has been found in it's database of games used to create >>it's book. >> >>As mentioned elsewhere, the positions are then sorted lexicographically, and the >>search to find it is a binary search. > >I wonder if a binary search is a good idea. >binary search means that you starts to search in the middle of the file but I >think that there is a better guess. > >binary search is needed when you know nothing about the size of the elements in >the file but it is not the case with many hash keys. > > > To be considered for a book move, the >>position before, as well as the resulting position, must both be in the book. >> >>The rookie 2.0 paper is some 75+ pages or so, but worth reading. I'm sure you >>can google it up. Bound to give you some good idea's. >> >>My experience with binary searches is that they are faster, and more efficient >>than you are giving them credit for. > >They may be fast but if I can do it even faster without doing more work(I do >not >know if writing a special program to do a binary search in a file is simpler >than writing a special function to guess the right place not based on binary >search). > >Uri If you try the binary search you will be very pleased. But try both and come back and tell us how the two search types compared in tests. The binary search is very simple to code up, (I'm curious what search you might be as easy!), and one beauty of it is that as the opening book increases in size, even if it should double in size - that only causes *one* more comparison to be made in the binary search. e.g. for 1,000,000 positions, the binary search will need to compare about 20 positions, to the search value. For 2,000,00 positions, the number of comparisons only increase to 21. Amazing, to me. (The joy of having a simple mind is that it's easily amused) :) I think of the binary search the same way I think about Quicksort. IMO they are two of the best building blocks ever coded up for a program to use. And they're similar - each has a very small inner loop, a high range point, a low range point, and a median or pivot point, which is repeatedly compared to other points as the program progresses. As mentioned previously, one added benefit for speed and less work for the disk, is Window's way of taking in a large chunk of data from the disk with every read it makes. So in effect, one disk read may get all the data for one binary search, and put it all in a disk cache for really quick retrieval from memory. Good luck, whatever you choose, Uri. Dave
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.