Author: Les Fernandez
Date: 22:38:43 10/21/01
Go up one level in this thread
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....... a saving of 53 bits (64-11) 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?
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.