Can chess engines recognize equivalence between two positions?

Question

The positions

[FEN "8/4kn2/4br2/8/8/3Q4/4K3/8 w - - 0 1"]

with white to move

[FEN "8/8/8/2Q5/1K3bk1/5rn1/8/8 w - - 0 1"]

with white to move

[FEN "8/2nk4/2rb4/8/8/4Q3/3K4/8 w - - 0 1"]

with white to move

and

[FEN "8/4KN2/4BR2/8/8/3q4/4k3/8 b - - 0 1"]

with black to move

are all equivalent to each other in the sense that each position can be transformed into one of the other 3 positions through a combination of rotation, reflection, and reversing the color of every piece.

This means that if we went through a search tree for one position there would be no need to go through the search tree for the other 3 as the result of the first 3 positions with best play must be the same, while the result of the last position would be reversed from the first 3. This means that for a search tree, in which each of these for positions are reached in some of the branches, it would only be necessary to search the sub tree of one of the positions, and apply the same evaluation for the first 3 positions while reversing the evaluation of the 4th from the first 3.

My question is would an engine that has say evaluated 1 of the 4 positions given within a search tree recognize the other 3 as being equivalent to it and simply apply the same or opposite evaluation to the other positions, or would it fail to recognize the equivalence between the 4 positions and independently go through the sub trees of all of them?

Answer 1

No. In general, a chess engine would not be able to recognise your four positions as equivalent and would search each of them independently.

Transposition tables

Chess engines do have a mechanism for remembering past positions and applying them to future searches - the transposition table. This is a large region of memory that associates an identifier for each position with some useful information about that position (usually including the search depth, evaluation, best move, and if the node failed low or high).

For a chess engine to recognise mirrored positions as equivalent, they would either need to have the same identifier, or the chess engine would have to calculate corresponding identifiers for mirrored positions and probe the transposition table for these other identifiers as well. In the most popular method of generating a position identifier, the former does not hold.

Zobrist hashing

Most chess engines generate position identifiers with a system called Zobrist hashing. In this system, every possible combination of a piece and a square is assigned a large randomly generated number¹. For example, a white king on e2 might be assigned the number 7626908458552064978 and a black rook on c5 might be assigned the number 3638090793699092332. The Zobrist hash is obtained by taking the numbers assigned to all the (piece, square) combinations in the position and combining them with the binary xor operator.

It should be clear that, in each of your different positions, the pieces will have completely different individual random numbers (as they are on different squares) and hence the position will have a completely different Zobrist hash: Zobrist hashes are not symmetric in this way. So, if one of your four positions was saved in the transposition table, the engine would not find its entry by probing one of the other positions.

Zobrist hashes are used because they can be incrementally updated and are therefore efficient to compute: the xor operator can be reversed by simply applying it again, so the hash of a position after a move can be computed by taking the hash of the position before the move and applying xor with the 'from' and 'to' squares of the move for the piece that moved².

Zobrist hashes are asymmetric because the game of chess is asymmetric: chess is asymmetric vertically as long as there are pawns on the board, and asymmetric horizontally as long as either side has castling rights. It would be theoretically possible for a chess engine to switch to a symmetric Zobrist hashing scheme when either or both of these conditions no holds, but this would break the incremental property of Zobrist hashes, adding a substantial amount of complexity and reducing speed for potentially little gain.

Motivations

The main reason why chess engines have not explored ideas like transitions between asymmetric and symmetric hashing schemes or probing multiple times with mirrored positions is that the ability to recognise these equivalences seems unlikely to be useful.

The transposition table is a performance critical part of a chess engine. In most implementations, hashes are updated and the TT is probed in every single position examined by the engine. As a result, ideas that slow this process down need to be able to at least compensate for the resulting strength reduction in addition to showing some other benefit.

Ultimately, it seems that recognising mirrored positions is likely to have a negligible impact on engine strength. A tiny proportion of lines will lead to an exact mirrored position, and the transposition table hit that might result from this is likely to have a very small impact in the overall search³. In fact, the reduction in engine strength from a slower TT would probably outweigh any gains⁴.

^{I will also note that, in your specific example, an engine with access to 6-piece endgame tablebases would be able to recognise those positions as equivalent. Chess is solved for 7 or fewer pieces, and these positions can therefore be evaluated perfectly without any search.}

---

^{1 Random numbers are also assigned for other features of the position, such as "white has the right to castle kingside" and "the pawn on b5 may be taken en-passant".
2 Some more complicated logic is required for captures, promotions, castling and en-passant, but this logic is still incremental and efficient.
3 Especially as, given that we know this position is equivalent, the line that leads there is both drawish and almost certainly does not form part of the principal variation.
4 It could be argued that detecting mirrored positions would aid analysis, though it is unclear what kind of analysis would be aided more by mirror detection than a stronger engine.}

Answer 2

Absolutely not. The positions look identical to you, but are represented very differently internally by an engine. There is no good reason to do it. Furthermore, everything in a chess engine about search tree optimization is about connecting move sequences, your three positions couldn't be connected to each other by normal plays.

Answer 3

An answer depends very much on your definition of 'chess engine'.

A playing chess engine can (or could) identify them as identical, as already described by konsolas, but they rarely have a sufficient reason to do so. (Or probably don't: different ECO openings leading to the same position through different paths may provide a situation in which it would be useful, but that is also a situation which can be solved by a suitably designed opening book, and so any opening book creation engine -- if there are any -- may very well include it in creating books where a white position is reused for black mutatis mutandis.)

Some analysis engines do recognize related situations, for example chess problem engines (for composed problems, not practical problems). In those cases, however, the purpose is not to minimize evaluation time or effort, but to identify problems in which the same 'mate' occurs in different locations in the mating positions-- a situation called a 'mate echo', and sometimes regarded as a desirable artistic feature to have or focus on in a composed problem.

(It just strikes me that in the literary thriller world such situations sometimes can be identified when the villain -- perhaps Mr Black -- says 'you and I are not so different after all, Mr. White.' ... or words to similar effect. )