Author: KarinsDad
Date: 23:38:31 04/22/00
Go up one level in this thread
On April 23, 2000 at 01:47:12, blass uri wrote: >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 Of course you can, but you can also have 26 or 24 or 14. What if you only had 5 pawn promotions? Where would your distribution be then? Is it the a and b pawns promoting along with the f pawn? How would you know? > >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. So what is your point? That you can save 1 bit? Maybe 2 (which I doubt)? > >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 Yes, you are correct. We need 63 bits. But that saves all of 1 bit. Not worth creating an equation for. KarinsDad :)
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.