Do chess programmes keep a history of the full board for each move?

Question

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.

Answer 1

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.

Answer 2

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

Answer 4

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.

Answer 5

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.

Answer 6

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 7

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 8

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 9

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, 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 10

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.

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.

Answer 11

My exploration of Quantum Chess 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.