Author: Robert Hyatt
Date: 07:49:09 05/08/04
Go up one level in this thread
On May 08, 2004 at 03:05:54, Uri Blass wrote:
>On May 07, 2004 at 22:14:10, Robert Hyatt wrote:
>
>>On May 07, 2004 at 22:06:49, Uri Blass wrote:
>>
>>>On May 07, 2004 at 20:52:10, Robert Hyatt wrote:
>>>
>>>>On May 07, 2004 at 19:51:42, Uri Blass wrote:
>>>>
>>>>>I looked at the code of Crafty to understand what it does when it creates the
>>>>>opening book(the function BookUp()).
>>>>>
>>>>>1)I see that it it is using malloc to allocate memory.
>>>>>I have no malloc in movei and I use calloc to allocate hash tables.
>>>>>
>>>>>I find that Crafty has no calloc but many malloc and my question is if there is
>>>>>a reason for that.
>>>>
>>>>Nope. Just a long-time C programmer using what he has been using for 25+ years.
>>>> :)
>>>>
>>>>
>>>>>
>>>>>2)I understand that crafty first translate pgn to book positions but I do not
>>>>>see moves in the following structs
>>>>>
>>>>>typedef struct {
>>>>> BITBOARD position;
>>>>> unsigned int status_played;
>>>>> float learn;
>>>>> int CAP_score;
>>>>>} BOOK_POSITION;
>>>>>
>>>>>typedef struct {
>>>>> unsigned char position[8];
>>>>> unsigned char status;
>>>>> unsigned char percent_play;
>>>>>} BB_POSITION;
>>>>
>>>>
>>>>I don't store moves. I make a move and store the resulting 64 bit hash
>>>>signature only...
>>>>
>>>>
>>>>
>>>>>
>>>>>
>>>>>My question is where does Crafty save the moves.
>>>>
>>>>I don't. In a given position, I make a move, which updates the hash signature.
>>>>If that signature is found in the book file, then that move is a "book move". I
>>>>repeat for all legal moves and therefore produce the set of known book moves...
>>>>
>>>>
>>>>>
>>>>>I remember that I read that another program (Tao) save only positions in the
>>>>>book but it seems to me a bad idea for reasons that Dieter gave because the
>>>>>program may go to a book position instead of playing a better move.
>>>>>
>>>>>book should include positions and moves.
>>>>
>>>>
>>>>Perhaps. There is a solution. If the before-the-move position is not in the
>>>>book, but the after-the-move position is, then you are taking a slight risk to
>>>>go back into book without searching to see if there is anything better...
>>>
>>>Yes
>>>
>>>I think that you are right and if you check that the before position is in book
>>>then book based on position is clearly better because in book of position move
>>>you may have only a single reply and book based on positions may give you more
>>>than one reply and if you have a score for every move then there are chances
>>>that you will choose better move.
>>>>
>>>>
>>>>
>>>>
>>>>>
>>>>>3)If I understand correctly Crafty first remember the book in a big array and
>>>>>only later sort the big array by BookSort and later copy it to a file.
>>>>>
>>>>>I do not understand what BookUpNextPosition does and what reason there is to
>>>>>return the least (lexically) position key.
>>>>
>>>>It forces all book positions with the same "parent" position to be adjacent in
>>>>the book file. Now I don't have to randomly probe all over the book to find if
>>>>a particular move leads to a known book position. I index to the "cluster" that
>>>>contains all of those positions with a common parent position, and read that in
>>>>once and search thru it for each possible move from this position. This is
>>>>mainly to make it very fast.
>>>
>>>What do you mean in the word parent position
>>>Do you mean that the hashkey>>49 is the same or do you mean that they are the
>>>sons of the same position(for example you can say that positions after 1.e4 and
>>>after 1.c4 have the same parent position that is the opening position)
>>
>>What I do is the leftmost 16 bits come from the position before the move, the
>>rightmost 48 bits come from the position after the move. That makes all moves
>>with the same parent position (the position before a book move is played) sort
>>together in the final book file, which is important for performance...
>
>The problem is that position may have more than one perant.
>
>1.e4 e6 2.d4 may be a son of 1.e4 e6 or 1.d4 e6
>
Sure. But for legit transpositions in a 2M game database, somebody must have
played that. If not, that won't be caught. The alternative it to find the bad
transposition after 1. e4 e5 2. Bb5 a6 3. Nf3 giving up the bishop.
>
>>
>>
>>>
>>>In the first case you need to probe in different places in the book for every
>>>move that you make that lead to different hash key.
>>>
>>>In the second case I do not see how you can do it when the same position may
>>>have more than one father(1.e4 e6 2.d4 may be both the son of 1.e4 e6 and 1.d4
>>>e6) and if you decide based on the smallest parent then sons of the same parent
>>>may have different smallest parent.
>>>
>>
>>
>>We have position X, a set of legal moves M. Making each move from the set M
>>produces a set of new hash signatures of the same size as the set of legal moves
>>(call these signatures H). For each element of H, take the rightmost 48 bits
>>and combine with the leftmost 16 bits of X. Now _all_ successor positions of X,
>>reachable by playing a book move in the set M, sorts together since they have
>>the same upper 16 bits (most significant bits)...
>
>Suppose X is the position after 1.e4 e6
>d4 is in M
>
>You have in your book
>48 bits of hash(1.e4 e6 2.d4)+16 bit of hash(1.e4 e6)
>
>Later you look at the position after 1.d4 e6 and get in your book for the same
>position 48 bits of hash(1.d4 e6 2.e4)+16 bits of hash(1.d4 e6)
>
>What do you choose?
>
>Uri
I do a search if nobody ever played 1. d4 e6 2. e4 in the large PGN collection I
used to build the book... If someone did play it, I'll play the indicated book
move. I can always resort to a search if I don't find a book move...
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.