Author: Les Fernandez
Date: 21:57:15 10/20/99
Go up one level in this thread
On October 20, 1999 at 12:24:37, KarinsDad wrote: >On October 19, 1999 at 20:24:23, Les Fernandez wrote: > >[snip] >> >>Hello Dann, >> >>Well to start things off one might consider wasting 2 questions at the very >>beginning of your question tree to help "squish" your data set down by asking >>the following: Question 1 are there any blank rows on the chess board, Question >>2 are there any blank columns on the chess board. ie lets say that question 1's >>response is "no" then we have only wasted 1 question however, in which case we >>would not have to ask whether or not that particular row is blank. However if >>the answer is yes then we must add one question at the beginning of each row to >>determine if the current row is blank. With a yes we are assured of there being >>atleast 1 blank row (close break even point) since we would not have to concern >>ourselves with any question regarding any of the 8 squares in that blank row. >>This saves 7 questions since we needed to ask 1 question whether the row was in >>fact blank. Savings begin to get realized when more then 1 blank row exists. >>This could perhaps be applied to columns also. It will be interesting to see >>what other tricks people out here have up there sleeves <s>. > >Les, > >Although these types of "tricks" sound good on the surface, they do not work. > >The reason is that no matter how many positions have a blank row or column, >there is always millions of positions where there are no blank rows or columns >with the exact same pieces on the board. This means that for those millions of >positions, you have wasted two bits. > >The problem is always one of coming up with a "trick" that increases the number >of bits for positions that do not take up that many bits while at the same time >decreasing the number of bits for positions that take up a lot of bits. > > >A trick that does work is ignoring en passant. You effectively need no bits for >it. The reason for this is as follows: > >Say you have 32 pieces on the board. You can make the rule that with a 32 piece >representation on the board, there is no en passant. > >If you have a 32 piece position with en passant, you represent it as a 30 piece >position with two en passant pawns that are not represented in the normal way >(i.e. as if there are only 30 pieces). Since a 30 piece representation saves at >least 4 bits (with a 1 bit pawn and 1 bit pawn color for two missing pawns, it >saves more bits on algorithms with more than 1 bit for a pawn) over a 32 piece >representation, you could use the last 4 bits in the algorithm to determine if >there is en passant and if so, which pawns are capable: > >0000 - no en passant >0001 to 1110 - start column of en passant and direction of en passant (total 14) > >So, as can be seen, en passant can be represented in a 30 or fewer piece >representation with the exact same number of bits that no en passant in the >exact same position can be represented in 32 or fewer pieces. > >A similar thing can be done with representing castling state within the same >number of bits as the location of the kings. > >KarinsDad :) Thanks for your explanation. The EP is clever and I can't help think that there must be a way (not to tricky) to shave some additional bits from the picture. I know alot of you guys have worked on a bunch of things but my mind is not letting go yet <s>. Well onward and upward. I guess thats not a good phrase to use here, should have been onward and DOWNward <s>.
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.