Author: Ricardo Gibert
Date: 15:21:07 01/30/02
Go up one level in this thread
On January 30, 2002 at 08:32:40, Vincent Diepeveen wrote: >On January 29, 2002 at 14:29:09, Ricardo Gibert wrote: > >>On January 29, 2002 at 14:03:24, Robert Hyatt 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 >>> >>> >>>I think your math is wrong. If you need 288+36 bits to store one position, you >>>need 288+36-2 bits to store 1/4 of that number of positions. This is log math >>>and you _subtract_ exponents, not divide. >>> >>>ie 2^32 / 4 == 2^30, _not_ 2^8 >>> >>>That is where I am getting lost in your description... >> >>What they are doing is, "semantically" speaking, correct. You'll laugh when you >>figure it out. If you don't, don't worry, it doesn't mean they have come with >>anything new other than with the "semantics". > >it must be wrong there too as they miss 2^100 bits somewhere :) Too keep things simple, let's assume it takes them 200 bits to store 1 particular position. What they are saying is, "Oh look! That's really 4 positions when we include reflections and rotations! It takes 200 bits for the first position and we get the next 3 for free - 0 bits! That's an average of (200 + 0 + 0 + 0)/4 = 50 bits per position!" True. Unfortunately, it is still 200 bits per unique position. They're counting things up in a non-standard way. They can justify this, since their "new" idea is to expand the equivalence class that includes reflections and rotations to include more positions by trading optimal play for suffiently strong play. In this case, counting in this way is not unreasonable for comparison purposes. Their ideas can be made to "work" for EGTBs, but I don't think it will reduce EGTBs when they are in uncompressed format. It can be used to enhance the compressability of them, however. Another problem is it will be computationally prohibitive to generate such EGTBs and thus limit their utility for such EGTBs. Unlike in endings where we can content ourselves with an upper bound on the number of moves to win, in middle games and openings we are generally only interested in best known play. The trade for optimality for sufficiency is not a doable trade there.
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.