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

Mark Tilford ralphmerridew at gmail.com
Thu Apr 10 10:25:46 EDT 2008

On Thu, Apr 10, 2008 at 9:34 AM, Eric Angelini <Eric.Angelini at kntv.be> wrote:

>

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

Three methods, moving from "quick encode, bad length", "decent encode,
decent length", "unusable slow encode, minimum length".

Well, a simple method to do such would be to take 0=="00", 1="01",...
a="10", b="11", ..., A="37", ..., space="63"
Then simply concatenate all the numbers.
So Pa4, Pd5 would be 52100463521305.
It could be improved by using a base 64 encoding instead of base 100,
but length reduction wouldn't be much.

A variant on arithmetic encoding would be to start by encoding a game
as a range.
The null game is encoded as [.1,1).
For a game X, encoded as [a,b), suppose there are N legal moves (with
a special "stop game" move added), sorted in some predetermined
fashion.
The game (X + move #i) is encoded as [a + (i-1)*(b-a)/N), a + i*(b-a)/N).

To encode a game G as an integer, consider the range for G+"stop" as
[m,n). Find an integer j such that j/10^i is in [m,n). Send j.

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.

> 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

>