History pruning / move ordering question

[Don]

Hi,

how do you calculate the hash signature of two moves ?

key = boardkey XOR boardkey_two_moves ago ?

Thomas...

If you are simply talking about a refutation table, you just use a table. For example 2x6x64 where the contents store the refutation move.

If you want to go beyond 2 moves, you probably want to use a hash because even the 2x6x64 tables is sparse. You can do this the same way zobrist keys are generated for board positions but make sure that the first move has a different identify (or zobrist key) than the second move so that transposed moves don't hash to the same key.

You can utilize the existing zobrist key table with just a little bit of creativity.

[Don]

Hi,

how do you calculate the hash signature of two moves ?

key = boardkey XOR boardkey_two_moves ago ?

Thomas...

Yes, that's the beauty.

Two problems with that. One is that it's not move dependent which is probably what you want. The other problem is that you are hashing specific state changes, not moves. Refutation and history and killers are highly dependent on generalization. The idea is that some move "usually" works well (in all related positions) in response to some other move or in the case of killers even in general.

On another subject, Marcel Van Kervick posted a very interesting paper on Open Chess that uses this property (for a different purpose though)
http://open-chess.org/viewtopic.php?f=5&t=2300

[tpetzke]

Two problems with that. One is that it's not move dependent which is probably what you want.

Hmm. I thought

Code: Select all

Current_Key = Key_two_moves_ago XOR my_last_move XOR his_last_move

So Current_Key XOR Key_two_moves_ago should form a hash signature that stands for the combination of his and my move. So the location of all other (non-moved) pieces is filtered out.

I agree it is more specific than a [piece][moveto] ^ [piece][moveto] scheme because also the starting square of the moved pieces becomes part of the hash. A rook move A1 to D1 would generate a different hash than rook H1 to D1. But I don't think it hurts.

Whether the idea to collect my move - his move refutations works in my engine is of course a different story.

Thomas...

[Don]

Two problems with that. One is that it's not move dependent which is probably what you want.

Hmm. I thought

Code: Select all

Current_Key = Key_two_moves_ago XOR my_last_move XOR his_last_move

So Current_Key XOR Key_two_moves_ago should form a hash signature that stands for the combination of his and my move. So the location of all other (non-moved) pieces is filtered out.

But it's the same as

current_key = his_last_move XOR my_last_move XOR Key_two_moves_ago

In other words, any order the moves are played hash to the same key. There is nothing wrong with that if it's specifically what you want.

Are this MOVES you are hashing or positions? I assume they are moves with some hash function, for example: key = hash( "Pe2e4" )

I agree it is more specific than a [piece][moveto] ^ [piece][moveto] scheme because also the starting square of the moved pieces becomes part of the hash. A rook move A1 to D1 would generate a different hash than rook H1 to D1. But I don't think it hurts.

Whether the idea to collect my move - his move refutations works in my engine is of course a different story.

Thomas...

[tpetzke]

I don't have hash signatures for moves (and I thought I don't have to start building them). So I would xor two positions, the current and a former one.

In principle you are right that an exchanged move order results in the same (difference) signature. But I can store two refutation moves (a white and a black one) and pick the one for the side to move.

Thomas...

[Don]

I don't have hash signatures for moves (and I thought I don't have to start building them). So I would xor two positions, the current and a former one.

This almost the same as just using the key of the current position and a refutation would not be applicable to any other positions. You probably already have that in your program, it's called the hash table move.

In principle you are right that an exchanged move order results in the same (difference) signature. But I can store two refutation moves (a white and a black one) and pick the one for the side to move.

Thomas...

Thomas, there are some excellent and very fast hash functions for small strings or data structures. They don't have to be perfect for this usage.

But for the simple refutation table you only index a single move, the refutation itself is stored in the table and no hashing required.

If you want to hash move sequences, it's pretty simple too. Let's say you have a 2 move sequence. Just use the zobrist key of the first piece "from" square, add a constant to that, xor it with the "to" square from the zobrist table, add a constant to that, xor it with the next moves "from" square, add a constant and so on. The constant provides move order dependence. Even if there is only a single constant it will work just fine - just make it a nice big value to guarantee lots of bit overflow. I think multiplication and subtraction would work well also. The xor makes sure the numbers are well mixed, the other operation provides a bit of move order dependence. It may not be perfect without a serious analysis of which constants to use but that is not going to be a big issue here as long as you use a big random number as your constant.

[dchoman]

I don't have hash signatures for moves (and I thought I don't have to start building them). So I would xor two positions, the current and a former one.

In principle you are right that an exchanged move order results in the same (difference) signature. But I can store two refutation moves (a white and a black one) and pick the one for the side to move.

Thomas...

You can also add an xor of the hash signature for the side-to-move at the end of the combination.

- Dan

[Don]

I don't have hash signatures for moves (and I thought I don't have to start building them). So I would xor two positions, the current and a former one.

In principle you are right that an exchanged move order results in the same (difference) signature. But I can store two refutation moves (a white and a black one) and pick the one for the side to move.

Thomas...

You can also add an xor of the hash signature for the side-to-move at the end of the combination.

- Dan

If he is hashing 2 move sequences or more it is hardly a problem but you are right, it could be done this way.

To have a proper zobrist hash you need a separate random key table for each "element" of the thing you are hashing. In the simple case with just "from" and "to" hashing that would be 4 tables for a 2 move sequence.

A full move however really only needs 64 random numbers - you can construct offsets that do not represent legal moves. For example NO piece can move from a1 to g2 so you might be able to find a magic constant offset that would work with any valid move to avoid the from/to independence as long as one never mapped to the other. Presumably you would mask off the lower 6 bits to make sure your offset stayed on the board.

So you would want an offset that made ANY legal move by any piece come out as unique. Let's say the offset was 13 for example. Your key for a single move might be:

key = zobrist[f] ^ zobrist[ (t + 13) & 63 ];

where f is the from square and t is the to square.

to hash a 2 move sequence you need to multiply a well selected constant to the first move before xoring the second move:

seq2 = (key1 * K) ^ key2;

K could probably be any large random number but there are some hashing functions with multipliers such as Murmur Hash and you could steal constants known to work well for those - although I don't think it really would matter that much.

[tpetzke]

Thanks for the explanation, I put some work around that on my long todo list.

Thomas...

[Don]

Thanks for the explanation, I put some work around that on my long todo list.

Thomas...

I was just rambling here - but if you do trying it please note that I did not check my offset of 13 - it was just an example. I cannot even guarantee that there IS a number that would map all legal move to something unique.

Something much simpler for from/to square mapping is a 64x64 array of keys to avoid all this complexity. You can just use your regular zobrist table for that.

Don