A single integer N = a complete chess game

[David Wilson]

The largest known possible number of moves from a given position, including 
en passant, castling, and promotion, is 218. Supposing the actual maximum is 
not much more, it is indeed possible to use encode each move into an 8-bit 
integer representing an index into a canonical ordering of possible moves 
from each position.

If the number of possible moves is less than 256, we can do better by using 
that number as a base.

The position from which 218 moves is possible is a contrived position 
involving multiple promoted queens. Positions reached in serious 
over-the-board play do not approach that number of possible moves. I also 
suspect that there are moves that are much more likely to occur in 
over-the-board play, making Huffman encoding seem like a possible avenue for 
shrinking the game description.

----- Original Message ----- 
From: "Ralf Stephan" <ralf at ark.in-berlin.de>
To: <m at hasler.ws>
Cc: "Eric Angelini" <Eric.Angelini at kntv.be>; "SeqFan" 
<seqfan at ext.jussieu.fr>
Sent: Thursday, April 10, 2008 12:29 PM
Subject: Re: A single integer N = a complete chess game


> You wrote
>> >  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...
>>
>> it is sufficient to use the number obtained from concatenating initial
>> and final square of each move, i.e.
>> G = sum( (a.i+64b.i)*64^2i )
>> where i is the half-move, and a.i, b.i is starting / ending square
>
> You'll need additional bits for underpromotion, i.e., creating
> a rook instead of a ueen from a pawn.
>
> This scheme, in summary, will need 18 bits per move.
>
> You can do much better by creating a list of all possible
> moves from the start position, and choosing a predefined order,
> finding the move position in that list; and doing so for all
> possible positions. Now, there is a maximum of moves from any
> position, should be less than 176 (what is it exactly?).
> So, you need only 8 bits per move.
>
> Now with a theoretical maximum of 5000? moves (in practice 200
> but with the new endgame rules there's more possible) your number
> is less than 2^200, but certainly less than 2^5000 or so.
> That is, about 30 and 1500 digits, respectively.
>
> Regards,
> ralf
>
>
> -- 
> No virus found in this incoming message.
> Checked by AVG.
> Version: 7.5.519 / Virus Database: 269.22.12/1372 - Release Date: 
> 4/10/2008 5:36 PM
> 





A089218 looks to me like a wrong (because incomplete) version of A052195,
or am I missing some aspect here?

Richard