# [Retros] A single integer N = a complete chess game

**Mark Tilford**
ralphmerridew at gmail.com

*Thu Apr 10 19:41:05 EDT 2008*

On Thu, Apr 10, 2008 at 6:54 PM, Thomas Brand <t.brand at gmx.net> wrote:

>* You need 6 bit to uniquely encode a square on a chess board (64 = 2**6
*

>* squares), e.g. 3 bit a..h, 3 bit 1..8, each 000..111 with e.g. 000 = a or 1;
*

>* 111 = h or 8, resp. in binary coding.
*

>*
*

>* To denote a chess game, sometimes it's sufficient to denote one square
*

>* (e.g. for starting a game with e4), sometimes not (e.g. for starting a game
*

>* with Sg1-f3, but not f2-f3).
*

>*
*

>* So you might encode a game with "short notation" for one ply, if
*

>* sufficient, and with "long notation" for one ply, if necessary (obviously,
*

>* this includes e.p. capture and castling, too).
*

>*
*

Don't forget promotion.

>* To mix these two different kinds of notation you might use an additional
*

>* bit (say "0" for short, "1" for long).
*

>*
*

>* Eventually two bits are sufficent to code the final result of a game, say
*

>* "10" for White win, "01" for Black win, and "00" for draw.
*

Those last two bits are unnecessary; one can determine them by

expanding the position.

>*
*

>* So a white win after start of Ruy Lopez (Spanish Opening) with "e4 e5 g1-f3
*

>* b8-c6 b5 1-0" had to be coded
*

>* 0 100011 {e4} 0 100100 {e5} 1 110000 101010 {g1-f3} 1 001111 010101 {b8-c6}
*

>* 0 001100{b5} 10 {white wins}. Its it up to you to translate it into the
*

>* corresponding decimal number presentation.
*

>*
*

>* It's easy to prove that it is decidable if a given natural number denotes a
*

>* chess game and, if so, you can re-translate this number to standard chess
*

>* game notation.
*

>*
*

>* Maybe this is the "most economical way" to map a game of chess to the
*

>* natural numbers, i.e. resulting in the "smallest number possible" for chess
*

>* notation?
*

>*
*

No: the method

-------------

For total efficiency as far as length of output goes, sort all

possible games as follows:

a) Choose a fixed order for all possible single moves. (For example,

alphabetical when the move is fully written out.)

b) A shorter game comes before a longer game

c) If two games of the same length agree up to the nth ply but differs

on the n+1st, the one whose n+1st ply is earlier according to a) comes

first.

Encode a game as the index of where it appears on the list.

--------------

Is an optimal method in that

- Every game has a unique representation

- Every number corresponds to some board

To give any one position a smaller representation, some other position

would have to get a larger representation.

The method you gave is nonoptimal in that "111111" (h1) does not

correspond to a legal game, so it's possible to give some position a

smaller number by giving it the number 63 instead.

>* Best regards,
*

>*
*

>* Thomas
*

>*
*

>*
*

>*
*

>*
*

>* >
*

>* > > -----Original Message-----
*

>* > > From: retros-bounces at janko.at [mailto:retros-bounces at janko.at] On Behalf
*

>* Of Eric Angelini
*

>* > > Sent: Thursday, April 10, 2008 3:34 PM
*

>* > > To: The Retrograde Analysis Mailing List
*

>* > > Subject: [Retros] A single integer N = a complete chess game
*

>* > >
*

>* > >
*

>* > > Hello RetroChess and Seq fans!
*

>* > > (crossposted to both groups in two separated mails)
*

>* > >
*

>* > > Since Gödel's works we know we can assignate a unique integer to
*

>* > > almost anything (a 1000 words poetry, a Rothko painting, a walk
*

>* > > of Hamish Fulton, etc.) -- anything "with an end", of course.
*

>* > >
*

>* > > [If I remember well the technique would use prime exponents:
*

>* > > N = a^2 * b^3 * c^5 * d^7 * e^11 * ... with a, b, c, d, e, ...
*

>* > > being "plys" http://en.wikipedia.org/wiki/Ply_(game_theory) ]
*

>* > >
*

>* > > What would be the most "economical way" to assign a single number
*

>* > > to a complete chess game? I guess this number would be of googol-
*

>* > > length...
*

>* > >
*

>* > > An easier (?) task would be to transform a _chess position_ into
*

>* > > a single integer (using X-FEN? http://en.wikipedia.org/wiki/X-FEN )
*

>* > >
*

>* > > But I know that the retro-content of a position is very difficult
*

>* > > to encode (e.p and castling rights, for instance) -- so the task
*

>* > > of encoding a full game into a single integer (from the starting
*

>* position onwards) might be simpler.
*

>* > >
*

>* > > Sorry if this is old hat.
*

>* > >
*

>* > > Best,
*

>* > > É.
*

>* > > _______________________________________________
*

>* > > Retros mailing list
*

>* > > Retros at janko.at
*

>* > > http://www.pairlist.net/mailman/listinfo/retros
*

>* > >
*

>* > >
*

>* >
*

>* > _______________________________________________
*

>* > Retros mailing list
*

>* > Retros at janko.at
*

>* > http://www.pairlist.net/mailman/listinfo/retros
*

>* >
*

>* >
*

>*
*

>* _______________________________________________
*

>* Retros mailing list
*

>* Retros at janko.at
*

>* http://www.pairlist.net/mailman/listinfo/retros
*

>*
*

More information about the Retros
mailing list