Author: Les Fernandez
Date: 11:15:49 01/29/02
Go up one level in this thread
On January 29, 2002 at 13:03:33, Uri Blass wrote: >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 Hi Uri and may I say well phrased!! Anyway my thought regarding egtb's was more on the following premesis. First of all the egtb's is a collection of chess positions with perfect information. If that is the case then we can assume that there exists a response to some particular square based on the position that the egtb provides us (I call it the Target square. Now if the sliding piece is on say d3 and the target square is say and its target square according to the egtb is g3 then it is safe to assume that had the slider been on squares g1,g2,g4,g5,g6,g7,g8,a3,b3,c3,e3,f3,g3,h3 the sliding piece would still be able to reach the target square at g3. So now the number of variants becomes 14 for this first image and rotating it all 4 ways gives us 56 positions so in fact our average is (in the case of 3 pieces the binary key size is 63 bits [9*number of pieces+36]) 63 bits/56 positions. Keep in mind no compression has really been done up to this point and we are not just storing pointers/index and dtm's but actually the entire picture. Now I am not proclaiming this to be a replacement to formats of egtb's but only to possibly stimulate some thoughts in this direction which I feel may lead to some interesting things. Les
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.