Chess encoding - Draft | Luca Blanchi

We consider the problem of encoding moves, positions, games, and trees or graphs of chess games, focusing first on storage efficiency and secondarily on simplicity and read speed.

Some considerations follow.

Games as sequences of moves

A game can be encoded as the sequence of its individual positions. It is also possible, however, to store only the list of individual moves, so that the game and the positions that compose it can be reconstructed. An efficient move encoding becomes an efficient game encoding.

Move Encoding

Move encoding with origin and destination

We can define a move as the piece to move, or perhaps better its square, and the destination square. This still holds for castling: castling can be encoded by moving the king two squares to its destination, making the rook's follow-up move implicit. Selecting one of the 64 squares, identified by 6 bits, as the origin and one as the destination identifies any move in 12 bits.

A second important observation is that many moves are illegal; in particular, the king will always have many illegal moves. These can be used to represent states that are more particular than a standard move, especially resignation or a draw.

For example, a draw can be represented by one king capturing the other. Resignation can instead be represented by moving the king to an inaccessible corner, using the color of the destination square to indicate the resigning player, since such an illegal corner will always exist.

Another creative use of illegal moves is pawn promotion: we can indicate only the destination file, and use ranks 1, 2, 3, 4 for White, and 8, 7, 6, 5 for Black, to indicate promotion respectively to queen, rook, bishop, knight.

The encoding can be made more efficient if we know whose turn it is: list the side-to-move pieces in lexicographic order, select one with 4 bits, at most 16 pieces, and use 6 bits for the destination square.

This identifies a move in 10 bits, or 11 if the player must also be specified, and therefore encodes a game in 10 bits per half-move: a 40-move game would require 100 bytes.

Move encoding by enumeration

A lower weight can be achieved if, instead of using 4 bits to identify a piece, we dynamically allocate only as many bits as are needed to identify one of the pieces on the board that has legal moves. For example, if only 8 pieces can move, only the first 3 bits identify the piece, giving a 9-bit move. A forced move weighs 7 bits.

Continuing in this direction, we can also order lexicographically the possible moves that a piece can make after it has been identified, allocating the necessary bits dynamically, adding 3 moves for draw and resignations, and adding moves for the different pawn promotions. The maximum number of moves for a piece is 27, for a centralized queen, so at most 5 bits are needed.

A move, knowing whose turn it is, is therefore represented by at most 9 bits: 4 to choose the piece, 5 to move it. In the minimum case, a forced move, no bits are needed to identify the piece, and only 2 bits are used to make the move or choose a draw or resignation.

These two tricks reduce the storage used by the encoding, but they require reading the current position in order to decode the selected piece, whose possible moves must be calculated unless pieces with no legal moves are excluded, and the move that was made.

Following this path, we can compute all possible moves in a position, list them lexicographically after listing the pieces lexicographically, and add draw and resignations. We can then allocate only the bits needed to cover the available moves. A storage improvement can be achieved only on average if we introduce the idea that some moves are more plausible than others, or for games with an encoding that is not move-by-move.

Encoding geometrically admissible moves [June 13]

A middle path would be to consider only the moves that are geometrically admissible according to the piece type and its position on the board, ignoring the other pieces in play and the chess rules.

For example, a queen has at most 27 positions it can move to if it is centralized. This is simpler than computing the legal moves, which requires a chess engine and considerations about obstructions by the other pieces on the board, as well as checks.

We could therefore choose the piece to move with at most 4 bits, and then the geometrically sensible move with at most 5 bits, obtaining a reasonably clean encoding up to 9 bits.

We can also enumerate all geometrically plausible actions by listing the pieces in lexicographic order, and then, for each piece, enumerating its geometrically plausible moves according to type and position, treating resignations and draws as extra actions.

In this way we obtain an encoding that does not require a complete chess engine for encoding and decoding, and that in most cases can compress the move into 1 byte or less, requiring 9 bits only in rare cases: those in which there are more than 255 geometrically plausible moves, or 252 if space is left for special moves, essentially cases with many promoted queens.

Position Encoding

Combinatorial encoding of a legal position

We can encode a legal position as follows.

1 bit allocated to determine the side to move.
6 bits + 6 bits for the kings' positions.

Then we observe that a player has 15 other pieces, of 6 types: pawn, knight, bishop, rook, queen, or captured piece, in various configurations, also accounting for pawn promotion. To exploit the fungibility of equivalent pieces, we use bits to determine the configuration with the combinatorial stars-and-bars technique: ****|***|***|*||****. The total number of combinations is 20!/(15!*5!), and requires 14 bits per player to be represented, with standard decoding algorithms.

For each uncaptured piece, we can identify the position with 6 bits, selecting pieces in the category order chosen in the previous step. Since pieces of the same type are fungible, however, we can improve efficiency by allocating only the bits needed to identify the n-tuple among the remaining available squares, decoding it with standard algorithms such as the combinadic. In fact, we can also compress this sequence of numbers with a mixed-radix method to save bits for each tuple.

Finally, we can allocate the bits needed to identify which plausible castling rights are available, up to 4 bits, and which plausible en-passant states are available, up to 3 bits to cover up to 6 cases.

The optimal case, with only 2 kings, uses 1 + 6 + 6 + 14 + 14 = 41 bits. According to ChatGPT: worst case 189 bits, starting case 175 bits.

If a fixed size is desired, one can use 1 + 4 + 3 bits for turn, castling, and en passant; 14 + 14 for the piece configurations; 6 + 6 for the kings' positions; and 6*30 for the positions of the pieces, for a total of 228. Alternatively, allocate 189 bits and waste the unnecessary ones at the tail.

Encoding illegal positions

For positions with illegal piece combinations, we can apply a similar strategy. Assuming there are still 2 kings, we can determine the piece combination for both players as a choice of 62 pieces among 11 types: 5 white pieces, 5 black pieces, and captured pieces. Then we can determine the positions of the n-tuples and add bits for turn, castling, and en passant. According to ChatGPT: worst case 249 bits, starting case 186 bits.

Second take on encoding pseudo-legal positions [June 13]

We have effectively split the problem of encoding a position into metadata encoding plus board-state encoding.

For the metadata: turn, castling, and en passant, we have seen that 1 to 8 bits of information are enough for the encoding.

For the board state, the method discussed above is conceptually divided into determining the types of pieces on the board, and placing them while exploiting fungibility through the combinadic.

In fact, there is no reason to place the kings immediately: it is logically and practically better to relegate this to the later phase in which all positions are identified.

Most of the optimization we can still obtain remains in the phase that determines the piece types: the stars-and-bars method allows illegal configurations, such as 15 queens. If we consider that each player has at most eight pawns, and that compared with the starting count of 2 rooks, 2 bishops, 2 knights, and 1 queen, extra pieces can exist only if at least that many pawns are missing due to promotion, far fewer legal configurations remain.

We could enumerate only those configurations, at worst with precomputed lookup tables, although it would be nice to find a clean encoding for this tranche, saving bits.

Then, during the piece-placement phase, a further useful optimization is to place the pawns immediately, considering that only 48 squares can contain pawns, not the first and last ranks.

Other optimizations are possible, such as mixed radix between metadata, type configuration, and placement, and by noticing that some piece configurations are impossible. For example, pawns on a2, a3, and b2 are impossible; doubled pawns without captures are impossible.

With enough optimizations of this kind, the starting case should reach about 153 bits, the best case 27 bits, and the worst case around 185 bits, potentially also guaranteeing 23 bytes or less per position.

Ci poniamo il problema di codificare mosse, posizioni, partite, e alberi o grafi di partite di scacchi, curando in primo luogo l'efficienza di storage, e secondariamente semplicità e velocità di lettura.

Seguono alcune considerazioni.

Partite come sequenze di mosse

Una partita può essere codificata tramite la sequenza delle singole posizioni; è anche però possibile riportare solamente l'elenco delle singole mosse, in modo che la partita e le posizioni che la compongono possano essere ricostruite. Una codifica efficiente per le mosse diventa una codifica efficiente per le partite.

Encoding di mosse

Encoding mosse con partenza e destinazione

Notiamo che possiamo definire una mossa come il pezzo da muovere, o forse meglio la sua casella, e la casella di destinazione; questo è vero notando che l'arrocco può essere codificato muovendo il re di 2 caselle, fino alla sua destinazione, rendendo ovvio come la torre debba seguire. Naturalmente selezionando una delle 64 caselle, individuata con 6 bit, in partenza, e una in arrivo, individueremo una qualsiasi mossa con 12 bit.

Una seconda osservazione importante è che molte mosse sono illegali; in particolare, il re avrà sempre una moltitudine di mosse illegali. Queste possono essere usate per rappresentare stati più particolari di una mossa standard, in particolare una resa o una patta.

Possiamo per esempio indicare una patta con la cattura di un re da parte dell'altro re. Possiamo invece muovere il re in un corner inaccessibile, per indicare la resa del giocatore con il colore della casella di destinazione, dato che ci sarà sempre un tale corner illegale.

Un altro uso creativo delle mosse illegali è la promozione di pedone: possiamo indicare solo la colonna di destinazione, e utilizzare la traversa 1, 2, 3, 4 per il bianco, e 8, 7, 6, 5 per il nero, per indicare una promozione rispettivamente a regina, torre, alfiere, cavallo.

Possiamo rendere l'encoding più efficiente se sappiamo di chi è il turno: possiamo elencare i pezzi del giocatore di turno in ordine lessicografico e selezionarne uno usando 4 bit, massimo 16 pezzi, e usare 6 bit per la casella di destinazione.

Questo garantisce di individuare una mossa con 10 bit, 11 se si vuole specificare il giocatore, e di conseguenza di codificare una partita con 10 bit per semi-mossa: per una partita di 40 mosse basteranno 100 byte.

Encoding mosse tramite enumerazione

Un peso inferiore si può ottenere se, invece di utilizzare 4 bit per individuare un pezzo, se ne allocano dinamicamente tanti quanti sono necessari per individuare uno dei pezzi presenti nella scacchiera con mosse valide. Per esempio, se solo 8 pezzi possono muoversi, decreteremo che solo i primi 3 bit individueranno il pezzo, individuando una mossa con 9 bit. Una mossa obbligata peserà 7 bit.

Proseguendo in questa direzione, ordiniamo in ordine lessicografico anche le possibili mosse che un pezzo può fare dopo essere stato individuato, allocando dinamicamente i bit necessari, aggiungendo 3 mosse per patta e rese, e aggiungendo mosse per le diverse promozioni di pedone. Il numero massimo di mosse per un pezzo è 27, per una regina centralizzata, per cui saranno necessari al massimo 5 bit.

Una mossa, sapendo chi è di turno, sarà rappresentata quindi al massimo da 9 bit: 4 per scegliere il pezzo, 5 per muovere. Nel caso minimo, una mossa obbligata, non servono bit per individuare il pezzo, e useremo solo 2 bit per fare la mossa, o scegliere una patta o una resa.

Questi due accorgimenti riducono lo spazio occupato dalla codifica, ma richiedono di leggere la posizione attuale per poter decodificare il pezzo selezionato, per il quale vanno calcolate tutte le mosse possibili, a meno di non voler escludere i pezzi che non possono muovere, e la mossa eseguita.

Seguendo questa pista, possiamo calcolare tutte le mosse possibili in una posizione, elencarle in ordine lessicografico dopo aver elencato i pezzi in ordine lessicografico, e aggiungere patta e rese. Possiamo poi allocare i soli bit necessari a coprire le mosse disponibili. Un miglioramento in termini di storage si può ottenere solo in termini di media se si introduce il concetto di mossa più plausibile di altre, o per le partite con una codifica che non sia mossa per mossa.

Encoding mosse geometricamente ammesse [13 Giugno]

Una via di mezzo sarebbe considerare solo le mosse geometricamente ammesse in base alla tipologia del pezzo e alla posizione nella board, ignorando gli altri pezzi in gioco e le regole scacchistiche.

Ad esempio, una regina avrà al più 27 posizioni in cui muovere se è centralizzata. Questo è più semplice che calcolare le mosse ammesse, che richiede un engine di scacchi e considerazioni su ostruzioni da parte degli altri pezzi della scacchiera, oltre che sugli scacchi.

Potremmo dunque scegliere il pezzo da muovere con al più 4 bit, e poi la mossa geometricamente sensata con al più 5 bit, ottenendo un encoding discretamente pulito fino a 9 bit.

Possiamo però anche enumerare tutte le azioni geometricamente plausibili enumerando i pezzi in ordine lessicografico, ed enumerando poi per ciascuno le mosse geometricamente plausibili in base a tipologia e posizione, considerando rese e pareggi come azioni extra.

In questo modo otteniamo un encoding che non richiede un completo engine scacchistico per la codifica e decodifica, e che nella maggior parte dei casi riesce a comprimere la mossa in 1 byte o meno, richiedendo 9 bit solo in rari casi: quelli in cui le mosse geometricamente plausibili sono più di 255, o 252 per lasciare spazio alle mosse speciali, sostanzialmente casi con molte promozioni a regine.

Encoding di posizioni

Encoding combinatorio di una posizione legale

Possiamo codificare una posizione legale nel modo che segue.

1 bit allocato per determinare il giocatore di turno.
6 bit + 6 bit per le posizioni dei re.

Dopodiché, osserviamo che un giocatore avrà 15 altri pezzi, di 6 tipologie: pedone, cavallo, alfiere, torre, regina, o pezzo catturato, in varie configurazioni, considerando anche la promozione di pedone. Al fine di fare leva sulla fungibilità di pezzi equivalenti, utilizziamo dei bit per determinare la configurazione con la tecnica combinatoria delle stelle e barre: ****|***|***|*||****. Le combinazioni totali sono 20!/(15!*5!), e richiedono 14 bit per giocatore per essere rappresentate, con algoritmi standard di decodifica.

Per ciascuno dei pezzi non catturati, possiamo individuare la posizione con 6 bit, selezionandoli nell'ordine delle categorie selezionate allo step precedente. Essendo però pezzi della stessa tipologia fungibili, possiamo migliorare l'efficienza allocando solo i bit necessari a individuare l'n-upla tra le caselle rimaste disponibili, decodificandolo con algoritmi standard come il combinadic. Possiamo in realtà anche comprimere questa sequenza di numeri con metodo mixed radix per leakare bit per ciascuna tupla.

Possiamo infine allocare i bit necessari a individuare quali arrocchi plausibili sono possibili, fino a 4 bit, e quali en-passant plausibili sono possibili, fino a 3 bit, per coprire fino a 6 casi.

Il caso ottimo è con solo 2 re, e occupa 1 + 6 + 6 + 14 + 14 = 41 bit. Secondo ChatGPT: worst case 189 bit, starting case 175 bit.

Se si vuole una dimensione fissa, è possibile 1 + 4 + 3 bit per turno, arrocco, en passant, 14 + 14 per la configurazione dei pezzi, 6 + 6 per la posizione dei re, 6*30 per le posizioni dei pezzi, per un totale di 228; oppure allocare 189 bit sprecando quelli non necessari in coda.

Encoding di posizioni illegali

Per posizioni con combinazioni di pezzi illegali, possiamo applicare una strategia simile. Assumendo comunque 2 re, possiamo determinare la combinazione di pezzi di entrambi i giocatori come scelta di 62 pezzi di 11 tipologie, cioè 5 pezzi bianchi, 5 neri, catturati. Possiamo poi determinare la posizione delle n-uple, e aggiungere bit per turno, arrocco, en-passant. Secondo ChatGPT: worst case 249 bit, starting case 186 bit.

Second take su encoding di posizioni pseudo-legali [13 Giugno]

Abbiamo effettivamente suddiviso il problema dell'encoding di una posizione in encoding metadati + encoding dello stato della board.

Per i metadati turno, arrocco, en-passant, abbiamo visto che bastano da 1 a 8 bit di informazione per l'encoding.

Per lo stato della board, il metodo trattato sopra si divide concettualmente in determinazione della tipologia dei pezzi nella scacchiera, e posizionamento che sfrutta la fungibilità tramite combinadic.

In effetti non c'è motivo di posizionare i re subito: è logicamente e praticamente meglio relegarlo alla fase successiva in cui vengono individuate tutte le posizioni.

La maggior parte dell'ottimizzazione che possiamo ancora ottenere rimane nella fase di determinazione della tipologia dei pezzi: il metodo stars and bars permette configurazioni illegali, come 15 regine. Se consideriamo che ciascun giocatore abbia al più otto pedoni, e che rispetto al numero di partenza di 2 torri, 2 alfieri, 2 cavalli, 1 regina, se ne possano avere in eccesso solo se mancano almeno quei pedoni, per promozione, risultano molte meno configurazioni legali.

Potremmo enumerare solo quelle configurazioni, alla peggio con delle lookup table precalcolate, ma sarebbe carino trovare un encoding pulito per questa tranche, risparmiando dei bit.

Dopodiché, nella fase di posizionamento dei pezzi, è opportuna come ulteriore ottimizzazione il posizionare subito i pedoni, considerando che solo 48 caselle possono avere dei pedoni, non la prima e ultima traversa.

Sono possibili altre ottimizzazioni come mixed radix tra metadati-tipologia-posizionamento, e notare che alcune configurazioni di pezzi sono impossibili. Ad esempio, sono impossibili pedoni in a2, a3, b2; sono impossibili impedonature senza catture.

Con sufficienti ottimizzazioni di questo tipo si dovrebbe raggiungere uno starting case a circa 153 bit, un best case a 27 bit, e un worst case intorno ai 185 bit, e potenzialmente anche garantire 23 byte o meno per posizione.