Author: Angrim
Date: 13:21:59 10/22/01
Go up one level in this thread
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
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.