Author: William H Rogers
Date: 06:42:36 10/27/99
Go up one level in this thread
On October 27, 1999 at 02:21:54, Les Fernandez wrote: >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| > >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 >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 >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> ???? I may be wrong, but I think that you are forgeting that each piece is 4 bits long counting leading zeros or else you may not be able to read correctly. How is the computer suppost to know if it should read only two bits, three, or four? you can write..11 but in reality it should be written as 0011 I may be wrong but that is my opinion. Bill
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.