Identical positions in tree

[evert823]

Suppose we were checking this position:
[d]8/4K3/3NB3/8/8/3k4/8/8 w - - 0 1
One continuation:
1. Nc4 Kd4 2. Kf6 Kc3
Another continuation:
1. Kf6 Kd4 2. Nc4 Kc3
These two continuations result into identical positions.
Two questions:
1. Do we consider these identical positions to be two separate nodes in the tree?
2. Is it common practice to optimize search, by remembering positions, and detecting that a later position is identical to an earlier one?

W.r.t. point 2, I can imagine that it would be complex to program it this way, and the overhead of remembering positions and comparing them, could slow down the search.

[Robert Pope]

Your search will arrive at each position individually as part of the search, but all good chess programs keep a large number of past positions in a transposition table and save the score reached. Then when it finds it a second (or hundredth) time, it can look up the value instead of having to continue searching it's descendants.

That saves a huge amount of time, especially in endgame positions like this. There isn't enough memory to store every position, so the program has rules about when to overwrite an old position to save a new one.

[evert823]

Your search will arrive at each position individually as part of the search, but all good chess programs keep a large number of past positions in a transposition table and save the score reached. Then when it finds it a second (or hundredth) time, it can look up the value instead of having to continue searching it's descendants.

That saves a huge amount of time, especially in endgame positions like this. There isn't enough memory to store every position, so the program has rules about when to overwrite an old position to save a new one.

Thanks for responding.
How does transposition table interact with alpha-beta?
For example, you're getting a position that you have in your transposition table, but the old value was calculated based on a certain state of alpha and beta.
If your alpha and beta are sharper when you see that position for the 2nd time, does it mean that you should go through it again?

[hgm]

Scores obtained by alpha-beta search can be exact (if they are between alpha and beta), upper bounds (below or equal to alpha) or lower bounds (above or equal to beta). The entry for the position in the transposition table stores this information (the 'flags') together with the score, and the depth of the search that produced the score. If the search later encounters that same position, alpha, beta and the requested depth can be different. You would only accept the score when it is compatible with these new parameters. That is, the stored depth should be equal or higher than what is requested now, if the stored score is below the new alpha it should not be a lower bound, if it is above the new beta it should not be an upper bound, and if it is between the new alpha and beta it should be an exact score. If it doesn't satisfy these requirements, the stored score is useless, and you would have to search the position anyway. Which eventually will lead to improvement of the bounds and/or the depth, which you will then store in the TT.

One usually also stores the best move that the search found. (If one was determined; if all moves in a position score below alpha you would have no idea which move is best.) This information can be used even if it was obtained at lower depth, for the purpose of move sorting. Usually this 'hash move' is the first move to search.

Positions are considered equal when the board position is the same, castling and e.p. rights are the same, and the same side is on move. (I.e. when the FIDE rules for 3-fold repetition would consider them equal.) Strictly speaking this doesn't mean they are the same game state, as the 50-move counter and the entire move history since the last irreversible move are part of that too, in order to determine when draws can be claimed. But paying attention to those aspects of the game state would completely subvert the huge beneficial effect a transposition table has, and is thus very counter-productive.

[smatovic]

Next question might be about the "Graph History Interaction Problem"....

https://www.chessprogramming.org/Graph_ ... nteraction

--
Srdja

[evert823]

Thanks, this is very clear and helpful, except that I have a hard time reading this part:

if the stored score is below the new alpha it should not be a lower bound, if it is above the new beta it should not be an upper bound, and if it is between the new alpha and beta it should be an exact score.

Does this mean that the stored score is only accepted, if:
stored alpha < alpha < stored score < beta < stored beta

[hgm]

No, alpha and beta are not stored. Only the fact whether their values at the time the stored result was obtained were smaller cq larger than it. This can be done in only 2 bits. Suppose we call these stored 'flags' alphaLower and BetaHigher, we accept a stored score S when

(alphaLower && S > alpha) || (betaHigher && S < beta)

In other words: there does not have to be a specific relation between the original and the new alpha or beta. They just must ly on the same side of the stored score as they originally did. The given expression makes use of the fact that always alpha < beta.

[evert823]

[d]8/4B2k/8/4N1K1/8/8/8/8 w
I just roughly implemented this transposition table and was testing this mate in 6.
What is a realistic expectation of how many positions it would re-use from the transposition table?
(My log says: nodecount 137332756, Reused from transposition table 10)

[shawn]

I just roughly implemented this transposition table and was testing this mate in 6.
What is a realistic expectation of how many positions it would re-use from the transposition table?
(My log says: nodecount 137332756, Reused from transposition table 10)

10 hits on the transposition table (if that is what you meant by that) sounds quite low, but it does depend on the search tree and TT size. SPRT https://www.chessprogramming.org/Sequen ... Ratio_Test is probably your best bet to check for correctness, as a correct implementation can gain tens and even hundreds of Elo.

[hgm]

10 hits on the transposition table (if that is what you meant by that) sounds quite low, but it does depend on the search tree and TT size. SPRT https://www.chessprogramming.org/Sequen ... Ratio_Test is probably your best bet to check for correctness, as a correct implementation can gain tens and even hundreds of Elo.

Testing whether there are bugs in your TT implementation by playing games is about the worst you can do. Better just debug through print statements to make sure it does what you wanted it to do.

With hash setting 256MB (I think it actually uses only 3/4 of that, because the entry size is 12 bytes) Fairy-Max takes 2.39M nodes to report the mate in 6. When I lower the allowed hash size to 1MB (the lowest it accepts) it takes 8.10M nodes. That doesn't really tell you how much hash hits there are (in theory a single hash hit could have cut off a sub-tree that contained 6M nodes), but it indicates a sufficiently large hash table should affect the search tree enormously.