Author: Gerd Isenberg
Date: 13:10:36 07/17/02
Go up one level in this thread
On July 17, 2002 at 14:36:29, Dieter Buerssner wrote:
>On July 17, 2002 at 04:22:44, Gerd Isenberg wrote:
>
>>On July 17, 2002 at 02:23:52, Russell Reagan wrote:
>>
>>>Two things:
>>>
>>>1. How are most opening books stored? Are they in human readable move notation,
>>>or a binary representation?
>
>I guess, most will use a binary representation. But like in Gerd's case a
>intermediate human readable intermediate representation (which might be a PGN
>collection) probably is common, from which the binary representation is created.
>
>>>
>>>2. How do most programs interact with their book? I've heard of some schemes
>>>where the book is loaded into the transposition table and it simply works
>>>seamlessly from that. Is that the standard method?
>>>
>>>Russell
>>
>>I do it in the following way (kind of persistent hashtable):
>>
>>1. I use a readable file with all opening lines, algebraic notation with some
>>optional tags (!,=,?). Each opening line is one physical line separated by
>>CR/LF. They may include comments {some interpretable like +-, +=, ECO}.
>
>Very similar here. Although I do not necessarily need them to be on seperate
>input lines. Therfore some other means is needed to seperate the different
>opening lines, for example one (or more) PGN tag.
>
>>2. With this source file i generate a binary file. This binary represents an
>>array of structs like a transpositions table does. With hash index modulo table
>>size i seek to the appropriate struct, which containes hashkey, castle rights,
>>color to move and ep-information and a (lseek) pointer to a dynamic struct
>>placed in an appendix of the binary file.
>
>Also very similar here.
>
>>This dynamic structure contains all
>>the necessary information about the position, all the moves (including
>>probability to play) and also all source line indices that lead to this position
>>(for bookeditor reasons).
>
>However, I do not have a dynamical struct. The structs in the array have all the
>information needed for one position and one move. My pointer (=file offset,
>"lseek pointer") points is the start of a link list of additional moves of this
>position and/or different positions with the same array index (=hash key modulo
>number of entries in the array of structs). So I have to traverse the linked
>list, to find all opening moves in one position. This may sound a bit costly
>because of the several disk accesses, but is only a few milliseconds at max in
>practice.
>
>How do you work around the problem, that different position may yield to the
>same index in the array of structs? From reading the above, I cannot see it.
Not yet correctly handled. If a collision occurs, i only trace and look whether
the line/position was an important one. There was no one so far (the most
important lines are in front of the source and the table size is rather huge, so
that at least every second entry is free in average). But if, i fiddle around
with the table size. Not very professional - have to think about it.
>Another possiblility would sort the structs by hash index, and use a binary
>search to find the positions. No need for linked lists anymore, but some more
>effort while creating the binary representation because of the additional sort
>process, (or by generating it sorted from the beginning).
>
>>3. If i probe the table and there is no hit, i try it with the black/white
>>mirrored position, to look for reversed opening lines, where white possibly
>>looses one tempo.
>
>Did you check, if this is worth the work? Do you get now and then opening moves
>by the probing of the mirrored position? How often? Once in 10 games, in 100
>games? ...
Yes, i believe. And it's not much work to mirror the hashkey and some
coordinates and castle flags. I don't have exact statistics (unfortunately i do
not recognize/trace mirrored hits explicitely as mirrored). Against humans it
occurs quite often, specially in closed games. Some like to play 1.e3 e5(c5)
2.(or later)e4 to play their favorite black line with white, or simply to throw
the program out of book very early. I was often surprised while entering new
book lines that i hit a mirrored position from an other already stored line. I
recognized that the Book Editor suddenly showed the reversed position (generated
from the first stored line lead to this position) with one ply difference. It
was a few years ago, when i extensive worked with the book of my former Dos
IsiChess, so i can't remember exactly. There are lines, where a "hidden" tempo
loss leads to a superior position. Of course it's more common that both sides
loose a "hidden" tempo (sicilian svechnikov e5,Bg5 or e6,Bf4,e5,Bg5).
>Regards,
>Dieter
Thanks Dieter, to point out some weak points and give me some suggestions.
Regards,
Gerd
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.