Author: Ratko V Tomic
Date: 12:03:49 11/03/99
Go up one level in this thread
> You can have many bishops on the board. I believe that the maximum > would be 10 bishops, with up to 9 of a single color. ... > Any scheme to number all positions must take into account any legal > board position. Otherwise it cannot be used and its value is limited This was only a sub-problem, with restrictions as Guido stated (the maximum material count, i.e. no captures or promotions have occured as yet), in a different approach to encoding. The approach is based on classifying first all positions by Material Content (MC; i.e. how many pieces of each kind are there). Then for each of the distinct MC states one can compute number of distinct positions they generate and add them up over all MC possibilities. It is easy to show that the number of distinct materal content states is always below 2^28 (that's a very rough upper limit, the exact number may be 3-4 bits lower), i.e. fewer than 28 bits are used to index MC part of the code. As a rough estimate for the upper bound on the maximum number of states one MC may have, I looked at the maximum material configuration, which from these calculations needs 133 whole bits (and this is the case Guido was discussing). So, that gives a rough upper bound on the number of positions as 133+28=161 bits. Since 28 bit is a highly non-optimized upper limit on number of MC states, and an average position will need substantially fewer bits than 133, it seems more likely that all positions will fit in the 160 bits. It would take a program, though, to go though all 10^28 MC cases and add up the numbers of positions each generates to check if that is the case (i.e. to find the actual total number of positions and identify the worst case, which might be the 32-piece MC state we were looking at, or something close to it). This encoder/decoder wouldn't need to keep a 2^28 entry MC table, but maximum about 2^14 entry table (this is a very rough upper limit) for one color. The combined color MC is produced on the fly by pairing the 2^14 entries between themselves and applying a pairing restriction that even though there could be up to 8 promotion produced extra pieces for 1 color, no more than 12 total promotion produced extra pieces can occur for the two colors. 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).
This page took 0.01 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.