Talk:Board representation (computer chess)

Old talk

I don't buy the foll: By use of a jump table, adding the piece value to the program counter can go directly to the code to generate moves for this type of piece on this square. Although the program is longer than for a conventional move generation methods, no checks for the edge of the board are required, and no moves off the board are considered, increasing move generation speed. Modern CPU caches allow code relevant to the current position to be cached, giving move generation times of a few clock cycles per position. —Preceding unsigned comment added by [[User:{{{1}}}|{{{1}}}]] ([[User talk:{{{1}}}|talk]] • [[Special:Contributions/{{{1}}}|contribs]])

What don't you buy exactly? Each piece is checked separately with code like this (on the ARM):

• ANDS R0, Rmask, Rn, LSL #4*(column-1)
• BNE piece_found_on_square_row_column

(this is written out 64 times, once for each square, with early exit tests for Rn=0)

Rmask = 15<<28

n = row number (using registers R1 to R8)

column is in the range 1-8.

The destination for the BNE is:

.piece_in_R0_found_on_square_row_column

ADD table, base, #row*8+column

LDR PC, [table, R0, LSR #26]

The destination branch caused by the final LDR is to a piece of code which knows which piece has been found (which is also in R0), whether it is black or white (sign bit from ANDS) and what square it is (table offset is to this square). All it has to do is generate the moves for a known piece in a known position. As the board is stored in registers, this only takes a few cycles too, but that's another story. Stephen B Streater 17:39, 19 May 2006 (UTC)

I buy most of it, and in fact I've seen it done that way, but I don't buy the part about "a few clock cycles per position". And in fact, the point about code caching is pretty irrelevant - even without a switch statement (which is exactly what is beign described) other schemes can easily work with cached instructions. 64.174.34.250 17:55, 20 April 2007 (UTC)

Sources for opening paragraph

I would LOVE to have sources for defining a chess position or state from a qualified source. —Preceding unsigned comment added by Fulldecent (talk • contribs) 23:43, 11 May 2010 (UTC)

I think the opening paragraph is different now, but to answer your concern - the elements of a chess position are either self-evident, i.e. a board with pieces on it, or they follow directly from the rules of chess. Certain state, like the player on move, castling privileges, enpassant capture and 50-move rule are invisible state that depend on the history of the game, so must be abstracted and explicitly stated. A source for the rules of the game can be any book on chess; the final arbitor would be the FIDE Laws of Chess Handbook. Sbalfour (talk) 13:30, 10 May 2019 (UTC)

Why 12x12 array?

This concerns the Array Based section. I see no way using a 12x12 array could possibly be beneficial. Perhaps my problem is that I don't understand why checking that a "move is on the board" is expensive. Seems like that should be a very straight forward computation. I think this deserves clarification, but I'm not sure how to do that... --Danielx (talk) 08:53, 7 March 2011 (UTC)

The reason is that the over sized array allows all possible moves to be enumerated without checking each one first to see if it is off the board. This removes what in effect are a couple of array bounds checks for the row and column of each potential move generated. It is always necessary to look at the square you are attempting to move to since you can't capture a piece of your own color, so marking the squares that are off the board to avoid row and column checks saves work. The idea is very similar to that of a sentinel value. In tight loops these can achieve savings of nearly 50%. The article should explain this better. If someone can find a good source we could use it to improve the explanation. Quale (talk) 04:24, 8 March 2011 (UTC)

And 10x10 would suffice, except for knight moves, which is why 12x12 is used. Bubba73 ^{You talkin' to me?} 20:23, 12 January 2012 (UTC)

And actually 10x12 is sufficient as the sentinel squares off the ends of the rows on left and right can overlap. I added an ancient reference to this technique which was widely understood in 1977. A while later I realized that this is explained in a fair amount of detail on the Hyatt web page. That page has been in the references for the article for a long time, but it wasn't cited directly for that claim. The Hyatt page could provide a reference for a few other claims in the article as well. Quale (talk) 09:26, 15 January 2012 (UTC)

missing representation

If you want to be complete you should include the graphical representation:

In chess playing programs, a visual representation of the board can be presented to the user via the screen or printed off. This representation is considered the most user friendly, but cannot be used for calculating the next move. Some programs feature a 3D visual representation.

I would add this myself, but would want to hear "that is a good idea" first. 69.168.144.138 (talk) 01:24, 24 September 2011 (UTC)

Rename to Board representaion (computer chess)?

What do you think about renaming this article as above --178.208.207.204 (talk) 20:00, 12 January 2012 (UTC)

I think that's an excellent idea. Quale (talk) 09:28, 15 January 2012 (UTC)

Hodge-podge

We've got a hodge-podge of concepts thrown into this article: data structures for representing board positions in computer automatons that play chess; UI formats (FEN) for recording and communicating game positions; and data compression techniques (Huffman) for digitizing chess positions. FEN is covered adequately in the Chess article - maybe all we need here is a hatnote to that. Digitizing chess positions isn't a significantly involved issue that it couldn't be relegated to a footnote in the Huffman coding article; it's certainly not enough at this point for it's own article, but it's kind of a wart here. I'm going to be bold and restructure this article before I do any work on it. Sbalfour (talk) 17:54, 17 September 2019 (UTC)

Orphan subsection moved here

Huffman encodings

Inspired by Huffman coding, chess positions can be represented with bit patterns in such a way that the more common board elements (empty squares and pawns) are stored using fewer bits than the less common board elements:

Empty square = 0
Pawn         = 10c
Bishop       = 1100c
Knight       = 1101c
Rook         = 1110c
Queen        = 11110c
King         = 11111c

where c is a bit representing the color of the piece (1 = LIGHT, 0 = DARK).

Additional bits are needed for:
50-move rule (7 bits)
en-passant column (3 bits)
color to move (1 bit)
castling rights (4 bits).

For the fifty-move rule, a number representing one of 101 possibilities is needed: a pawn was just moved or a piece just captured, a pawn was moved or a piece was captured 1..99 moves ago, or a pawn was moved or a piece captured 100 or more moves ago. This fits in 7 bits.

Any board may have a maximum of 5 seemingly en-passant-capturable pawns. Thus a number representing one of 6 possibilities is needed. This fits in 3 bits and is only needed if the board appears to allow an en passant.

Trailing empty squares can be omitted. If the remaining last piece is a king, it can by definition be omitted without loss of information, saving six more bits in some cases. Castling rights need be stored if the board appears to allow such castling.

With the above, a complete board state can be represented in a maximum of 204 bits, and often much less.

Huffman encodings are fairly CPU intensive, in comparison to other board representations which seek to minimize required processor and memory cycles. However, the small size of the final representation makes this approach well suited to storage of long-term knowledge, for instance in storing positions in an opening book, where minimizing the board representation's size is more important than minimizing CPU cycles. Huffman encoded boards are also sometimes used in transposition tables for shallow entries.

Huffman fine-tuning

An even more compact variant sacrifices the two to four-bit representation of as many empty squares for encoding two to nine empty squares in five bits. If another zero follows, the number is extended by two bits, allowing ten to 41 empty squares to be encoded in eight bits.

One empty square               = 0
nnn+2 (2-9) empty squares      = 00nnn
nnnnn+10 (10-41) empty squares = 00nnn0nn

or

nnnn+10 (10-25) empty squares  = 00nnn0n

For up to 41-length gaps, like the initial or end game boards, this saves up to 33 bits. For all sparse boards where there are pieces or pawns at near nine-square intervals or much longer gaps, there are also nice savings, e.g. 16 bits for four gaps of length nine. This is offset by the extra bits for short gaps. To always have the optimal encoding, one extra bit can mark whether straightforward or compact empty square encoding is used.

In addition the coordinates of the kings can be stored and their fields ignored in the bit sequence instead. This also takes 6 bits each. But the queen can then be coded in five bits. And gaps to the right and left can then be coalesced, making for one longer gap which is often a candidate for better compacting.

A set castling bit implies the position of a rook and the king, and of the 2^nd rook for the other bit of the same color. So for one to four set castling bits, this allows taking two to six figures and their fields out of the coding. This saves 12 to 32 bits or even more if empty ranges on either side of a king can be coalesced.

The color-to-move bit need not be part of the encoding, instead the stored value can indicate for which color (or both) a move is stored. Along with the two bits guaranteed to be saved with the above king positions, this means the encoding will never be more than 24 bytes long, which fits nicely with 32 or 64 bit architectures.

Four extra bits can store the number of pieces of the first color encountered. After the last piece of that color, the color bit can be skipped. For the initial boards, this saves 12 bits. Alternately or additionally, when the maximal possible number of one piece of the first color has been stored, i.e. eight black pawns or one white king, all further pawns, kings, etc. must be of the other color and don't require the color bit.

Another extra bit appears when the number of pieces of the first color is eight or less. It can mark the fact that no pawns are left. In this case the first bit of all pieces can be skipped:

Bishop       = 100c
Knight       = 101c
Rook         = 110c
Queen        = 1110c
King         = 1111c

Huffman multi-table approach

Additionally you can consider that for each rook there are 3 possibilities related to its home square: it has left it or it is there, either with or without castling right. When combining this for all rooks, that creates 81 different board categories, going from those with all rooks being home with castling rights, to none being home. If you store each category in a separate table, that table holds implicit information about rooks and castling rights, i.e. you only need to encode those rooks in those tables which mean it is not home. Moreover, in 25 of these categories, on each side at least one rook has its castling right, meaning that the king's position is implicitly known and need not be encoded either. And if the king's position is implicit, the queen's last bit is not needed or where both rooks are home, its shorter bit sequence can be used for the queen.

This means that for the nine tables with both rooks home, and at least one on each side having castling rights, you always save 38 bits (20 bits for four rooks, 12 bits for two kings and 2 bits for the queens and, as in all cases, 4 bits for the castling rights). At the other extreme, with no rooks home, you only save the 4 castling bits. So the gains are much higher for an opening data base than for end games.

(seems very tricky and doesn't work in case of rook promotion. Coding castle rights with the two kings positions (3612 possibilities without castle + 329 with castle => 12 bits) is safer)

References