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

[Otto Janko]

> Otto is correct, that Huffman like (context sensitive) encoding will 

> theoretically result in shorter (since compressed) numbers than my 

> algorithm, but you have to take into account, that these "context 

> sensitive information" has to be stored anywhere -- with the 

> number, if you want to optimize the compression for any game notation.


This is the reason why Huffman is "asymtotically" optimal. You can see the
problem in real life if you ZIP-compress very short text files - the encoded
file may become longer than the uncompressed file. But ZIP recognized this
and does not compress such files at all.

The impact of the "context sensitive information" (usually calles
"dictionary") can be minimized by using a pre-calcultated dictionary:
Analyze 1 millonn games, calculate the optimal Hufmann encoding for these,
and use the resulting dictionary for encoding. The pre-calculated dictionary
needs not to be stored in in encoded string itself (as e.g. ZIP does), it is
part of the encoder/decoder.

---

I must corrent myself: Mark's porposal


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

> possible games as follows:


is *not* optimal. There are ~64! possible chess *positions" (ok, not all of
them are legal, but this does not matter here) and much, much more possible
chess games. Therefore, a game number may have 1000 digits or more, but most
of the games can be represented shorter in the usual notation. [There is a
common name for this paradox, but I can' remember it.] The reason for that
is that Tilford-Numbering must take into account the myriads of games which
have never been played and will never been played, and must reserve encoding
space for these games. 

~ÔttÔ~



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

> From: retros-bounces at janko.at 

> [mailto:retros-bounces at janko.at] On Behalf Of Thomas Brand

> Sent: Friday, April 11, 2008 7:57 AM

> To: The Retrograde Analysis Mailing List

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

> 

> Some notes:

> 

> It's simple to include promotion into "my algorithm": just 

> add two bits 

> for the promoted piece to the end of a promotion move; this will keep 

> uniqueness unchanged.

> 

> Marks and my approach are different: I construct a unique 

> number for a 

> single game, while Mark needs such an algorithm to "generate" 

> a subset 

> of the natural numbers, which, of course is well ordered, so 

> he can map 

> a game to its index: true, that results in "shorter" numbers, but 

> requires the array of the presentation of all possible games to do so 

> (and in reverse, to map a natural number to a game).

> 

> Otto is correct, that Huffman like (context sensitive) encoding will 

> theoretically result in shorter (since compressed) numbers than my 

> algorithm, but you have to take into account, that these "context 

> sensitive information" has to be stored anywhere -- with the 

> number, if 

> you want to optimize the compression for any game notation. Or you 

> require to optimise the compression for all possible games -- 

> and than 

> your approach results in the same problems as Marks: you have to take 

> into account all possible games.

> 

> Regards, Thomas

> _______________________________________________

> Retros mailing list

> Retros at janko.at

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

>