Author: Ratko V Tomic
Date: 12:59:26 11/03/99
Go up one level in this thread
> The code would have a fixed length part, giving the MC index, plus a > variable part corresponding to the variable number of positions > generated by the different MC states. The decoder, once it gets MC index, > can compute exactly how many distinct positions such MC produces, and > whether there may be ep or castle cases (which would use extra code > space, probably negligible, if one uses similar method suggested for > the example 2 kings + castle status in 12 bits). I should have added also that the MC part of code can be made a variable length code, as well, in order to make the overall code roughly fixed length, i.e. to reduce the lenght of the worst cases, those with the longest second part (which is the permutation code within the given MC case). A simple way would be to use fixed Huffman codes for the MC part, using the "counts of permutations for the given MC case"/"total positions" as Huffman probabilities(the "total positions" number is obtained by adding all permutation counts over all MC cases; it exceeds the number of strictly legal positions, since we don't eliminate illegal checks or positions with illegal/nonexistent predecessor, e.g. a mutual stalemate). The effect of such Huffman encoding for the MC part would be to reduce the MC part length, down from the 28 bits, for those cases where a given MC state produces unusually large number of permutations (such as the 133 bits in the 32 piece case we were talking about), and lenghten it for those cases which have small number of permutations, making thus the overall codes more uniform in length. That way, these worst MC cases would use fewer than 28 bits for the MC part, leaving thus the extra space for the permutation part of the full code. [When I get a few days of free time from my consulting work, I'll write a program to go thorugh all of the 2^28 MC candidate cases (that's only about 268 millions) and clean up the simplest of the material counts illegalities, then compute number of distinct permutations for each of the psudo-legal MC cases, then compute Huffman codes from these permutation counts, and then show the distribution of the code lengths, the total pseudo-legal chess positions and the MC/s for the longest full code length case/s. If there is enough time to refine the program, and run time doesn't turn into astronomical, it would be nice to also identify in this context the ep and the castle candidate positions and at least calculate the code space for them and see how they affect the total positions and the worst case.]
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.