ep and castle rights hashing

[xmas79]

FIDE rules say exactly nothing about what you should put into your hash signature. Look at the rules, they are silent on hash signatures.

Of course they don't, they are not meant for computer chess...

However, if you use hash signatures to detect 3-fold repetition, then you'd better including castling rights in the hash signature.

And if you do that, then removing castling rights when a king is in check is wrong, as has already been explained in detail. You probably have to be more careful when reading the above comments and the FIDE rules.

I do use castling rights in the hash key as already said, I'm questioning if I should remove them temporarily. And I read all the FIDE rules and all the comments here and everyone can only "interpret" article 9.2, no one is able to tell "the rule is..." because is poor written (IMO).

In particular, the FIDE rule you cite mentions "possible moves of all the pieces of both players" which implies that you should not only look at the legal moves of the side to move (the other side not having any legal moves, as it is not its turn to move), but at all legal continuations.

I dont see this in the rule, I only see "all the possible moves of both players", that means if it's white to move in position A and a black castle move could be possible if it was black to move instead of white, and in the position B where is white to move but a black castle could not be possible if it was BTM then the two positions are different, as black has a castle move in position A that have not in B, which is of course very different than looking at all possible continuations. Please note that article 6.9 says:

...However, the game is drawn, if the position is such that the opponent cannot checkmate the player’s king by any possible series of legal moves...

So "they" actually know the difference between "all possible legal continuations" and "all possible moves". Maybe this is a mistake and these are the magic words missing in the 9.2 rule?

The next paragraph then makes one clarification/exception: castling rights are only lost after the king or rook is moved. The only possible reason for mentioning this, is that it qualifies the preceding paragraph.

edit: I agree 100% with Sven on this.

And then again I only see "The only possible reason for mentioning this, is that it qualifies the preceding paragraph.": an interpretation of the rule, not what the rule actually says.

Best regards,
Natale.

[syzygy]

Why not this?
[d]8/8/8/8/8/7k/4q2P/6KR w K -

You win

[rtitle]

I think it's a mistake to be using the transposition table to detect repetitions in the first place.

A simple algorithm for detecting repetition not using the TT:

1 In your stored move history, store with each move the appropriate hash of the position in which the move was made. (By "appropriate hash" I mean taking into account whatever the FIDE rules say about repetition. Before reading this thread, I thought that meant just the position of the pieces on the board and the color-to-move. At this point I'm not sure. )
2. To detect a repetition, walk backwards through that move history until you reach an irreversible move. As you walk backward, compare the hash of the current position with the stored hash in your move history. If it matches, you have a repetition, so assign a score of 0 to the position.

Why you don't want to use the TT for that: Because it forces you to keep in your TT all positions that might be needed for repetition detection. This in turn forces you to make replacements you don't really want to make. E.g., let's say you have a high-quality TT entry (based on a deep search) at a certain slot in the TT table. Now say you get a hash collision on that slot searching near the leaves of your tree, e.g. in your extension search. If you're using your TT to detect repetitions, you are forced to replace, i.e. toss out that high-quality entry and replace it with the lower-quality TT entry, in order to detect repetitions below your current search point. In fact at the point you do that replacement you're going to have an entry in the TT with no information except "I'm on the stack of positions being searched". Oh, and another thing you need to be careful of if you detect repetitions this way: If your engine is multithreaded and the TT is shared amongst threads, you better store thread info in the TT entry, or else you might detect incorrect repetitions due to one thread seeing a TT entry as "being searched" when it was actually a different thread that put it there.

OK, I hope the above made sense and I've convinced you.

[xmas79]

I think it's a mistake to be using the transposition table to detect repetitions in the first place.

Hi,
who said that we use TT for detecting repetitions?

...In your stored move history, store with each move the appropriate hash of the position in which the move was made. (By "appropriate hash" ...

This thread is all about that "appropriate hash"... Can you say something about what FIDE says (apart the "I'm not sure....")?


Best Regards,
Natale.

[syzygy]

I think it's a mistake to be using the transposition table to detect repetitions in the first place.

Most don't, but almost everybody uses the hashkey for detecting that two positions are the same.

Still, it is simply wrong and arrogant to call it a mistake. Many excellent programmers have used the TT for repetition detection.

1 In your stored move history, store with each move the appropriate hash of the position in which the move was made. (By "appropriate hash" I mean taking into account whatever the FIDE rules say about repetition. Before reading this thread, I thought that meant just the position of the pieces on the board and the color-to-move. At this point I'm not sure. )
2. To detect a repetition, walk backwards through that move history until you reach an irreversible move. As you walk backward, compare the hash of the current position with the stored hash in your move history. If it matches, you have a repetition, so assign a score of 0 to the position.

This is what most engines do. Some improvements are possible.

[rtitle]

re: "who said the TT is used to detect repetitions?" I guess I was inferring it (perhaps incorrectly) from Ronald's reply (3rd reply in this thread) when he said: "Another reason for not assigning these two positions the same hash key is that the hash key is probably used to detect repetitions".

So if you're *not* using the TT to detect repetitions, then there's no reason you have to use the same hash for detecting repetitions as you use for indexing into the TT. This thread seems be mixing the 2 questions (i.e. "what hash should I use for my TT hash index" and "what hash should I use to detect repetitions"), in various replies. I was just trying to point out these 2 questions are separable, and clarify which of the 2 you guys are talking about.

A question I have related to this is: Everyone seems to assume ZOB hash for chess positions. But there are many good hash functions out there. Has anyone done a study comparing the performance of various hash functions on chess positions in a search tree, in terms of how well the hash distributes the positions across very large hash tables (e.g. billions of entries)? I.e. is it possible that some of the good cryptographic hashes would do a better job of filling up a large TT with fewer collisions than ZOB hash...?

Rich

[rtitle]

re: "it is simply wrong and arrogant to call [using the TT to detect repetitions] a mistake. Many excellent programmers have [done that]"

Ouch. Let me re-phrase. I *myself* went down the path of using my TT to detect repetitions. Then I decided it was a mistake for the reasons I gave in that earlier post, and I changed over to the simple walk-backward-in-the-move-history approach. The engine is much better for the change because now I'm not thrashing my TT with entries that are just there to detect repetitions. I'm just relaying my own experience.

Rich Title

[syzygy]

re: "who said the TT is used to detect repetitions?" I guess I was inferring it (perhaps incorrectly) from Ronald's reply (3rd reply in this thread) when he said: "Another reason for not assigning these two positions the same hash key is that the hash key is probably used to detect repetitions".

There is only way to understand that sentence: repetitions are detected by comparing hashes. Exactly as in the remarkable algorithm you described.

So if you're *not* using the TT to detect repetitions, then there's no reason you have to use the same hash for detecting repetitions as you use for indexing into the TT. This thread seems be mixing the 2 questions (i.e. "what hash should I use for my TT hash index" and "what hash should I use to detect repetitions"), in various replies. I was just trying to point out these 2 questions are separable, and clarify which of the 2 you guys are talking about.

I think you were the only one that was confused here.

A question I have related to this is: Everyone seems to assume ZOB hash for chess positions.

Because it is brilliant and has all the right properties for the job.

But there are many good hash functions out there. Has anyone done a study comparing the performance of various hash functions on chess positions in a search tree, in terms of how well the hash distributes the positions across very large hash tables (e.g. billions of entries)?

Nothing to gain here, but good luck searching for a solution to a problem that does not exist.

Studies have been done on the number of bits needed and on how to pick good Zobrist keys. The general concensus is that using any reasonable random generator is sufficient to get to what is for all practical purposes a uniform random distribution. You can then calculate the number of collisions as a function of hash table size, bucket size and number of bits used using simple math.

I.e. is it possible that some of the good cryptographic hashes would do a better job of filling up a large TT with fewer collisions than ZOB hash...?

Cryptographic hashes are the worst tool for this particular job.

[rtitle]

I composed the following position to show why you must consider castling rights when you look up an evaluation/best-move in your TT table. With castling rights, this is a win for White with 1.Bd3! (there is no defense to 2.O-O mate). Without castling rights, this is losing for White. (Hope this diagram comes through in the real post; it doesn't display in "Preview" but I think I got the EPD notation right...):

[d]8/8/p7/8/8/4Bp2/pppP1P2/rk2KB1R w K--- -

WRT to the separate subject of repetition detection, the FIDE rules say the following:

9.2 The game is drawn upon a correct claim by the player having the move, when the same position, for at least the third time (not necessarily by a repetition of moves):
a. is about to appear, if he first writes his move on his scoresheet and declares to the arbiter his intention to make this move, or
b. has just appeared, and the player claiming the draw has the move.
Positions as in (a) and (b) are considered the same, if the same player has the move, pieces of the same kind and color occupy the same squares, and the possible moves of all the pieces of both players are the same.
Positions are not the same if a pawn that could have been captured en passant can no longer be captured in this manner. When a king or a rook is forced to move, it will lose its castling rights, if any, only after it is moved.

The above is clear enough except for the last sentence which is weird.

Consider the following position as an example:

[d]4k3/8/8/8/8/8/8/4KB1R w K--- -

After the sequence 1.Ke2 Ke7 2.Ke1 Ke8 3.Ke2 Ke7 4. Ke1 Ke8 5.Ke2 Ke7 6.Ke1, black could write his intention to play Ke8 and claim a draw by triple repetition. The conditions of the above FIDE rules are met. The fact that white had castling rights in the initial position and does not in the final position, does not invalidate the draw claim, right?

Thus I claim that, unlike the hash done for TT lookup, castling rights should not be factored into the hash done for repetition detection.

Rich

[syzygy]

Thus I claim that, unlike the hash done for TT lookup, castling rights should not be factored into the hash done for repetition detection.

Castling rights should be included in a hash key used for repetition detection, because two positions with the same pieces of the same colors on the same squares with the same side to move are not the same for the purpose of 3-fold repetition if they differ in castling rights.

This follows from the inclusion of "and the possible moves of all the pieces of both players are the same", which refers to all present moves and future moves. Indeed, it refers to the moves of both players and only 1 player can presently make moves. (In your example remove Bf1 and switch side to move to black. Obviously the position with castling right for white should be different than the position without for the purpose of 3-fold rep even though it does not matter for black's present legal moves).

It is further confirmed by the statement "When a king or rook is forced to move, it will lose its castling rights, if any, only after it is moved". The inclusion of this statement in the definition of draw by repetition would not make sense if castling rights were not to be taken into account (apart from the direct possibility of playing a castling move).

Also there is no doubt that it is generally recognised in the world of chess that castling rights are to be taken into account for the purpose of draw by rep, even if no castling move is immediately available. Finding an interpretation of the FIDE rules completely contrary to the accepted understanding of the game of chess can be fun, but does not change the "law".

So this is why essentially all somewhat mature chess engines include castling rights into the hash key and use the same hash key for indexing the TT and detecting draws.

There is one case where it would make sense to distinguish between hash key for the TT and a hash key for detecting repetitions: if the current position has castling rights for the side to move, but that side is bound to lose those castling rights on the next move without actually castling for lack of other legal moves. In this case the position is not the same as the identical position without castling rights for the purpose of draw by rep (see the rule and its proper interpretation), but since all possible continuations are the same it would be safe to hash them to the same entry. But this case is so rare that accomodating for it would probably not give any measurable benefit.