Answers.Body: <p>Most programmers only record the move (and some other key flags) played and only the position it's thinking about.</p>
  <p>A move structure often contains the move, castling rights, move ply, 50 move ply, EP square, and, and a hash value.  (Depending on how involved you want the AI, you may add other data, such as what the computer evaluates this position to help with the AB search.)  By restoring the flags and using simple logic to retract the move, a previous position can be restored.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-04T21:45:58.743Z
Answers.LastActivityDate: 2021-04-04T21:45:58.743Z
Answers.UserDisplayName: Mike Jones
Answers.Body: <p>There is only little memory required for the purpose of checking the rules for remis: Either party can request a draw when a position repeats three times or there is no pawn move or capture within 50 (or is it 70?) moves. In your GUI, you may want to <em>automatically</em> end the game in a remis in such a condition (even though formally this has to be requested by a player).</p>
  <p>Then note that you never need to keep track of more than 50 positions because whenever a pawn moves or a piece gets captured, no previous position can ever repeat any more, i.e., you can clear your history and start afresh. On the other hand, if you do collect 50 positions without pawn/capture, then the other remis rule kicks in.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T10:42:04.213Z
Answers.Text: Good luck checking for "dead", though :P (BTW, considering hash, I would be surprised if the number of "sensible" chess positions is larger than 10^20, and the number of positions that ever occurred in RL greater than 10^10.)
Answers.UserDisplayName: Hauke Reddmann
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T08:45:35.607Z
Answers.LastActivityDate: 2021-04-05T08:45:35.607Z
Answers.UserDisplayName: Hagen von Eitzen
Answers.Body: <p>I wouldn't worry too much. It is true that there are 10^120-ish possible positions, but you won't have to worry about most of them. To specify a position, you only need a <a href="https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation" rel="nofollow noreferrer">FEN string</a>. You can therefore keep track of the FEN strings corresponding to all positions that were reached during a game and check if one of them appears three times for the draw condition to activate.</p>
  <p>While you may want to define &quot;hashes&quot; and then make a second check if three positions have the same hash, I don't see how this could be a significant improvement over the brute force method.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T16:34:41.507Z
Answers.LastActivityDate: 2021-04-06T11:51:16.283Z
Answers.LastEditDate: 2021-04-06T11:51:16.283Z
Answers.UserDisplayName: David
Answers.Body: <p>You might want to consider computing a <a href="https://en.wikipedia.org/wiki/Zobrist_hashing" rel="nofollow noreferrer">Zobrist Hash</a> of each position, and checking for three occurrences of the same hash. Hash collisions, as you mention, are possible but rare.</p>
  <p>If you want you could use this in combination with storing the list of moves made (since space seems to be a concern this should require much less space than storing the board state after each move) and then, in case you detect the same hash occurring three times, you could check for a false positive by using the list of moves to recreate the three positions and verify that they are, in fact, identical.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T12:40:06.210Z
Answers.LastActivityDate: 2021-04-05T12:40:06.210Z
Answers.UserDisplayName: loxod
Answers.Body: <p>Firstly, I wouldn't worry about tracking board state history, computers are powerful enough that modern frameworks like React, can afford to basically store the entire history of your interaction with a website, just because it makes debugging and writing tests way easier.</p>
  <p>But if you really want to, here's how I'd do it efficiently:
  You don't need to store the entire board, since it's mostly empty. It can have a max 24 occupied positions out of 64, so you only need to store those. The only other thing you have to worry about, is whether the king can castle(because technically, 2 identical board states are different for the purpose of the draw rules, if the king can castle in one and not the other).</p>
  <p>So you have a board position, represented by an unsigned short, of which bit 0 is black/white, 1-3 is row, 4-6 is column and 7-9 is piece_type.</p>
  <p>You have a board struct</p>
  <pre><code>{
  unsigned short positions[];
  byte num_positions
  }
  </code></pre>
  <p>The positions are stored in the order(doesn't matter, it just has to be consistent, so they can be compared) of Ascending row and Ascending column within row. And to efficiently compare 2 boards: check if num_positions is the same, if not(one piece has taken another) return false, loop through positions, if board1.positions[n] != board2.positions[2], return false, return true.</p>
  <p>Another way to do it, would be to have a struct with:</p>
  <pre><code>{
  unsigned short pos1,
  unsigned short pos2,
  ...
  unsigned short pos24
  }
  </code></pre>
  <p>less space efficient, but equality comparison is simply board1 ^(bitwise XOR) board2 &gt; 0</p>
  <p>Then, for the game, you have a Stack, that you push each new board state onto as a player makes a move. i.e.</p>
  <pre><code>boardHistory.push(latestMove)
  </code></pre>
  <p>If something happens that obviously invalidates the 3 repetition rule, like a piece being taken, promoted, or castling no longer possible, toss the old boardHistory, i.e.</p>
  <pre><code>boardHistory = new Stack&lt;BoardHistory&gt;(latestMove)
  </code></pre>
  <p>When you search for repetitions, you only have to search a small stack for two repetitions, because it will get cleared repeatedly throughout the game and the board comparison is very efficient as well.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T21:49:56.360Z
Answers.LastActivityDate: 2021-04-05T21:49:56.360Z
Answers.UserDisplayName: Eugene
Answers.Body: <p>You'll want to store the move history anyhow, because that record is useful.  The move history is tiny.</p>
  <p>You'll probably store a hash of each board position.  While it is true there are only 2^K hash values, and the birthday paradox says that these will have a decent chance of having a collision in a universe of 2^(K/2) items, the point of hashing isn't to make comparison faster.  Only after you find a hash collision do you need to compare board states.</p>
  <p>So your snapshot can be highly compressed.  An example of a valid snapshot is the series of moves used to reach that state; from it, you can generate the board state; this isn't unique, but we don't care, as we don't compare the move sequence, we compare the genearted board.</p>
  <p>There are certainly better ways, but that will only matter if you have a huge database of every chess position; and by that point you should be organizing your chess positions in a more interesting manner than &quot;board state&quot; anyhow (like, by material first, then equivalence classes of material positions to game solutions).</p>
  <p>So keep track of each move, and a map from the hash of the board position to the indexes of the moves with that hash.  Then to detect a draw, when you add to that hash-&gt;index, actually generate the board for each of them and compare them for equality.</p>
  <p>Even with a 32 bit hash, it takes an average of about a 32,000 length game to have a decent chance of <strong>one</strong> false collision here (birthday paradox; a random bucket of N numbers has a decent chance at a collision at O(sqrt(N)) elements).  So the performance impact of false checks is going to be small; the number of times you'll have to &quot;wastefully&quot; generate the boards and not have a collision is going to be tiny.</p>
  <p>In fact, you'll have to work hard to force that to happen, so you'll want good unit test coverage of that case.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-07T14:38:36.213Z
Answers.LastActivityDate: 2021-04-07T14:38:36.213Z
Answers.UserDisplayName: Yakk
Answers.Body: <p>My <a href="https://github.com/gregsdennis/QuantumChess" rel="nofollow noreferrer">exploration of Quantum Chess</a> does, in a way.</p>
  <p>When any move is made, a copy of the board is made, then the move is performed on the copy (and any other copies where that move is valid).  In this way, there is always a copy of the board for each state the board has been in throughout its history.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-06T20:45:24.027Z
Answers.LastActivityDate: 2021-04-06T20:45:24.027Z
Answers.UserDisplayName: gregsdennis
Answers.Body: <p>The accepted answer points out that a GUI doesn't need to be so fast.  But if you did want to work on an engine, consider this: 2^64 is a really big number.  By the <a href="https://en.wikipedia.org/wiki/Birthday_problem" rel="nofollow noreferrer">birthday paradox</a>, you will need 2^32 board positions, on average, to find 2 duplicates.  If we assume that all positions are just 1 move away from a draw (an absurdly conservative estimate), that says that on average it will take 4 billion positions to come up with a collision.</p>
  <p>Even in a chess engine, which has to worry about trees of moves, not just a linear stream, you only have to look within the current branch for positions that draw, so the collisions can only come from that line.  Even if we made another extreme assumption that the game lasts less than a thousand moves, there is a 0.0000232% chance of finding a collision.</p>
  <p>Finding a collision is like mis-scoring the board.  It makes the board evaluate to a draw, even though it may have been a win.  So unless your engine's rate of mis-scoring boards is less than 1 in a million, these collisions can be handwaved away.</p>
  <p>And, obviously, if one does occur, you can always check the game history to be sure.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T16:41:40.960Z
Answers.LastActivityDate: 2021-04-05T16:41:40.960Z
Answers.UserDisplayName: Cort Ammon
Answers.Body: <p>Your actual question is which data structure to use to find repeated board positions.</p>
  <p>It is irrelevant how many theoretical chess scenarios there are; the most relevant &quot;big number&quot; in this context would be the maximum length of a <em>concrete</em> game you want to support. As of right now, the longest recorded chess game had <a href="https://en.wikipedia.org/wiki/List_of_world_records_in_chess#Longest_game" rel="nofollow noreferrer">269 moves</a>.</p>
  <p>This is a ridiculous low number for a current device (no matter if a PC or a smartphone or even just one of the nicer microcontrollers).</p>
  <p>To be guaranteed to be correct and still easily humanly understandable, you could find a representation of the board as an explicit array (i.e., list off all pieces with their X/Y coordinates and a special mark if removed). A naive implementation would need 7 bits per piece to encode position on the board and whether it was taken already; or let's call it 8 bits for ease of programming. This means 32 bytes (due to 32 pieces) to encode the whole board (1 byte per piece). 32*269 is somewhere between 8 KB and 9 KB of storage. ( * )</p>
  <p>At this point I would immediately stop looking for optimized solutions, the numbers are just too small. I would err on the side of making the code easier to maintain and develop, to avoid errors, and make for a more pleasant programmer experience.</p>
  <p>To find duplicates, depending of your programming language, you could use a hash/dictionary (with the encoding of the board, i.e. the 32 bytes, as key; and the number of occurrences as value). If your language of choice has no easily usable hash data structure, you could keep a sorted list of these 32-byte tupels and do a simple linear scan operation to look for repeated numbers. I would not go to the excess of creating an involved tree structure or anything like that at all.</p>
  <p>As to your literal question on how chess programs do that: I have not looked at the source code of any chess program, but as a programmer, I would simply use whatever data structure is most comfortable, and comes &quot;out of the box&quot; with the required operations (in the form of a standard library of my programming language) to re-use, and to avoid re-inventing the wheel. There are other aspects than duplicate detection: e.g. at some point your program <em>needs</em> the explicit information about which piece just moved from where to where (to be able to display just that movement on the screen, possibly in an animated fashion).</p>
  <p>At some points your program <em>needs</em> a complete representation of the board (i.e. if you want to be able to mouse-over a piece and highlight it, to show the user that he is about to &quot;pick up&quot; this piece). And so on. All these things factor into which data structure to use, and it is not unheard of to have multiple structures available in parallel when there is so little data involved. So there surely is no final answer on how the GUI of a chess program stores this.</p>
  <hr />
  <p>(*) Side note: This is just the first naive data structure that comes to my mind. One would need to take a little care to build the array in a way that the <em>order</em> of equivalent pieces (i.e. all the black pawns) does not matter, but this would be relatively simple and left as an exercise for the reader. The point of the answer is to show any one algorithm with relatively little RAM usage, not the best or most elegant algorithm.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-06T14:50:39.330Z
Answers.LastActivityDate: 2021-04-06T14:56:39.507Z
Answers.LastEditDate: 2021-04-06T14:56:39.507Z
Answers.UserDisplayName: AnoE
Answers.Body: <p>You seem to not understand the concept of a hash. The whole point of a hash is that it is lossy compression. A lossy compression by definition allows collisions. A collision being theoretically possible and a collision occurring are two very different things. The probability of two random numbers hashing to the same <code>long</code> is one in 16 billion billion. So unless your program is being used a <em>lot</em>, the chances of seeing a collision is tiny.</p>
  <p>Storing all the moves is hardly much of an imposition. The maximum size of a packet is 2^16 bytes, so if you're storing the board as 256 bytes, then you can fit up to 256 moves in a single packet.</p>
  <p>On top of that, there are lossless compressions you can use. A basic one would be to store the location of each of the 24 pieces, for 48 bytes. You'd have to deal with removed and promoted pieces, so say 52 bytes. More complicated systems can bring that down.</p>
  <p>You can also just store each move; the board state then can be reconstructed from the move history. You can combine this with hashing; if none of the hashes match, you know none of the board states match. If the hashes do match, then you can spend the effort reconstructing board states. Once every 16 billion billion moves, a hash collision will require you to reconstruct a board state unnecessarily.</p>
  <p>You can also dump your history every time a piece is captured or a pawn moves, as the board state can't repeat from then on.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-06T23:25:12.467Z
Answers.LastActivityDate: 2021-04-06T23:25:12.467Z
Answers.UserDisplayName: Acccumulation
Answers.Body: <p>You are doing a chess GUI, not a chess engine right?</p>
  <p>Chess GUI doesn't need to be super efficient, because you have no more than a chess game to look for. Even a game over 200 moves about the world record is absolutely nothing for a computer.</p>
  <p>I would just simply keep your positions with an array of strings like FEN format (or any other format), and then simply linear scan the whole game for repetitions.</p>
  <p>If you want to get fancy, try <a href="https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf" rel="noreferrer">https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T08:35:17.200Z
Answers.Text: “Even a game over 200 moves about the world record is absolutely nothing for a computer.” Exactly. What makes chess _engines_ expensive is that they need to worry not only about a linear history but about a _tree_ of possible ways the game can develop. Storing that up to a depth of 200 would be utterly impossible, because the number of nodes scales exponentially (resulting in more nodes than there are atoms in the observable universe). But a GUI doesn't need to deal with that issue, because the tree will already have been narrowed down to a single branch.
Answers.UserDisplayName: leftaroundabout
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T15:24:35.167Z
Answers.Text: You really only have to scan backwards to the last capture.  Since there's no way to add pieces to the board, anything before the last piece captured is guaranteed not to be a repeat.
Answers.UserDisplayName: Darrel Hoffman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T16:57:52.573Z
Answers.Text: The last capture or the last pawn move.
Answers.UserDisplayName: Spitemaster
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-06T15:01:28.907Z
Answers.Text: Actually to check for repetition it's o(n^2) if done naively (check board against all previous boards): 200^2 = 40 000. And done for 32 pieces, is a abit over 1 million comparisons. By far still possible for computers to handle, but you do get into the "heavy to compute" period. Quadratic growth is just bad.
Answers.UserDisplayName: paul23
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-06T15:42:54.027Z
Answers.Text: Forget scans. Just keep a FEN: count dictionary and if (fen_dict[current_pos] +=1) >= 3 you have a threefold repetition. It's maybe 3 lines of code in nearly any modern language and it's constant time.
Answers.UserDisplayName: Adam
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-04T23:29:50.293Z
Answers.LastActivityDate: 2021-04-04T23:29:50.293Z
Answers.UserDisplayName: SmallChess
Body: <p>I am creating a chess GUI for UCI engine as a hobby. I keep the history of moved positions (e.g., (4,6) -&gt; (4,4) for the pawn in front of the white king moving forward 2 squares) and the type of the moved piece (e.g., pawn), and some minor states like castling, capturing, etc).</p>
  <p>Now I am trying to implement checking for draw conditions. At first, I thought it was about repeated moves, but after seeing <a href="https://en.wikipedia.org/wiki/Threefold_repetition" rel="noreferrer">the official rules</a>, it seems that it is about repeated positions. <strong>Is it practically possible to check for this without keeping the snapshot of the whole board (in my case, a 8x8 integer array, 256 bytes) for each move?</strong> I thought about taking a hash value of the board, but even if I take a <code>long</code> value, it can only represent 2^64 values, and according to a quick search, the number of all possible positions is about <a href="https://www.chess.com/forum/view/more-puzzles/number-of-possible-chess-configurations" rel="noreferrer">10^120</a>, so hash collisions will occur.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-05T05:58:38.237Z
Comments.Text: 256 bytes times a very theoretical maximum of 1000 moves is 256 KB, which is nothing on any hardware that might run something like a "GUI". To speed up comparing positions, you can still store the hash, and only compare full positions (which might involve recreating the position) if the hash matches.
Comments.UserDisplayName: Guntram Blohm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-05T08:31:56.483Z
Comments.Text: Hash collisions may occur, but even for a game with hundreds of moves, it will be rare. And within those rare hash collisions you can easily check the hard way. But I don't think it will be necessary to do hashing for this. You can also make it easier on your processor by splitting the game into blocks depending on whether a pawn has been moved, castling has been done or a piece has been captured. That makes each collision search space a _lot_ smaller.
Comments.UserDisplayName: Arthur
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-05T17:15:59.687Z
Comments.Text: If you're worried about the space overhead, you can easily compress your 256-byte array into 32 bytes before saving it in the game history array -- there are only 13 possible states for a square, so you can fit two in each byte. And you can save a 32-bit hash of each position to allow for faster checking; then if you find a matching hash, you can check the board contents, castling status etc to see if the match is genuine. But I doubt that the hashing approach is worth the programming time.
Comments.UserDisplayName: TonyK
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-05T17:24:05.660Z
Comments.Text: For the particular purpose of detecting draw by repetition, it would be enough to store positions since the last material exchange only.
Comments.UserDisplayName: sleepy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-05T18:35:20.193Z
Comments.Text: @sleepy: or the last pawn move.
Comments.UserDisplayName: TonyK
Tags: <programming>
Title: Do chess programmes keep a history of the full board for each move?
ThreadText: # Do chess programmes keep a history of the full board for each move?
  
  (Asked by: username_0 on 2021-04-04)
  
  I am creating a chess GUI for UCI engine as a hobby. I keep the history of moved positions (e.g., (4,6) -> (4,4) for the pawn in front of the white king moving forward 2 squares) and the type of the moved piece (e.g., pawn), and some minor states like castling, capturing, etc).
  
  Now I am trying to implement checking for draw conditions. At first, I thought it was about repeated moves, but after seeing [the official rules](https://en.wikipedia.org/wiki/Threefold_repetition), it seems that it is about repeated positions. **Is it practically possible to check for this without keeping the snapshot of the whole board (in my case, a 8x8 integer array, 256 bytes) for each move?** I thought about taking a hash value of the board, but even if I take a `long` value, it can only represent 2^64 values, and according to a quick search, the number of all possible positions is about [10^120](https://www.chess.com/forum/view/more-puzzles/number-of-possible-chess-configurations), so hash collisions will occur.
  
  **Tags:** programming
  
  > **Comments:**
  > **username_1**: 256 bytes times a very theoretical maximum of 1000 moves is 256 KB, which is nothing on any hardware that might run something like a "GUI". To speed up comparing positions, you can still store the hash, and only compare full positions (which might involve recreating the position) if the hash matches.  
  > **username_2**: Hash collisions may occur, but even for a game with hundreds of moves, it will be rare. And within those rare hash collisions you can easily check the hard way. But I don't think it will be necessary to do hashing for this. You can also make it easier on your processor by splitting the game into blocks depending on whether a pawn has been moved, castling has been done or a piece has been captured. That makes each collision search space a _lot_ smaller.  
  > **username_3**: If you're worried about the space overhead, you can easily compress your 256-byte array into 32 bytes before saving it in the game history array -- there are only 13 possible states for a square, so you can fit two in each byte. And you can save a 32-bit hash of each position to allow for faster checking; then if you find a matching hash, you can check the board contents, castling status etc to see if the match is genuine. But I doubt that the hashing approach is worth the programming time.  
  > **username_4**: For the particular purpose of detecting draw by repetition, it would be enough to store positions since the last material exchange only.  
  > **username_3**: @username_4: or the last pawn move.  
  
  ---
  
  ## 11 answers
  
  ### Answer by username_16 on 2021-04-04. Score: 23 | Accepted answer
  
  You are doing a chess GUI, not a chess engine right?
  
  Chess GUI doesn't need to be super efficient, because you have no more than a chess game to look for. Even a game over 200 moves about the world record is absolutely nothing for a computer.
  
  I would just simply keep your positions with an array of strings like FEN format (or any other format), and then simply linear scan the whole game for repetitions.
  
  If you want to get fancy, try <https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf>.
  
  > **Comments:**
  > **username_17**: “Even a game over 200 moves about the world record is absolutely nothing for a computer.” Exactly. What makes chess _engines_ expensive is that they need to worry not only about a linear history but about a _tree_ of possible ways the game can develop. Storing that up to a depth of 200 would be utterly impossible, because the number of nodes scales exponentially (resulting in more nodes than there are atoms in the observable universe). But a GUI doesn't need to deal with that issue, because the tree will already have been narrowed down to a single branch.  
  > **username_18**: You really only have to scan backwards to the last capture.  Since there's no way to add pieces to the board, anything before the last piece captured is guaranteed not to be a repeat.  
  > **username_19**: The last capture or the last pawn move.  
  > **username_20**: Actually to check for repetition it's o(n^2) if done naively (check board against all previous boards): 200^2 = 40 000. And done for 32 pieces, is a abit over 1 million comparisons. By far still possible for computers to handle, but you do get into the "heavy to compute" period. Quadratic growth is just bad.  
  > **username_21**: Forget scans. Just keep a FEN: count dictionary and if (fen_dict[current_pos] +=1) >= 3 you have a threefold repetition. It's maybe 3 lines of code in nearly any modern language and it's constant time.  
  
  ---
  
  ### Answer by username_5 on 2021-04-04. Score: 4
  
  Most programmers only record the move (and some other key flags) played and only the position it's thinking about.
  
  A move structure often contains the move, castling rights, move ply, 50 move ply, EP square, and, and a hash value. (Depending on how involved you want the AI, you may add other data, such as what the computer evaluates this position to help with the AB search.) By restoring the flags and using simple logic to retract the move, a previous position can be restored.
  
  
  ---
  
  ### Answer by username_6 on 2021-04-05. Score: 3
  
  There is only little memory required for the purpose of checking the rules for remis: Either party can request a draw when a position repeats three times or there is no pawn move or capture within 50 (or is it 70?) moves. In your GUI, you may want to *automatically* end the game in a remis in such a condition (even though formally this has to be requested by a player).
  
  Then note that you never need to keep track of more than 50 positions because whenever a pawn moves or a piece gets captured, no previous position can ever repeat any more, i.e., you can clear your history and start afresh. On the other hand, if you do collect 50 positions without pawn/capture, then the other remis rule kicks in.
  
  > **Comments:**
  > **username_7**: Good luck checking for "dead", though :P (BTW, considering hash, I would be surprised if the number of "sensible" chess positions is larger than 10^20, and the number of positions that ever occurred in RL greater than 10^10.)  
  
  ---
  
  ### Answer by username_8 on 2021-04-05. Score: 3
  
  I wouldn't worry too much. It is true that there are 10^120-ish possible positions, but you won't have to worry about most of them. To specify a position, you only need a [FEN string](https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation). You can therefore keep track of the FEN strings corresponding to all positions that were reached during a game and check if one of them appears three times for the draw condition to activate.
  
  While you may want to define "hashes" and then make a second check if three positions have the same hash, I don't see how this could be a significant improvement over the brute force method.
  
  
  ---
  
  ### Answer by username_9 on 2021-04-05. Score: 2
  
  You might want to consider computing a [Zobrist Hash](https://en.wikipedia.org/wiki/Zobrist_hashing) of each position, and checking for three occurrences of the same hash. Hash collisions, as you mention, are possible but rare.
  
  If you want you could use this in combination with storing the list of moves made (since space seems to be a concern this should require much less space than storing the board state after each move) and then, in case you detect the same hash occurring three times, you could check for a false positive by using the list of moves to recreate the three positions and verify that they are, in fact, identical.
  
  
  ---
  
  ### Answer by username_10 on 2021-04-05. Score: 1
  
  Firstly, I wouldn't worry about tracking board state history, computers are powerful enough that modern frameworks like React, can afford to basically store the entire history of your interaction with a website, just because it makes debugging and writing tests way easier.
  
  But if you really want to, here's how I'd do it efficiently:
  You don't need to store the entire board, since it's mostly empty. It can have a max 24 occupied positions out of 64, so you only need to store those. The only other thing you have to worry about, is whether the king can castle(because technically, 2 identical board states are different for the purpose of the draw rules, if the king can castle in one and not the other).
  
  So you have a board position, represented by an unsigned short, of which bit 0 is black/white, 1-3 is row, 4-6 is column and 7-9 is piece\_type.
  
  You have a board struct
  
  ```
  {
  unsigned short positions[];
  byte num_positions
  }
  
  ```
  
  The positions are stored in the order(doesn't matter, it just has to be consistent, so they can be compared) of Ascending row and Ascending column within row. And to efficiently compare 2 boards: check if num\_positions is the same, if not(one piece has taken another) return false, loop through positions, if board1.positions[n] != board2.positions[2], return false, return true.
  
  Another way to do it, would be to have a struct with:
  
  ```
  {
  unsigned short pos1,
  unsigned short pos2,
  ...
  unsigned short pos24
  }
  
  ```
  
  less space efficient, but equality comparison is simply board1 ^(bitwise XOR) board2 > 0
  
  Then, for the game, you have a Stack, that you push each new board state onto as a player makes a move. i.e.
  
  ```
  boardHistory.push(latestMove)
  
  ```
  
  If something happens that obviously invalidates the 3 repetition rule, like a piece being taken, promoted, or castling no longer possible, toss the old boardHistory, i.e.
  
  ```
  boardHistory = new Stack<BoardHistory>(latestMove)
  
  ```
  
  When you search for repetitions, you only have to search a small stack for two repetitions, because it will get cleared repeatedly throughout the game and the board comparison is very efficient as well.
  
  
  ---
  
  ### Answer by username_11 on 2021-04-07. Score: 0
  
  You'll want to store the move history anyhow, because that record is useful. The move history is tiny.
  
  You'll probably store a hash of each board position. While it is true there are only 2^K hash values, and the birthday paradox says that these will have a decent chance of having a collision in a universe of 2^(K/2) items, the point of hashing isn't to make comparison faster. Only after you find a hash collision do you need to compare board states.
  
  So your snapshot can be highly compressed. An example of a valid snapshot is the series of moves used to reach that state; from it, you can generate the board state; this isn't unique, but we don't care, as we don't compare the move sequence, we compare the genearted board.
  
  There are certainly better ways, but that will only matter if you have a huge database of every chess position; and by that point you should be organizing your chess positions in a more interesting manner than "board state" anyhow (like, by material first, then equivalence classes of material positions to game solutions).
  
  So keep track of each move, and a map from the hash of the board position to the indexes of the moves with that hash. Then to detect a draw, when you add to that hash->index, actually generate the board for each of them and compare them for equality.
  
  Even with a 32 bit hash, it takes an average of about a 32,000 length game to have a decent chance of **one** false collision here (birthday paradox; a random bucket of N numbers has a decent chance at a collision at O(sqrt(N)) elements). So the performance impact of false checks is going to be small; the number of times you'll have to "wastefully" generate the boards and not have a collision is going to be tiny.
  
  In fact, you'll have to work hard to force that to happen, so you'll want good unit test coverage of that case.
  
  
  ---
  
  ### Answer by username_15 on 2021-04-06. Score: 0
  
  You seem to not understand the concept of a hash. The whole point of a hash is that it is lossy compression. A lossy compression by definition allows collisions. A collision being theoretically possible and a collision occurring are two very different things. The probability of two random numbers hashing to the same `long` is one in 16 billion billion. So unless your program is being used a *lot*, the chances of seeing a collision is tiny.
  
  Storing all the moves is hardly much of an imposition. The maximum size of a packet is 2^16 bytes, so if you're storing the board as 256 bytes, then you can fit up to 256 moves in a single packet.
  
  On top of that, there are lossless compressions you can use. A basic one would be to store the location of each of the 24 pieces, for 48 bytes. You'd have to deal with removed and promoted pieces, so say 52 bytes. More complicated systems can bring that down.
  
  You can also just store each move; the board state then can be reconstructed from the move history. You can combine this with hashing; if none of the hashes match, you know none of the board states match. If the hashes do match, then you can spend the effort reconstructing board states. Once every 16 billion billion moves, a hash collision will require you to reconstruct a board state unnecessarily.
  
  You can also dump your history every time a piece is captured or a pawn moves, as the board state can't repeat from then on.
  
  
  ---
  
  ### Answer by username_12 on 2021-04-06. Score: -1
  
  My [exploration of Quantum Chess](https://github.com/username_12/QuantumChess) does, in a way.
  
  When any move is made, a copy of the board is made, then the move is performed on the copy (and any other copies where that move is valid). In this way, there is always a copy of the board for each state the board has been in throughout its history.
  
  
  ---
  
  ### Answer by username_13 on 2021-04-05. Score: -1
  
  The accepted answer points out that a GUI doesn't need to be so fast. But if you did want to work on an engine, consider this: 2^64 is a really big number. By the [birthday paradox](https://en.wikipedia.org/wiki/Birthday_problem), you will need 2^32 board positions, on average, to find 2 duplicates. If we assume that all positions are just 1 move away from a draw (an absurdly conservative estimate), that says that on average it will take 4 billion positions to come up with a collision.
  
  Even in a chess engine, which has to worry about trees of moves, not just a linear stream, you only have to look within the current branch for positions that draw, so the collisions can only come from that line. Even if we made another extreme assumption that the game lasts less than a thousand moves, there is a 0.0000232% chance of finding a collision.
  
  Finding a collision is like mis-scoring the board. It makes the board evaluate to a draw, even though it may have been a win. So unless your engine's rate of mis-scoring boards is less than 1 in a million, these collisions can be handwaved away.
  
  And, obviously, if one does occur, you can always check the game history to be sure.
  
  
  ---
  
  ### Answer by username_14 on 2021-04-06. Score: -1
  
  Your actual question is which data structure to use to find repeated board positions.
  
  It is irrelevant how many theoretical chess scenarios there are; the most relevant "big number" in this context would be the maximum length of a *concrete* game you want to support. As of right now, the longest recorded chess game had [269 moves](https://en.wikipedia.org/wiki/List_of_world_records_in_chess#Longest_game).
  
  This is a ridiculous low number for a current device (no matter if a PC or a smartphone or even just one of the nicer microcontrollers).
  
  To be guaranteed to be correct and still easily humanly understandable, you could find a representation of the board as an explicit array (i.e., list off all pieces with their X/Y coordinates and a special mark if removed). A naive implementation would need 7 bits per piece to encode position on the board and whether it was taken already; or let's call it 8 bits for ease of programming. This means 32 bytes (due to 32 pieces) to encode the whole board (1 byte per piece). 32\*269 is somewhere between 8 KB and 9 KB of storage. ( \* )
  
  At this point I would immediately stop looking for optimized solutions, the numbers are just too small. I would err on the side of making the code easier to maintain and develop, to avoid errors, and make for a more pleasant programmer experience.
  
  To find duplicates, depending of your programming language, you could use a hash/dictionary (with the encoding of the board, i.e. the 32 bytes, as key; and the number of occurrences as value). If your language of choice has no easily usable hash data structure, you could keep a sorted list of these 32-byte tupels and do a simple linear scan operation to look for repeated numbers. I would not go to the excess of creating an involved tree structure or anything like that at all.
  
  As to your literal question on how chess programs do that: I have not looked at the source code of any chess program, but as a programmer, I would simply use whatever data structure is most comfortable, and comes "out of the box" with the required operations (in the form of a standard library of my programming language) to re-use, and to avoid re-inventing the wheel. There are other aspects than duplicate detection: e.g. at some point your program *needs* the explicit information about which piece just moved from where to where (to be able to display just that movement on the screen, possibly in an animated fashion).
  
  At some points your program *needs* a complete representation of the board (i.e. if you want to be able to mouse-over a piece and highlight it, to show the user that he is about to "pick up" this piece). And so on. All these things factor into which data structure to use, and it is not unheard of to have multiple structures available in parallel when there is so little data involved. So there surely is no final answer on how the GUI of a chess program stores this.
  
  ---
  
  (\*) Side note: This is just the first naive data structure that comes to my mind. One would need to take a little care to build the array in a way that the *order* of equivalent pieces (i.e. all the black pawns) does not matter, but this would be relatively simple and left as an exercise for the reader. The point of the answer is to show any one algorithm with relatively little RAM usage, not the best or most elegant algorithm.
  
  
  ---
  
  