Oh, that’s the answer to my question above – thanks. The link in post #9 uses 4-bits of the e.p (e.p. flag and e.p. column of the baggy pawn).
The most efficient way to encode a move is almost certainly a look up table of some sort, as it’s relatively easy to calculate all possible moves from a given board position. Just calculate them all in some systematic fashion, list them in some systematic order, find the chosen move in that list, and provide its index.
The only theoretical improvement over that would be some scheme which knows which moves are “likely” to be made, and does variable length encoding such that likely moves are shorter than unlikely ones.
Something I’ll throw out there because I bothered to think about it and it’s different from all the other suggestions. It’s not an all-inclusive solution, but a different way of thinking about it.
- Record the position (6 bits) of each of the 16 original pieces (96 bits total). All other positions are of course empty.
- Any piece that repeats the position of a king is not actually on the board; disregard its position reading.
- Promoted pieces have to be encoded with an additional 6 bits: 1 for black/white, 3 for which pawn it takes the place of (so you’ll still use the position reading for that original pawn), and 2 bits for the promotion type (queen, rook, knight, bishop).
I guess this seems to benefit from a smaller starting size by not having to encode the empty spaces, but doesn’t shrink at all with fewer pieces on the board (even increases a bit in the case of promotions, but not much).
There are actually 32 original pieces, so you’d need to double that.
:smack: I knew I had to be missing something. What I get for posting tired, I guess.
Oh, well in that case you should definitely use XML over SOAP with a web-based, AJAX enabled distribution system. I imagine you could encode an entire chessboard in less than half a meg!
That was the first way I came at this, too. It certainly generates the shortest fixed-length encoding of the board, but the variable-length systems will beat it for an average length. The list of all valid positions has to leave room for a lot of highly unlikely positions (theoretically, white could have ten knights on the board).
The answer also changes depending on application. The OP presented a short context-free representation of a board. If you’re looking at representing the state of a game, it requires extra data (as previously noted). If you’re looking at preserving the record of a game, it’s almost certainly shorter to list the moves than to save the state of the game after each move.
Not necessarily. We’re already assuming that we have some sort of end-of-file signal, or the variable-length systems have no advantage. Then we just need some way of systematically deciding which positions are more likely, and put those earlier on our lookup table. They’ll then get lower numbers, which can be represented in fewer bytes. The net savings should be the same as for the other variable-file-length methods, or even greater (since some unlikely positions nevertheless have few pieces on the board).
Taking the above idea, and noticing that pieces are more likely to be around pieces of their own color, I changed the Huffman categories from black and white to ‘of same color as previous piece’ and ‘of opposite color to previous piece’.
The results are
square status weight prefix code length
empty 320 0 1
similar pawn 120 111 3
opposite pawn 40 1100 4
similar rook 30 1000 4
opposite rook 10 110100 6
similar knight 30 1001 4
opposite knight 10 110101 6
similar bishop 30 1010 4
opposite bishop 10 110110 6
similar queen 15 10110 5
opposite queen 5 1101110 7
similar king 15 10111 5
opposite king 5 1101111 7
The starting board comes out to be 149 bits with the particular choice of weights given above. Since we need 1 additional bit to indicate what color the first piece is, the total comes out to 150 bits.
You can tweak the weights depending on how frequent color switches are on a typical chess board. Using the above set of weights, each color switch costs about 2 bits. Other sets of weights can punish color switches more or less.
For example:
square status weight prefix code length
empty 320 0 1
similar pawn 140 10 2
opposite pawn 20 11101 5
similar rook 35 11110 5
opposite rook 5 1110001 7
similar knight 35 11111 5
opposite knight 5 1110010 7
similar bishop 35 1100 4
opposite bishop 5 1110011 7
similar queen 18 11010 5
opposite queen 2 11100000 8
similar king 18 11011 5
opposite king 2 11100001 8
which brings the starting board to 143 bits, but punishes color switches with 3 bits each time.
We can get more fancy and add 1 bit to indicate whether we are using the codebook above or a codebook which does not punish color switches (i.e. which has equal weights for similar and opposite pieces, and which results in a codebook similar to the one given by chrisk)
This way, we would use the above codebook for chess boards during the beginning of the game, when there are a lot of pieces, and few color switches, and we could use chrisk’s codebook later on when there are fewer pieces and we have a lot of color switches.
I think that using something like the above, you should get away with less than 150 bits to represent just about any chess board.
One other thing about castling: you need to flag King’s and Queen’s side separately. Moving either Rook bars castling on that side, but it’s still valid on the other. (There’s a line in the Benko Gambit where Black exchanges Bishops on f1, and if White takes with the KR he could still castle long, though why he’d want to in the Benko is a whole other question.)
I’m just as much a chess geek as glee, but by no means as good a player. 
Encoding moves can be done better than that. 6 bits for the initial square. That identifies the piece to be moved, which then has a limited number of moves, with 28 being the maximum (for a queen). A consistent definition for the numbering needs to be created so that it works anywhere on the board (e.g., for the queen, start heading up the board - from White to Black - and move outwards, then rotate clockwise).
With this you require 6 bits for the initial square, then 5 bits if a queen is moving, 4 for a rook, bishop or king (to include castling), 3 for a knight and 2 for a pawn (to include taking, which includes en passant).
Using data from http://www.vanheusden.com/misc/datamining_on_chess.html I calculate that the average number of bits required for the move is around 3.4. So the average per move is 9.4.
Notes:
-
This can be reduced further by choosing consistent ways to only take into account the moves that can be made. I don’t have the stats for that, but I would guess that most queen moves would require 4 bits only, most Bishop, Rook and King moves only 3 and most pawn moves only 1. The average per move should drop to below 9 bits.
-
On promotion you’ll need an extra 2 bits for the pawn to choose the piece, but this only accounts for a very small fraction of moves).
-
Feel free to compress the resulting data and gain further savings.
This is still inefficient compared to other schemes mentioned here past move 15-20, but is good for the opening moves, which will not benefit from any savings due to sparsity.
So add an extra bit at the start of each position to choose between move encoding and some positional variant that benefits from sparsity later in the game.
Obvious improvement:
Maximum of 5 bits for the initial piece to be moved - forget identifying the squares. Promotions retain the identifier of the pawn they were promoted from.
That’s around 8 bits per move, so move encoding should be efficient compared to most schemes up to move 20 or so.
I think we should encode the possibility of castling and en passant, but not the repetition stuff and 3 moves. They are a more integral part of the game.
The 4 castling possibilities, I think, could just be four 0/1 pairs after all the squares have been covered.
Then we place the kings according to Chronos idea.
Then, if an en passant can be made, we code the square at which the en passant pawn is positioned. Otherwise we just end the code.
and 50* moves, I meant
Still not quite right. Don’t identify the piece by piece name, identify it by its current position on the board. That is to say: Start at the top left corner of the board. Go through all of the spaces, in order. Whenever a space is occupied, increment your count. When the count reaches the number specified, that’s the piece you’re supposed to move.
Also, you only need three bits for the king. A king in vacuum has eight “normal” moves, which is 3 bits. The king also, in general, has two castling moves. But it never has both. If castling is still possible, the king must still be in its starting position, meaning that it has (at most) five normal moves, plus the two castlings. So it’s still always 8 possibilities or less, and 3 bits suffices.
If we’re concerned about practical applications, of course, we need to sacrifice a little efficiency. All of the super-efficient methods proposed thus far would give radically different results if a single bit of the transmission is flipped. Given this, it would be prudent to add some number of check bits, for error correction or at least detection.
Yep. It would be embarrassing during a tournament, to decode a garbled bit-stream and have one player suddenly end up with, say, three kings.
Or, nothing but pawns. Or all his pieces located on the same square … or spelling out a rude word.
People, people. Are we not playing with fire?
If the goal is to reduce bandwidth as much as humanly possible, a pretty obvious improvement is to not send the entire board state every turn. If a board description can contain a reference to a previous board plus a list of moves that define the delta from that referenced board, then most transmissions will be a few bytes. You need a protocol that’s designed to detect the situation where the two sides are not in agreement about what initial board the delta should be applied to, but that’s not too hard to do.
Why would bandwidth be a problem with a chess game between two players? What is wanted here, to get a program to fit in a small foot print, or to make it faster for an AI can make a move?
Two players and an arbitrary number of viewers, who may join in or drop off at any time. That also makes it difficult to not pass the entire board every round.
That’s the clarification I wanted. One observation though, the players need to be in real time, but the observers can experience a delay in viewing, without a critical problem. I understand the reason for limiting data transmission here. The problem is set in it’s proper form now.