Author: Robert Hyatt
Date: 17:02:45 12/02/98
Go up one level in this thread
On December 02, 1998 at 16:41:35, Inmann Werner wrote:
>Analyzing my program, I found, that it spends most time in the routine detecting
>if the king is in check.
>I think, using Bitboard Representation will speed up a lot, and using Bitboards
>for this at the start will increase my learning.
>After some thinking and reading, I have some nice working routines but one big
>problem.
>
>I have a Bitboard with one Bit set to one, all others to zero. Now I want to
>know the number of the bit, counted from the "right side".
>Example: 64 should be 7 (or 6?) cause its the 7th (or 6th) bit.
>I programmed some routines which are more than bad. Is there a simple, but fast
>routine available? Please help!
Here is a thing we used in Cray Blitz. Note that it is somewhat memory
intensive, but it flies on a vector machine...
create an array attacks[64][64][6]
think of this as attacks[from][to][piece_type]
you initialize that array (64 bit integers) with masks... lets take the
case attacks[from][to][bishop]... all you do is for any two squares from,to,
that are on the same diagonal, you set 1 bits in every position where that
diagonal must be *empty* in order for a bishop on [from] to attack square [to].
If the squares aren't on the same diagonal, set the mask to -1 (all 1 bits).
You do the same for rooks and queens. For knights and kings it is easier. If
a knight on [from] attacks [to] you set the mask to 0, otherwise you set it to
-1. Ditto for kings.
To answer the "is a king in check" you only need a single "occupied squares"
bitmap that you update when you make/unmake moves. you do the following loop
to answer the in check question:
for (i=0;i<npieces;i++)
if (!(occupied_squares &
attacks[piece_loc[i]][opps_king_loc][piece_type[i]])) return(1);
return(0);
If you take the mask
attacks[one_of_your_pieces][opponents_king][your_piece_type], that gives the
set of squares that must be empty on the occupied_squares bitmap in order for
the attack from [from] to [to] for piece [piece_type] to be true. On the cray
this vectorizes and we didn't even notice it in our profiling. I don't do it
like this in crafty because with rotated bitmaps there are better ways...
>
>Second question.
>I will work with lookup tables. Cause I do not want to use rotated bitboards (at
>the beginning) I came to a "trick" for sliding figures.
>
>After some ANDs and ORs I know the Position of the king and the "attacking" rook
>for example. Now I have to find, if another figure blocks the attacking. With
>some other ANDs and XORs I have all possible "blockers" in a bitboard. Now I
>"AND" it with an attacktable which is defined as following.
>BITBOARD ATTACKTABLE[64][64]. In it are all BITBOARDS where all possible
>blocking Positions are in between the king and the attacking rook.
>Thats it.
check out the above piece of code... works like a charm. and does just what
you are doing... notice you need the piece type because a rook can't move down
a diagonal, nor a bishop down a file or rank.
>
>Is this a really bad idea? Any suggestions.
>
>Werner
>
>PS: I know, I "invite" old known things, but I want to understand what I do.
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.