Hashing based on move lists

[ZirconiumX]

Before I completely went cold turkey, Dmitri Gusev shared an idea of his with me,based around low-collision hashing via movelists. It's something for the Perft guys to use, most likely.

Bare in mind, before I share it, that it has been two months since I had this discussion, and I may have forgotten some elements of it.

It is based around bitboards, and the uniqueness of how chess pieces move.

Take, for instance, a pawn on d2. It can move to d3, d4, and possibly capture on e3 and c3. If we make a bitboard of this, we get:

Code: Select all

- - - - - - - -
- - - - - - - -
- - - - - - - - 
- - - - - - - -
- - - X - - - -
- - X X X - - -
- - - - - - - - 
- - - - - - - - 

Only a pawn on d2 could possibly get to these squares (I'll demonstrate why a trapped rook/queen wouldn't collide later).

Now, let's take a knight, and put it on d2, for the sake of example. It can move to b1, b3, c4, e4, f3 and f1. Once again, only a knight could get to those squares. Make a bitboard of it and you get:

Code: Select all

- - - - - - - - 
- - - - - - - - 
- - - - - - - - 
- - - - - - - - 
- - X - X - - -
- X - - - X - - 
- - - - - - - - 
- X - - - X - -

Note how different they are.

Now we get to the sliders, and for the sake of shortness, I will show how a queen fits in. Here is where some potentially useful information is lost. For sliders, we ignore all other pieces on the board for uniqueness. So, our queen goes to d1, e1, e2, f2, g2, h2, e3, f4, g5, h6, d3, d4, d5, d6, d7, d8, c3, b4, a5, c2, b2, a2, and c1. Only a queen could go to these squares. A bitboard:

Code: Select all

- - - X - - - - 
- - - X - - - - 
- - - X - - - X
X - - X - - X -
- X - X - X - -
- - X X X - - -
X X X - X X X X
- - X X X - - -

With all of that explained, the rest is simple, if somewhat expensive. You go through all of the white pieces, and compute their attacks (square attacks on an empty board anyone?(, and OR them into a single bitboard. You do the same for black, giving you a white_attacks bitboard, and black_attacks bitboard. IIRC Dmitri, assuming a1 is bit 0, suggested taking the top 32 bits of black_attacks, and ORing them with the bottom 32 bits of white_attacks, but I would recommend keeping the two bitboards seperate.

The main point of this is that it has a much lower collision rate than Zobrist keys, even 128-bit ones, but 128 bits is impractical for anything other than Perft, IMO.

Feel free to point out massive mistakes made.

Matthew:out

[mcostalba]

1) XOR not OR

2) Zobrist are defined as zob[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB], so when building up a position's key you not only xor together the zobrits keys of the squares occupied by piece, but also they depend on the piece type and color. In your idea instead of just the squares you compose together also a signature of the piece by means of it's more or less unique attacks, but this is already done also by standard ones.

3) Standard one is stronger because takes in consideration also color, instead in your case attacks signatures (except for the pawns) are color independent

[hgm]

It is not clear to me what exactly you propose. Is this intended to be a manner of constructing Zobrist keys? How do you get a different key for a white Queen on e4 and a black Queen on a4?

What exactly has a much lower collision rate? How has this been proven?

[nionita]

How do you get a different key for a white Queen on e4 and a black Queen on a4?

I'm not sure if this will be better then Zobrist classical method, but for this concrete question you could take the direct pattern for white and the complement of it for black.

Then you will have an array zob[NB_PIECE_TYPE][NB_SQUARE] where the color is not a dimension anymore, but codded in the direct/complement procedure. The array is only half and this could take pressure from caches.

But then this method could be used also for the classical Zobrist procedure, as I guess to take the complement is much cheaper than take another cache line from a bigger array.

[hgm]

That would be disastrous, because color-flipping any two pieces on the board would give you the same hash key for the position (if you XOR the Zobrist keys). With many dependent sets of just 4 keys, the number of collisions would become astronomical.

Tricks to save space in the Zobrist array that do work (and which I do use in my engines) are:

*) Make it an array of char Z[], and access them as *(long long int *)(Z+i), so that it forges 8 neighboring elements into a single key. Saves you a factor 8. (Used in Shokidoki, where the board has 81 squares (plus 6 for the holdings), and there are 14 piece types per color.)
*) Construct the key as pieceKey[coloredType]*squareKey[square]. (Used in HaChu, where the board for instance would be 144 squares, with 36 piece types per color, so that the memory requirement drops from 2 x 36 x 144 keys to 2 x 36 + 144 keys, a factor 48. Would save you even more when there are 1296 board squares and 300 piece types per side!)
*) Similarly, pieceKey[coloredType]+squareKey[square] would also work in an XORed key, while pieceKey[coloredType]^squareKey[square] would work in an additive key. (Tested by Daniel Shawul.)

[ZirconiumX]

This isn't my idea, this is Dmitri Gusev's idea.

I'll start with Marco.

1) I guess you could use XOR, but OR works fine too.

I don't understand 2).

3) You store white_attacks and black_attacks seperately. That distinguishes color.

H.G Muller

I can understand your confusion. For each piece, we work out it's color (no problem for bitboard engines) and work out its attacks on an otherwise empty board. We then OR/XOR with a color-specific bitboard that contains the attacks on an otherwise empty board for all other pieces OR/XORed together.

In your example, you'd have a white_attacks bitboard like this:

Code: Select all

X - - - X - - -
- X - - X - - X
- - X - X - X - 
- - - X X X - - 
X X X X - X X X
- - - X X X - -
- - X - X - X -
- X - - X - - X

And a black_attacks bitboard of:

Code: Select all

X - - - X - - -
X - - X - - - -
X - X - - - - -
X X - - - - - -
- X X X X X X X
X X - - - - - -
X - X - - - - -
X - - X - - - -

Find me a piece array that collides exactly with this. You'll be looking for a very long time.

Matthew:out

[ZirconiumX]

This is seperate from Zobrist keys. This is a chess-specific, very low collision (if not zero) hashing method. H.G, this won't be feasible in Shogi, or checkers.

This is basically a "do one thing and do it well" method.

Matthew:out

[hgm]

For each piece, we work out it's color (no problem for bitboard engines) and work out its attacks on an otherwise empty board. We then OR/XOR with a color-specific bitboard that contains the attacks on an otherwise empty board for all other pieces OR/XORed together.

Sorry, it is still a complete mystery to me. OR together to get what? What do you use this for?

Which other pieces? Standing where? If I OR all attack sets of all possible pieces on all possible squares, I get a bitboard of all ones, as every square is reachable by some piece. So why go through this tedious procedure and not simply write '-1'?

In your example, you'd have a white_attacks bitboard like this:

Code: Select all

X - - - X - - -
- X - - X - - X
- - X - X - X - 
- - - X X X - - 
X X X X - X X X
- - - X X X - -
- - X - X - X -
- X - - X - - X

And a black_attacks bitboard of:

Code: Select all

X - - - X - - -
X - - X - - - -
X - X - - - - -
X X - - - - - -
- X X X X X X X
X X - - - - - -
X - X - - - - -
X - - X - - - -

Sorry, my bad, I made a typo there. I meant: how is a white Queen on e4 different from a black Queen on e4 (not a4).

Find me a piece array that collides exactly with this. You'll be looking for a very long time.

What is a 'piece array'? What do you mean by 'collide with'? How can an array collide with a bitboard????

This is seperate from Zobrist keys. This is a chess-specific, very low collision (if not zero) hashing method. H.G, this won't be feasible in Shogi, or checkers.

Why not? What makes Shogi different from Chess? How is Checkers different from a Chess Pawn ending?

[ZirconiumX]

Hmmm... I'm not sure I can explain this simply.

Dmitri's method is basically a Zobrist key replacement, that instead of using random numbers, relies on the uniqueness of how chess pieces move.

It is most likely too expensive for a mailbox program as it was built from the ground up for a bitboard program.

Matthew:out

[mcostalba]

This isn't my idea, this is Dmitri Gusev's idea.

I'll start with Marco.

1) I guess you could use XOR, but OR works fine too.

No, It doesn't: http://chessprogramming.wikispaces.com/Zobrist+Hashing

I don't understand 2).

Your example below:

Code: Select all

X - - - X - - -
X - - X - - - -
X - X - - - - -
X X - - - - - -
- X X X X X X X
X X - - - - - -
X - X - - - - -
X - - X - - - -

Is just a 64 bit number that means a queen on a4.

Zobrist[QUEEN][SQ_A4] is exactly the same thing, but it is more powerful because numbers are pseudo-randoms and so very weakly correlated (instead of yours)

3) You store white_attacks and black_attacks separately. That distinguishes color.

This is a waste for no reason, in zobrist you use a different set of pseudo-randoms for each color: simpler and more elegant.