Author: KarinsDad
Date: 22:11:55 05/14/99
Go up one level in this thread
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.