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

[Thomas Brand]

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

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.

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?

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

>