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

[Mark Tilford]

On Thu, Apr 10, 2008 at 6:54 PM, Thomas Brand <t.brand at gmx.net> wrote:

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

>


Don't forget promotion.


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


Those last two bits are unnecessary; one can determine them by
expanding the position.


>

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

>


No:  the method
-------------
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.
--------------

Is an optimal method in that
- Every game has a unique representation
- Every number corresponds to some board

To give any one position a smaller representation, some other position
would have to get a larger representation.


The method you gave is nonoptimal in that "111111" (h1) does not
correspond to a legal game, so it's possible to give some position a
smaller number by giving it the number 63 instead.



>  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

> >

> >

>

>  _______________________________________________

>  Retros mailing list

>  Retros at janko.at

>  http://www.pairlist.net/mailman/listinfo/retros

>