Author: Les Fernandez
Date: 15:56:33 10/27/99
Go up one level in this thread
On October 27, 1999 at 11:34:22, KarinsDad wrote: Hello KarinsDad, It is great to hear your thoughts as always <s>. I will try to answer some of your questions that you raised: >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| I do realize that this position can never be raised and just learned that you cant have more then 12 queens as you have been so kind to share. Learn something new every day. However for the moment I was more or less interested in explaining the method. >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? As far as this question KD what I am proposing is that the binaries on each individual line represent an individual square on the chess board. What I think confused you was the fact I think you thought that these binaries were in a horizontal contiguous string. What I am proposing is to allocate an individual line for each of the bit board. That way there is no need to distinguish between whether the pattern 0101 is a white knight followed by a black piece etc. What it is meant to say is the following: Bit 1=0=black Bit 2,3 and 4 represent a 5 and is equal to a Queen. So binary 0101 is a black queen. I think this also answers your next question which is similar. I hope this clarifies it for you KD and if not drop me a line. > >>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 :) Les :)
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.