Author: KarinsDad
Date: 00:41:38 05/16/99
Go up one level in this thread
On May 16, 1999 at 00:43:42, Eugene Nalimov wrote: >I slept, too and here is small correction: if you want to decrease not the >*average length*, but the *worst case*, you can squeeze 2 more bits: with >suggested schema, in the worst case we store 14 bits for kings squares and >castling status. It's possible to store that in 12 bits, but those 12 bits (or >at least half of them) must always present. There are 3612 (not 3812 as I posted >here yesterday) legal kings configurations. There are enough values left to 4096 >to store castling status. If one of the kings lost both castlings, but second >still can castle, we must store position of first king as well as which >castlings are possible for the second king - 2*64*3 values. Also there are the >cases when both knigs still can castle - 3*3 values. Total is 4005 values, so >all those values can be stored in 12 bits. Theoretically you can use remaining >to 4096 values to shorten the case when some castlings are available, and don't >store all 12 bits in that case. > >Eugene Well, there you went and ruined my idea on edge of board yesterday. :( (only kidding, it still works, see below) Ok, I will bite. How did you come up with your numbers? I would think that the 64 would be either a 59 or a 57 (the first king cannot be within range of the second king, nor within one square of the rook if it is the castling side to move). I assume you made it 64 for simplicity sake, but some of those values will never be used. Actually, even with this new castling schema, you could use the edge of board concept and drop this from 12 to 11 (ocassionally) since you could use the upper edge of the 10 or 11 bits from the edge of board schema to represent the castling cases. For example: Instead of 28 edge possibilities, you add 3 more (for each of the 3 different ways in which the first king can castle) Hence, 30*31+59=989 or still 10 bits (plus 1 bit to indicate an edge of board first king). There are 1315 first king not edge of board possibilities (if the first king is not at the edge of the board, we do not have to worry about castling for that king). Just add in your 2 * 33 * 3 possibilities at the high order of the 11 bits. The reason for 33 is that there is no chance of the first king being at the edge of the board (28) nor next to the other king within the middle of the board (3), so 64 - 28 - 3 = 33. Of course, it is not worth it to minimize the king representation by 1 bit if you are always going to pad your structure to 22 bytes (or 25 bytes or whatever). But it is fun to consider it. So, the total is now back to 173 bits (not including all legal pawn promotions in super bizarre cases). Dropping the 2 bits increases the chances of not running into one of those bizarre cases as well. Another well done Eugene! KarinsDad :)
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.