user27094: 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, 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, so hash collisions will occur.

user27289: 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.

user27284: You might want to consider computing a Zobrist Hash 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.

user4149: 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.

user18809: 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. 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.

user9684: 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.

user825: 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.

27094: <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>
 27289: <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>
 27284: <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>
 4149: <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>
 18809: <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>
 9684: <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>
 825: <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>
