Author: Eugene Nalimov
Date: 22:52:39 05/14/99
Go up one level in this thread
Simple example: imagine that you have 2 different values, each in the range 0..21. If you'll try to encode each of them separately, you'll end up with 2 5-bit values, so total will be 10 bits. Now, encode them as (value1)*22 + value2. You'll end up with value that is in the range 0..483, and you'll need 9 bits to encode it. Back to the original problem: there are 3812 legal placements of both king on the board. Now, if we can find other term that use not full interval [0..power of 2-1], maybe we can combine them and use less bits for that combination than sum of bits necessary for storing each of them separately. (I myself see that the phrase is not English, but cannot formulate it better). For example, counter that is necessary for 50 moves rule is in the range [0..99]. Not enough to save whole bit. Third value is necessary. Eugene On May 15, 1999 at 01:11:55, KarinsDad wrote: >On May 14, 1999 at 20:36:24, Eugene Nalimov wrote: > >>Ok. Why there are 14 possible configurations when EP is possible: >> >>There are 7 configurations when left EP capture is possible. >>There are 7 configurations when right EP capture is possible. >>If both EP captures are possible, use left one for encoding; right pawn will be >>encoding using usual board representation. If you prefer, you can add those >>configurations to the previous ones - then you'll end with 20 configurations >>instead of 14, so you'll use more space in the header, but less in the board >>when dual EP capture is possible. Will it be saving or not depends on the >>percentage of the positions when that's possible. > >Ok, this will work. So, the result is: > >0 EP save 3 bits (-3 bits in header) >1 EP save 8 bits (+1 bit in header, - 9 bits in squares) >2 EP save 8 bits (same as 1 EP since the other pawn had to be in the square >anyway) > >Cool! > >> >>About placing of the kings: there are 3812 legal combinations of the placing of >>the kings on the empty board. Unfortunately, you cannot save the bit in the >>general case. But you can save it, if you'll find similar 'underusage' of some >>other value (e.g. 14 instead of 16, or 20 instead of 32). Then you can combine >>both those values using multiplication instead of shift. > >3812 sounds like 12 bits to me. I do not understand the rest of your discussion >here on underusage and multiplication (I think you will have to spell it out for >me since I do not understand your terms), however, my quadrant solution is 12 >bits most of the time and 11 bits occassionally (when both kings are in the same >quadrant and the first king is in one of the central 4 squares of the quadrant >and the second king cannot castle either). This is 7 remaining squares * 4 first >king in center of quadrant * 4 quadrants = 112 out of the 3812 cases (a slim >amount I know, but I cannot think of a way to make it a larger number of cases >this late at night). > >See below on other king stuff. > >> >>Ok, I'll stop that thread. Back to my work... >> >>Eugene >> >>On May 14, 1999 at 20:22:04, KarinsDad wrote: >> >>>On May 14, 1999 at 19:56:51, Eugene Nalimov wrote: >>> >>>>On May 14, 1999 at 19:24:58, KarinsDad wrote: >>>> >>>>>I didn't look at the original structure when I wrote this last message. >>>>> >>>>>The savings would be 3 bits not 4 in the structure, so the overall savings would >>>>>be: >>>>> >>>>>0 EP 1 bit >>>>>1 EP 2 bits >>>>>2 EP 5 bits >>>>> >>>>>Oops! >>>>> >>>>>KarinsDad :) >>>> >>>>Actually, we can do even better: if there is *no* EP, we can store '0' in a >>>>header. If there *is* EP, we can store 1xxxx in a header, but we know values of >>>>the 4 squares - 2 pawns and 2 empty ones, so we can don't store those *at all*, >>>>just skip those fields when encoding a board. Total saving will be 2 bits in the >>>>first case (1 bit instead of 3 in the header), and 4 bits in the second case >>>>(header is 2 bits longer, but board is 6 bits shorter) compared to the first >>>>suggested schema. >>> >>>I figured out something similar on the way home. >>> >>>2 bits for EP >>>00 no EP >>>01 right EP >>>10 left EP >>>11 both EP >>> >>>plus if EP, then 3 more bits for column >>> >>>and we save either 3 (or 4 in the case of both) of the starting squares or 9 >>>bits there. >>> >>>0 EP 2 bits >>>1 EP 5 bits >>>2 EP 8 bits >>> >>>I am doing this quickly as I have to go, but I do not yet understand your entire >>>schmema yet ( I do not understand the 1xxxx yet ). >>> >>>> >>>>What is much more important, you can do something similar with castling status. >>>>In your schema, you reserverd 8 bits in the header - 6 for location of the king >>>>and 2 for possible castling directions. It's possible to replace it by something >>>>smaller, e.g. >>>>1) 0xxxxxx - castling not possible, and we have to store location of the king, >>>>2) 01 - both casling are possible, so we know locations of king and both rooks, >>>>3) 01x - only one castling is possible, so we know location of king and one of >>>>the rooks. >>>>In case 1 we save 1 bit, in case 2 - 14 bits, in case 3 - 7 bits. > >In case one, we save 1 bit, correct. > >In case two, it should be 100, not 01 (based on case 1 and case 3). We save 6 >bits for the king, 8 bits for the rooks (it is a back rank rook and so it has 4 >bits not 5 due to no pawns), but we gain one in the header. So we save 13 bits. > >In case three, it should be either 110 or 101 (or even 111) to indicate which of >the 2 castles is allowed. We save 6 bits for the king, 4 bits for one rook, but >we gain one in the header. So we save 9 bits. > >What does this mean for the starting position? 1 bit for side to move, 1 for no >EP, 3 for white can castle both ways, 3 for black can castle both ways, 0 for >kings, 0 for rooks, 16 for knights and bishops, 8 for queens, 48 for pawns, 32 >for blanks for a total of 112 or 14 bytes (it used to be 22 and then 20). Hope I >didn't miss anything. > >Not bad Eugene, this is looking better all of the time. Of course, every piece >that is not on the 1st or 8th rank will add 1 bit. Once castling for a side is >no longer viable will add in 8 bits for the rooks and 6 bits for the king. The >EP cases will be rare, so we do not have to worry much about them, but they will >actually be smaller than the none EP cases. And once in a blue moon (less than >2.5% of possible positions, a lot lower percentage of positions actually found >in a game), both kings will be properly in the same quadrant. All in all, not >too shaby. > >KarinsDad :) > >>> >>>There is an additional savings here that I realized on my drive home. If there >>>is a 0xxxxxx case, then you split the board up into quadrants. If both kings are >>>in the same quandrant AND one of the kings is in the middle 4 squares of the >>>quandrant, than the other king only has 7 squares that it can be in (as opposed >>>to 16 if the other king is not in the same quandrant), so from one king, you can >>>occassionally save 1 bit on the other king. This means that there are 16 squares >>>on the board where the white king can be where the black king cannot if if is in >>>the same quadrant (unfortunately, a king on the edge of a quadrant only cuts out >>>5 of the 16 opposing king squares, otherwise, this could be even better). >>> >>>KarinsDad :) >>> >>> >>>> >>>>It looks that I had a good practice when I invented a compact schema for TBs... >>>> >>>>Eugene
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.