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

[Otto Janko]

> For total efficiency as far as length of output goes, sort all

> possible games as follows:


This is theoretically optimal, but practically impossible und therefore
useless in real life.

Regarding all the encoding proposals in this thread: 

Please be aware of the fact that any encoding that uses a fixed number of
bits to represent something (a letter, a piece, a square, a move, etc.) is
not optimal because it does not take intoaccount the frequency a piece moves
or a square is used. For example, you can use a long representation for
castling, because castling is infrequent be definition, or a long
representation for e.p. - but you should use a short representation for the
knight because the knight moves frequently.

An asymptotic optimal algorithm therefore counts the frequency of all needed
representations in a first pass, calculates the optimal representation in a
second pass and then encodes the game in a third pass. For example, if the
pawn a2 never moves in the game, then it is not neceesare to reserve
encoding space for pawn a1 moves. (And in many games many pieces never
move!)

~ÔttÔ~



> -----Original Message-----

> From: retros-bounces at janko.at 

> [mailto:retros-bounces at janko.at] On Behalf Of Mark Tilford

> Sent: Friday, April 11, 2008 1:41 AM

> To: The Retrograde Analysis Mailing List

> Subject: Re: [Retros] A single integer N = a complete chess game

> 

> 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

> >

> _______________________________________________

> Retros mailing list

> Retros at janko.at

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

>