Author: Uri Blass
Date: 02:44:55 05/17/04
Go up one level in this thread
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
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.