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

[Otto Janko]

Hi ALL,

A game is encoded by its move list, which is usally 2-4 letters per half
move. This move list can be compressed by various algorithms, and the "most
economical way" in terms of the length of the encoded string is the best
compression algorithm (the most economical way in terms of time necessary to
compress the move list is no compression at all).

Compression usually leads to a bit stream, and any bitstream can be
interpreted as (binary) integer. This integer is "the most economical way"
to encode a complete game in a single integer.

It does not matter which notation is used as input for the move list,
because "the most economical way" will remove any redundancy.

IIRC it has been proven that Huffman is asymptotically optimal, and
therefore the bitstream resulting from Huffman encoding is the "most
economical representation" of a chess game.

Best Regards,

- Otto Janko [mailto:otto at janko.at] [http://www.janko.at]
-- Those who desire to give up freedom in order to gain security, 
- will not have, nor do they deserve, either one. [Benjamin Franklin]





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

>