Author: KarinsDad
Date: 08:34:22 10/27/99
Go up one level in this thread
On October 27, 1999 at 02:21:54, Les Fernandez wrote: Hi Les, I will try to address each problem as I see it. >Following is a chess board setup which I think represents a worst case scenario >for trying to find some scheme that we can use to demonstrate perhaps a >different approach in trying to reduce the number of bits needed to store thie >following position. > >|r|n|b|q|k|b|n|r| Piece key >|q|q|q|q|q|q|q|q| P - 1 >| | | | | | | | | N - 2 >| | | | | | | | | B - 3 >| | | | | | | | | R - 4 >| | | | | | | | | Q - 5 >|Q|Q|Q|Q|Q|Q|Q|Q| K - 6 >|R|N|B|Q|K|B|N|R| This position can never be reached. The most EXTRA queens on the board is 12, not 16. And, they can be in any combination with a maximum of 8 queens of one color. So, you could have 8 white queens and 4 black queens, or you could have 5 white queens and 7 black queens (with maximum promotions). I realize that having an illegal position will not affect your algorithm, however, when possible, we should take into account legal positions only. > >I am using the queens for the promoted piece since it takes the largest amount >to store. I realize that this position will never happen but it allows me to >demonstrate an idea I have for minimizing the bits needed to store this >position. > >Please note that "0" = black and "1" = white. In column 1 we will use a "0" as >a place holder for any square which is empty. Also each row below designates a >square on the bit board so we need 64 rows for each of the squares. > >The above board is stored by the following: > >Sticks Binary Binary > & with all with all >Stones queens pawns > >0000 0100 0100 >00 010 010 >000 011 011 >00000 0101 0101 Next problem. How do you differentiate between a knight 010 and a queen 0101? How do you know whether the pattern 0101 is a white knight followed by a black piece or a white queen? >000000 0110 0110 >000 011 011 >00 010 010 >0000 0100 0100 >00000 0101 01 >00000 0101 01 >00000 0101 01 >00000 0101 01 >00000 0101 01 >00000 0101 01 >00000 0101 01 >00000 0101 01 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >0 0 0 >11111 1101 11 The same here. What is the difference between a black space followed by a black piece 011.. and a white bishop 011? >11111 1101 11 >11111 1101 11 >11111 1101 11 >11111 1101 11 >11111 1101 11 >11111 1101 11 >11111 1101 11 >1111 1100 1100 >11 110 110 >111 111 111 >11111 1101 1101 >111111 1110 1110 >111 111 111 >11 110 110 >1111 1100 1100 >------ ------ ------ >170 152 120 > >Although EP and castling has not been considered here it should not involve many >bits to store that information. Whats interesting in the above example is that >using what I think is close to a worst type of position we show that we are able >to still keep the bit value down below 160. Now I know you always look at your >worst case scenario lets take a look at another board position. The exact >placement of all the pieces is not important here just as long as we mention >that we are talking all the initial chess pieces with no promoted pieces. By >using the above method we reduce the 152 bits down to 120. The way this is >arrived at is in the above case we eliminate all 16 promoted pieces which needed >4 bits and now with substituting our pawns in they only need 2 bits (01 black >pawn or 11 white pawn). Therefore for each all 16 pawns we need 32 bits a >saving of 32 bits. No I wonder if there is some way of estimating an overall >average for promoted pieces since I don't think having 16 promoted pieces on the >board happens very often. For a data point of view this may be a viable way of >storing positions if the above cant be disputed. Any feed back from any of you >number crunchers out there would be appreciated. KarinsDad <s> ???? This system is really not that much different than others, it just dropped some bits on the floor that are used to determine uniqueness. Since the parser that looks at the position knows where pieces are, it is able to create the bit pattern. However, the parser that reads in the bits does not know where pieces are, therefore, it cannot distinquish where to stop reading for a given piece. Note: You are on the correct track. You do have to check the worse case scenarios. But, you also have to take into account different interpretations of the bits (i.e. all bit patterns must be unique to a given position). 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.