Author: Les Fernandez
Date: 23:00:54 10/21/01
Go up one level in this thread
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)] > >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.