Is it necessary to include emty fields in the hash key of a position?
Frank Hablizel
is it necessay to include even empty fields in the hash key of a position
or not? I have read different suggestions for hashing in different books
or web sides.
This means in practice, using an array [64][12] or an array
[64][13] for the board using Zobrist hashing.
At the moment I implement the hash algorithm in my chess engine, but now
I'm not sure what is better. I'am using 64 bit numbers. Has anyone an idea?
Thanks in advance,
Frank
Ed Seid
pieces, excluding empty squares.
The location of empty squares isn't explicitly hashed, but it is still taken
into account when you, for example, XOR a knight on f3 to remove it. In
that example, you aren't hashing an empty square, but are hashing a piece in
order to make it disappear.
Note: I'm not a chess engine author (yet), but hope to be someday. Maybe
more experienced programmers have better knowledge than me.
"Frank Hablizel" <frank.h...@gmx.de> wrote in message
news:pan.2003.12.25....@gmx.de...
Frank Andreas de Groot
news:pan.2003.12.25....@gmx.de...
> is it necessay to include even empty fields in the hash key of a position
> or not?
No, it isn't.
Frank Hablizel
Ok, this means I also need only to xor additional values if castling is
possible (max. 4 values) and one value for each row if ep is possible and
one additional xor if black side is to move. Is this correct?
Frank Andreas de Groot
It sounds reasonable, but I am not a chess programmer.
You must think about your specific design.
As a Go programmer, and with a good understanding of Zobrist hashing,
I could answer your original question with absolute certainty, but your new
question is about implementation details that have no 100% defined yes/no
answer.
You may want to hash in much more stuff, or less, depending on your design.
The more you hash in, the higher potential for hash collisions.
Werner Mühlpfordt
If you code for the en-passant _target_ line, you need
one value at maximum.
Werner
David Richerby
> Ok, this means I also need only to xor additional values if castling is
> possible (max. 4 values) and one value for each row if ep is possible
> and one additional xor if black side is to move. Is this correct?
Yes because different castling flags and different en-passant target
squares mean that different moves are available. You should only hash in
the en passant square if an en-passant capture is legal, though.
Dave.
--
David Richerby Mouldy Soap (TM): it's like a personal
www.chiark.greenend.org.uk/~davidr/ hygiene product but it's starting to
grow mushrooms!
Werner Mühlpfordt
David Richerby <dav...@chiark.greenend.org.uk> writes:
> You should only hash in the en passant square if an
> en-passant capture is legal, though.
It's just as valid to hash in the en-passant row exactly
after a pawn double-move has appeared, no matter if there's
an opponent pawn to actually make the capture. This will
never make two unequal positions hash equal. FEN uses this
method as well.
And you don't really need the field - it's enough to have
the row. It's not even necessary to make a difference between
"ep can happen on e3" and "ep can happen on e6", because
the side-to-move code will always remove the ambiguity.
Saves some bytes which are likely to be in cache and thus
may be valuable.
Regards;
Werner
David Richerby
> David Richerby <dav...@chiark.greenend.org.uk> writes:
>> You should only hash in the en passant square if an
>> en-passant capture is legal, though.
>
> It's just as valid to hash in the en-passant row exactly
> after a pawn double-move has appeared, no matter if there's
> an opponent pawn to actually make the capture. This will
> never make two unequal positions hash equal. FEN uses this
> method as well.
Any hashing scheme will have two unequal positions hash equal because
the hash key will be smaller than the amount of data that is being
hashed. (If it were not, you'd just use the data itself rather than a
hash.)
You have to be careful about en-passant squares because including en-
passant squares that cannot be used means that two positions that are
the same will have different hashes. Since hashes are often used for
transposition tables, it's rather self-defeating to allow two positions
that result from transpositions of the same moves (e.g., the positions
after 1.d4 Nf6 2.c4 and 1.c4 2.Nf6 2.d4) result in different hashes!
Dave.
--
David Richerby Pickled Zen Boss (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ middle manager that puts you in touch
with the universe but it's preserved
in vinegar!
Werner Mühlpfordt
David Richerby <dav...@chiark.greenend.org.uk> writes:
> Werner Mühlpfordt <werner_mu...@knuut.de> wrote:
> Any hashing scheme will have two unequal positions hash equal because
> the hash key will be smaller than the amount of data that is being
> hashed. (If it were not, you'd just use the data itself rather than a
> hash.)
meet your above condition (key smaller than data), and the typical
64bit Zobrist keys do. What I was trying to say: the ep-mechanism
doesn't introduce any other type of collision that the usual ones.
> You have to be careful about en-passant squares because including en-
> passant squares that cannot be used means that two positions that are
> the same will have different hashes. Since hashes are often used for
> transposition tables, it's rather self-defeating to allow two positions
> that result from transpositions of the same moves (e.g., the positions
> after 1.d4 Nf6 2.c4 and 1.c4 2.Nf6 2.d4) result in different hashes!
I gladly pay a rare hash miss that could have been a hit, in favour
of speed of Zobrist key maintenance (and reduced codesize)
in move/unmove. YMMV, of course.
Werner