Answers.Body: <p>No. In general, a chess engine would not be able to recognise your four positions as equivalent and would search each of them independently.</p>
  <h3>Transposition tables</h3>
  <p>Chess engines do have a mechanism for remembering past positions and applying them to future searches - the <a href="https://www.chessprogramming.org/Transposition_Table" rel="nofollow noreferrer">transposition table</a>. 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).</p>
  <p>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.</p>
  <h3>Zobrist hashing</h3>
  <p>Most chess engines generate position identifiers with a system called <a href="https://en.wikipedia.org/wiki/Zobrist_hashing" rel="nofollow noreferrer">Zobrist hashing</a>. In this system, every possible combination of a piece and a square is assigned a large randomly generated number<sup>1</sup>. For example, a white king on e2 might be assigned the number <code>7626908458552064978</code> and a black rook on c5 might be assigned the number <code>3638090793699092332</code>. 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.</p>
  <p>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.</p>
  <p>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<sup>2</sup>.</p>
  <p>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.</p>
  <h3>Motivations</h3>
  <p>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.</p>
  <p>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.</p>
  <p>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<sup>3</sup>. In fact, the reduction in engine strength from a slower TT would probably outweigh any gains<sup>4</sup>.</p>
  <p><sup>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.</sup></p>
  <hr>
  <sup><sup>1</sup> 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".</sup>
  <br>
  <sup><sup>2</sup> Some more complicated logic is required for captures, promotions, castling and en-passant, but this logic is still incremental and efficient. </sup>
  <br>
  <sup><sup>3</sup> 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.</sup>
  <br>
  <sup><sup>4</sup> 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. </sup>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-04T09:21:29.493Z
Answers.Text: What about Tablebases ? It seems that it must be much more efficient, once you have solved a position, to immediately save its equivalent positions than to eventually calculate them independantly...
Answers.UserDisplayName: Evargalo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-04T13:18:01.630Z
Answers.Text: Tablebases do take advantage of this. The Syzgy tablebases store mirrored (colour swapped) positions only once and utilise horizontal and (when there are no pawns) vertical symmetries to improve compression.
Answers.UserDisplayName: konsolas
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-04T01:43:22.133Z
Answers.LastActivityDate: 2023-01-04T01:43:22.133Z
Answers.UserDisplayName: konsolas
Answers.Body: <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-04T21:46:12.410Z
Answers.LastActivityDate: 2023-01-04T21:46:12.410Z
Answers.UserDisplayName: SmallChess
Body: <p>The positions</p>
  <pre><code>[FEN &quot;8/4kn2/4br2/8/8/3Q4/4K3/8 w - - 0 1&quot;]
  </code></pre>
  <p>with white to move</p>
  <pre><code>[FEN &quot;8/8/8/2Q5/1K3bk1/5rn1/8/8 w - - 0 1&quot;]
  </code></pre>
  <p>with white to move</p>
  <pre><code>[FEN &quot;8/2nk4/2rb4/8/8/4Q3/3K4/8 w - - 0 1&quot;]
  </code></pre>
  <p>with white to move</p>
  <p>and</p>
  <pre><code>[FEN &quot;8/4KN2/4BR2/8/8/3q4/4k3/8 b - - 0 1&quot;]
  </code></pre>
  <p>with black to move</p>
  <p>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.</p>
  <p>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.</p>
  <p>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?</p>
  
Tags: <engines><programming><evaluation>
Title: Can chess engines recognize equivalence between two positions?
ThreadText: # Can chess engines recognize equivalence between two positions?
  
  (Asked by: username_0 on 2022-10-13)
  
  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?
  
  **Tags:** engines, programming, evaluation
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2023-01-04. Score: 2
  
  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](https://www.chessprogramming.org/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](https://en.wikipedia.org/wiki/Zobrist_hashing). In this system, every possible combination of a piece and a square is assigned a large randomly generated number1. 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 moved2.
  
  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 search3. In fact, the reduction in engine strength from a slower TT would probably outweigh any gains4.
  
  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.
  
  > **Comments:**
  > **username_2**: What about Tablebases ? It seems that it must be much more efficient, once you have solved a position, to immediately save its equivalent positions than to eventually calculate them independantly...  
  > **username_1**: Tablebases do take advantage of this. The Syzgy tablebases store mirrored (colour swapped) positions only once and utilise horizontal and (when there are no pawns) vertical symmetries to improve compression.  
  
  ---
  
  ### Answer by username_3 on 2023-01-04. Score: 1
  
  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.
  
  
  ---
  
  