Author: blass uri
Date: 22:47:12 04/22/00
Go up one level in this thread
On April 22, 2000 at 22:06:22, KarinsDad wrote: >On April 22, 2000 at 19:30:50, blass uri wrote: > >>On April 22, 2000 at 17:41:35, Heiner Marxen wrote: >> >>>On April 22, 2000 at 14:47:08, Tom Kerrigan wrote: >>> >>>>On April 22, 2000 at 13:28:39, KarinsDad wrote: >>>> >>>>>On April 22, 2000 at 13:25:03, Tom Kerrigan wrote: >>>>> >>>>>[snip] >>>>>> >>>>>>Notice my idea was to use Huffman encoding for the bitboard, and not the pieces. >>>>>> >>>>>>-Tom >>>>> >>>>> >>>>>How so? Please elaborate. >>>>> >>>>>KarinsDad :) >>>> >>>>I doubt it would be possible to do a very good job compressing the pieces (4 >>>>bits ea.) themselves, but I think the bitboard should be fairly compressable. I >>>>suspect that most bitboards have strings of 0's scattered throughout them. >>> >>>If you mean that bitboard which distinguishes empty from nonempty positions, >>>then no: try to do the math yourself (at first I did not believe it myself): >>>there are at least 2 and at most 32 of the 64 bits set to "non-empty". >>>Sum choose(2,64) upto choose(32,64) and compare to 2^64, and you will see, >>>that you need a little bit more than 63 bits to code all possibilities, >>>regardless of how clever you do it. >>> >>>Heiner >> >>You are right if you assume that all the location configurations of 2-32 pieces >>are legal and have the same probability but not all the location configurations >>of 2-32 pieces are legal >> >>For example: >>If there are 32 pieces you must have at least 2 of them in every file >>because there is one white pawn and one black pawns in every file. >>If there are 31 pieces you must have at least 2 of them in at least 6 files. >> >>There are many configurations with probability 0 and I think that you can save >>at least one bit even if you assume that all the legal configurations have the >>same probability. >> >>Uri > >I agree with Heiner. That was why I asked Tom how to do this. What if you have >12 pawn promotions and 26 pieces on the board. Which files are they on? How does >this affect your probabilities? > >KarinsDad :) You can by 4 captures pawnxpawn (axb,cxd,exf gxh) have 28 pieces on the board and 12 pawns promotions I do not see a simple idea to know the probabilities about these 28 pieces but it does not change the fact that the probabilities are not the same so it is theoretically possible to use it to save space. practically if you sum choose(2,64) up to choose(28,64) and add part of choose(29,64)+part of choose(30,64)+part of choose(31,64)+less than half of choose(32,64) you get less then 2^63. I think that you get less than half of choose(32,64) because the probability to have less than 2 pawns in the a file is almost 7/64 It was exactly 7/64 if the number of pawns in the a files was binomical distribution with 6 and .5 and it is not binomical distribution only because of the fact that the after we know that there is a pawn at a2 the probability to have a pawn at another square is smaller but the difference is not big. If you assume probability 0.9 for more thanone pawn in the a file then something like 0.9^8 is the probability to have the same thing in all the files and it is even smaller than 0.44 I did not calculate the probability but I guess that it is smaller than 0.5 but even if I am wrong and it is slightly bigger the fact that I have less than choose(31,64) and less than choose(30,64) may compensate for it so I guess we need 63 bits and not 64 bits if we assume equal probability for all location configurations. Uri
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.