Author: KarinsDad
Date: 09:24:37 10/20/99
Go up one level in this thread
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 :)
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.