Author: Robert Hyatt
Date: 06:34:39 06/05/98
Go up one level in this thread
On June 05, 1998 at 04:32:10, Guido Schimmels wrote:
>
>On June 04, 1998 at 14:32:24, Robert Hyatt wrote:
>
>>If I interpret your prior post correctly, you have a problem. Because
>>in your hash table you don't store the piece that is moving. Which
>>means you could have a queen on e4 in the original position, and a
>>bishop
>>on e4 now, and you assume that the same diagonal-move is legal. And
>>that
>>is wrong... it would be legal... but it would be the wrong move in the
>>wrong position... that's why I store the full 21-bit move format in my
>>hash entries, 6bit from, 6bit to, 3bit moving piece, 3bit captured piece
>>and 3bit promote-to piece.
>>
>>
>>>ValidateWhiteMove()
>>>(
>>> to = from = square;
>>>switch(PieceOnSquare(square)) {
>>
>>there is the problem I see... you are using the piece on the real board,
>>which might not be the piece on the board in the hashed position. So
>>while you won't look at illegal moves, you might not be looking at the
>>right move, and using this to "validate" the hashing can overlook
>>collisions..
>>
>
>I already admitted in my previous post, storing the complete move format
>will detect a few more collisions, but I consider those additional
>12bits you
>store highly redundant compared to additional 12 bit of hash signature
>you could store instead (for example the lower 12 bits of the PawnKey
>for crafty as you already store 48 bits of the signature).
>Your validation will detect maybe 4 to 32 times as many collisions as
>mine,
>but you could detect 4096 times more collisions by help of those 12
>bits.
>("4 to 32 times" is my guess, I have no evidence for that, so correct
>me if you ran experiments that prove me wrong.)
>The only advantage with storing the complete move format is speed, but
>not for me, as my move format is 32-bit - the shifting I would have to
>do
>would be not faster compared to the switch statement, because
>it does both decompress and validate the move at the same time.
>
>I'd like to discuss with you an idea I'm having but not yet tried.
>What about storing the number of pieces on the board (TotalPieces in
>crafty
> I think) ? That would be only 5 bits but has the potential to detect
>lots of
> collisions.
>I had the idea when I read a text from Donninger about hashing,
>where he says, the probabilty to positions share the same signature
>grows
>with the number of differently placed pieces between them.
>So most likely will a position near the root collide with a position
>near the tips,
>whereas two positions near the root will hardly collide. My idea now
>was, most
>relevant long lines include captures, so the number of pieces on the
>board
>will change.
> Does this make sense, what do you think ?
>
>- Guido
I don't agree with him on collisions. In general, the collision rate
increases with the depth of the search tree, something that has been
known for many years, since lots of folks tested the "Zobrist hashing"
scheme in chess programs. A single move greatly perturbs the hash
signature. and the liklihood of a collision after one ply is close
enough to zero to be zero, particularly if you check your random numbers
to be sure that they average a hamming distance of 32, with *none* that
drop below 16, which I have done. But the deeper you go, the greater
the
probability that you get duplicate keys, and it has nothing to do with
the
pieces that are captured... just the additive probability that going
from
one move to the next will undo something already done to the hash
signature.
It's worthy of ignoring, however. :)
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.