Author: Dan Newman
Date: 16:00:58 01/16/99
Go up one level in this thread
Posted by Frank Phillips on January 16, 1999 at 06:40:05:
>I have vague thoughts of moving on from mailbox[] to 0x88 and would be
>grateful for a bit more detail on the second part of Bruce’s 0x88 message
>(Jan 12, message number 39133) about masks, particularly how to use them
>(bfBishop | bfQueen for instance)?
>
The idea is to make an array of bitmaps which can be indexed by the
difference in 0x88 coordinates of two squares. This index is in
the range of -119 to 119 since on-board 0x88 coords range from 0 to
119. This means the array must have at least 239 entries (I ususally
"round" this up to 240 with the idea that that might improve alignment
of data...). You can then index the array like this:
array[coord2-coord1+119]
What I usually do is set a pointer equal to array+119 and then
index that with the coordinate difference to save adding the
offset each time:
pointer[coord2-coord1]
The bits in each bitmap indicate which piece types are capable of
moving from coord1 to coord2, ignoring whether the intervening
and target squares are occupied or empty.
These sorts of tables are quite useful in testing for in-check and
in determining whether a side attacks a given square or not. For
the non-sliding pieces (knight and king and pawn when attacking)
this table tells you almost instantly whether the piece attacks a
given square. For the sliding pieces it tells you whether it is
possible for the piece to attack the square and tells you almost
instantly if it can't. I implemented my brute-force in-check
detector something like this:
int incheck( int side)
{
piece_t *p = plist[side^1];
int kcoord = coord( king[side]);
while( *p ) {
int diff = kcoord - coord( *p);
if( attacks[diff] & masks[ type( *p)] ) {
if( slider( *p) ) {
int step = steps[diff];
int i;
for( i = coord( *p) + step; i != kcoord; i += step ) {
if( board[i] != 0 ) break;
}
if( i == kcoord ) return 1;
} else return 1;
}
p++;
}
return 0;
}
I did this one off the top of my head--I hope it's correct. Notice
that I also have a steps[] array that is also indexed by the coordinate
difference and which returns the step offset in the proper direction of
motion for sliding the piece toward the target (king).
>Also, is there a simply way of initialising the board, the piece-square
>tables and masks with this approach, which from this perspective seem a
>bit more cumbersome than 64 element arrays? I guess this goes for
>looping through the square as well - to find pieces for example.
>
This trick does make those tables larger, and the initialization code
generally isn't very pretty.
One could do the board and piece square tables as 64 element arrays
and just convert coordinates to 0x88 (table lookup or calculation)
before subtracting them to index the coordinate difference tables.
I use piece lists instead of looping through the board. I've tried
looping though the board, but that gives a rather big hit on move
generator performance in my experience.
>Are there any reference works on this technique other than Frey, Chess
>Skill in Man and Machine, which I have failed to locate.
Hmm. I must have missed it in Frey. I think I saw brief mention of
0x88 in Levy & Newborn's _How Computers Play Chess_ but I'm not sure.
I first found out about it on RGCC a couple years back I think. The
most I've seen about it in print was in the Rajah article in ICCAJ
(Manohararajah, V. (1997). RAJAH: The Design of a Chess Program, ICCA
Journal, Vol. 20, No. 2, pp. 87-91.)
-Dan.
This page took 0.01 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.