Author: Vincent Diepeveen
Date: 06:02:44 01/30/02
Go up one level in this thread
On January 29, 2002 at 14:15:49, Les Fernandez wrote: >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 to-square we call it in chess. >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. You can't compress 'binary key sizes' from 63 bits size. Everyone who has done computerchess a little before knows that. My tip is to first read a number of computerchess books and fiddle somewhat with hashkeys in a program, before writing papers that are complete nonsense. >Les Best regards, Vincent
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.