Author: Uri Blass
Date: 10:03:33 01/29/02
Go up one level in this thread
On January 29, 2002 at 11:28:06, Andreas Stabel wrote: >On January 29, 2002 at 10:47:40, Les Fernandez wrote: > >>On January 29, 2002 at 09:57:30, Robert Hyatt wrote: >> >>>On January 28, 2002 at 17:48:48, Les Fernandez wrote: >>> >>>>Just curious to know what is the best being done now for storing a chess >>>>position. In the worse case scenario (castling right exists) it takes me 162 >>>>bits to store 32 pieces, color, location, side to move, castling, enpassant, >>>>promotion, ce and pv. Now if castling rights do not exist then the worse case >>>>scenario for the above is 81 bits. Much further reduction in bits/position is >>>>possible but at the moment I am interested in the above. >>>> >>>>Thanks in advance, >>>> >>>>Les >>> >>> >>>How can you store a complete chess position without castling rights in 81 >>>bits? castling rights are certainly not 81 bits of information to get you >>>up to 162. >>> >>>Something is wrong. >> >>Hi Bob, >> >>The point is that in cases where castling is not available there exists a >>minimum of 4 rotations that can be applied to a board, top-bot and left-right. >>The method I discuss to store a position requires 9 bits to store piece, color >>and x and y location. 32x9=288 and then 36 bits are needed to store the other >>pertinent things about the position. (288+36)/4=81 bits/position on avg. just >>as Uri explained here (thx Uri sorry Bob if I was not clear). I thought the >>scheme I used to store a piece using only 9 bits was different and would >>appreciate feedback here. >> >>Thanks, >> >>Les > >You cannot divide the number of bits by four because there is a 4-fold >reduction in possibilities - you have to subtract two bits :) > >Regards >Andreas Stabel He can because the idea is not to use 81 bits for position but to use 324 bits per class of 4 positions. It is clear that it is impossible to use 81 bits for only one position even if you assume that positions in the same class are the same. Using 324 bits for every class of 4 positions mean using an average of 81 bits per position. Note that there is a simple known way to use less bits: 64 bit number that tells you the empty square(1 is not empty when 0 is empty) after the 64 bit number you need only 4 bit number for every piece in the board. In the worst case when there are 32 pieces in the board you may need 128 bits to store them. It means that the position can be stored by 192 bits I did not check how many are needed to store the other things but even if we assume that 36 bits are needed for it then you can store every class of 4 positions by 228 bits that mean that you get an average of 57 bits per position. Note that I do not see the importance of this result and I know that tablebases are constructed by using symmetry considerations so these ideas cannot help to build smaller tablebases than the existing tablebases. 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.