Author: Robert Hyatt
Date: 07:16:46 10/23/01
Go up one level in this thread
On October 23, 2001 at 02:17:15, Nino wrote: >On October 22, 2001 at 16:21:59, Angrim wrote: > >>On October 22, 2001 at 02:00:54, Les Fernandez wrote: >> >>>On October 22, 2001 at 01:38:43, Les Fernandez wrote: >>> >>>>The following proposed method incorporates Eugene's 64 bitmap for piece location >>>>but in what appears to be a more condensed format. Initially a signature file >>>>needs to be generated that contains all possible squares or rectangles that can >>>>be found within an 8x8 matrix. There are 1296 of these unique squares for which >>>>some of them can be eliminated. ie 1x1(64), 1x2(56), 2x1(56) and 2x2(49) are >>>>eliminated since a legal chess position cannot exist in any of these >>>>configurations. 1296-225=1071. The following configurations will use Eugene's >>>>64 int bitmap anytime the piece distribution covers the boards 7x8(2), 8x7(2) >>>>and 8x8(1). 1071-5=1066. Note that there is potentially 2 ways of doing this. >>>>One approach is to use 1 extra bit as the first bit to tell you which method is >>>>to be used: >>>> >>>>ie if the matrix is 7x8, 8x7 or 8x8 then if bit 1=0 then you use Eugene's >>>>current method. However if it is any other configuration then bit 1=1 would >>>>tell you that the next 11 bits are to be used to search the signature file for >>>>the bitmap. Adding this one bit does minimize the benefit to some degree and >>>>can be eliminated if one is willing to keep those positions that exist in a 7x8, >>>>8x7 or 8x8 matrix in one file and all others in another file. For the sake of >>>>explaining this method it is not really necessary to ascertain which method is >>>>better, whats important is that we know we are using a signature file. >>>>Following is a segment from the signature file: >>>> >>>> 1000 1110000011100000111000001110000011100000000000000000000000000000 >>>> 1001 0000000000000000000000000111000001110000011100000111000001110000 >>>> 1002 0000000000000000011100000111000001110000011100000111000000000000 >>>> 1003 0000000001110000011100000111000001110000011100000000000000000000 >>>> 1004 0111000001110000011100000111000001110000000000000000000000000000 >>>> 1005 0000000000000000000000000011100000111000001110000011100000111000 >>>> 1006 0000000000000000001110000011100000111000001110000011100000000000 >>>> 1007 0000000000111000001110000011100000111000001110000000000000000000 >>>> 1008 0011100000111000001110000011100000111000000000000000000000000000 >>>> 1009 0000000000000000000000000001110000011100000111000001110000011100 >>>> 1010 0000000000000000000111000001110000011100000111000001110000000000 >>>> >>>>The number in front of the line is the index number and it is followed by a 64 >>>>int bitmap signature. Following I will try to demonstrate how we plan to use >>>>this signature file. Lets say we have the following 5 piece chess board. >>>> >>>>[D]8/1k6/2p5/8/2KR4/2P5/8/8 w - - >>>> >>>>or >>>> >>>>| | | | | | | | | >>>>| |k| | | | | | | >>>>| | |p| | | | | | >>>>| | | | | | | | | >>>>| | |K|R| | | | | >>>>| | |P| | | | | | >>>>| | | | | | | | | >>>>| | | | | | | | | >>>> >>>>Eugene's method would use the following 64 int bitmap to determine which squares >>>>were occupied: >>>> >>>>0000000001000000001000000000000000110000001000000000000000000000 >>>> >>>>However alot of the bits used here are really not necessary. >>>> >>>>The proposed thought is to construct a least fitting square which is capable of >>>>containing all the chess pieces that exist on the board, do a lookup to find >>>>that specific pattern in the signature file and use the index number as the >>>>reference. Since the index number can never be larger then 1066 it can always >>>>be represented by an 11 bit key. >>>> >>>>ie the above chess board pieces can all be contained in the following square. >>>> >>>>| | | | | | | | | >>>>| |x|x|x| | | | | >>>>| |x|x|x| | | | | >>>>| |x|x|x| | | | | >>>>| |x|x|x| | | | | >>>>| |x|x|x| | | | | >>>>| | | | | | | | | >>>>| | | | | | | | | >>>> >>>>Once this has been determined search the signature file and we see that >>>>index=1003 is in fact this pattern. Now this position can be stored using this >>>>11 bit index instead of the 64 bit number in the current system. Following is a >>>>comparison of the 2 methods: >>>> >>>>Eugene's 0000000001000000001000000000000000110000001000000000000000000000..... >>> >>>>Proposed 01111101011....... >>> >>>CORRECTION: >>>Proposed 01111101011 100010000011010....... >>> >>>> >>>>a saving of 53 bits (64-11) >>> >>>CORRECTION: >>>a saving of 38 bits [64-(11+15)] >> >>CORRECTION: >>a saving of -26 bits [0-(11+15)] >>The current method does not need to store a board representation in >>the file at all. >>The board being looked up is converted to an index into the file, and the >>value stored at this index is the distance to win/loss, or a special >>value such as 0 for draws. >> >>> >>>> >>>>This method appears to save bit storage as long as we dont use this method when >>>>the pieces are dispersed among 7x8, 8x7 and 8x8 in which case we would use the >>>>current method being used. Please note I have no idea speed wise if this method >>>>is practical but hope that it will atleast trigger some other potential variant >>>>ideas etc. If we find that speed is not compromised then certainly this could >>>>greatly reduce the size of egtb's since there are so few pieces present on the >>>>board. >>>> >>>>Now lets get on our thinking caps guys <s>!!! or is this boat still sinking? >> >>good news: the boat stopped sinking. >>bad news: there are rocks sticking through the bottom of the hull. >>To stretch an analogy rather far :) >> >>Your post continues the main theme of this thread, which is bright >>people coming up with creative ideas based on WAY too little information >>about the existing methods. >> >>Angrim > >Hi Angrim, > >How are egtb's done if the position is not stored? (just curious) Take KQ vs K. Most positions lead to a forced mate, while a few lead to draws (stalemates or insuficient material). Each piece can be on a square between 0 and 64. Create an array TB[64][64][64], which represents the three squares the white king, white queen and black king can be on. Now for each of these possible (64^3 or 262144 total) positions, you search them to find the mate-in-N value or 0. When you reach a positoin with KQ and K, you just find the three square numbers for the three pieces, and use those as the indices into the array to get the mate in N or draw score: score=TB[WK][WQ][BK]; that is all there is too it. And then you start reducing the size of that large array by constraining the king to sit on 10 squares only by using symmetry (horizontal, vertical and diagonal), and you then compress that result further with normal compression schemes... that's it, in a nutshell. >Anyway I really dont know much about egtb's but I do know a little bit about >storing of epd positions and that the current method I think requires 192 bits >per position. I have just put together a table using Les's concept but for >storing chess positions. The table follows: > > Bits >Square Saved % saved > >1x3 50 78.1 >1x4 49 76.6 >1x5 48 75.0 >1x6 47 73.4 >1x7 46 71.9 >1x8 45 70.3 >2x3 47 73.4 >2x4 45 70.3 >2x5 43 67.2 >2x6 41 64.1 >2x7 39 60.9 >2x8 37 57.8 >3x1 50 78.1 >3x2 47 73.4 >3x3 44 68.8 >3x4 41 64.1 >3x5 38 59.4 >3x6 35 54.7 >3x7 32 50.0 >3x8 29 45.3 >4x1 49 76.6 >4x2 45 70.3 >4x3 41 64.1 >4x4 37 57.8 >4x5 33 51.6 >4x6 29 45.3 >4x7 25 39.1 >4x8 21 32.8 >5x1 48 75.0 >5x2 43 67.2 >5x3 38 59.4 >5x4 33 51.6 >5x5 28 43.8 >5x6 23 35.9 >5x7 18 28.1 >5x8 13 20.3 >6x1 47 73.4 >6x2 41 64.1 >6x3 35 54.7 >6x4 29 45.3 >6x5 23 35.9 >6x6 17 26.6 >6x7 11 17.2 >6x8 5 7.8 >7x1 46 71.9 >7x2 39 60.9 >7x3 32 50.0 >7x4 25 39.1 >7x5 18 28.1 >7x6 11 17.2 >7x7 4 6.3 >7x8 -3 -4.7 >8x1 45 70.3 >8x2 37 57.8 >8x3 29 45.3 >8x4 21 32.8 >8x5 13 20.3 >8x6 5 7.8 >8x7 -3 -4.7 >8x8 -11 -17.2 > >It is interesting to see the gains using this method. Remember to throw out the >7x8, 8x7 and 8x8 sets. Now those numbers might be interesting to ponder when it >comes to storing chess positions. Unless my math is wrong can someone tell me >if they see anything wrong with this approach? Mr Corbit??
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.