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

[Mark Tilford]

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

>