[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
>
More information about the Retros
mailing list