Author: Dann Corbit
Date: 21:23:17 08/05/04
Go up one level in this thread
Using bitboards it is easy.
You precompute some tables and for any piece on a row or column or diagonal, all
the attacks and pins are a single mask and lookup.
For each square on the chessboard, for each possible piece, store a list of all
possible moves from that square by piece type.
By examiniation of what else is on the board, you can also automatically trim
the lists. It's much easier with bitboards [especially with rotated bitboards].
For kings, pawns, and knights, the attack bitboards are always the same (except
when pinned against a king by an opponent piece). For the sliding bishops,
rooks and queens (bishop +_rook) you need to know when to break it off.
Suppose we have a rook on e4:
+---+---+---+---+---+---+---+---+
8 | | | | | | | | |
+---+---+---+---+---+---+---+---+
7 | | | | | | | | |
+---+---+---+---+---+---+---+---+
6 | | | | | | | | |
+---+---+---+---+---+---+---+---+
5 | | | | | | | | |
+---+---+---+---+---+---+---+---+
4 | | | | | R | | | |
+---+---+---+---+---+---+---+---+
3 | | | | | | | | |
+---+---+---+---+---+---+---+---+
2 | | | | | | | | |
+---+---+---+---+---+---+---+---+
1 | | | | | | | | |
+---+---+---+---+---+---+---+---+
a b c d e f g h
He attacks this row:
+---+---+---+---+---+---+---+---+
8 | | | | | | | | |
+---+---+---+---+---+---+---+---+
7 | | | | | | | | |
+---+---+---+---+---+---+---+---+
6 | | | | | | | | |
+---+---+---+---+---+---+---+---+
5 | | | | | | | | |
+---+---+---+---+---+---+---+---+
4 | + | + | + | + | R | + | + | + |
+---+---+---+---+---+---+---+---+
3 | | | | | | | | |
+---+---+---+---+---+---+---+---+
2 | | | | | | | | |
+---+---+---+---+---+---+---+---+
1 | | | | | | | | |
+---+---+---+---+---+---+---+---+
a b c d e f g h
And he attacks this column:
+---+---+---+---+---+---+---+---+
8 | | | | | + | | | |
+---+---+---+---+---+---+---+---+
7 | | | | | + | | | |
+---+---+---+---+---+---+---+---+
6 | | | | | + | | | |
+---+---+---+---+---+---+---+---+
5 | | | | | + | | | |
+---+---+---+---+---+---+---+---+
4 | | | | | R | | | |
+---+---+---+---+---+---+---+---+
3 | | | | | + | | | |
+---+---+---+---+---+---+---+---+
2 | | | | | + | | | |
+---+---+---+---+---+---+---+---+
1 | | | | | + | | | |
+---+---+---+---+---+---+---+---+
a b c d e f g h
But if pieces are on the board, we can have 127 different bit patterns for
things that might be attacked on either row or column.
First, take a mask of everything on the board against (for instance) the column:
+---+---+---+---+---+---+---+---+
8 | | | | | P0| | | |
+---+---+---+---+---+---+---+---+
7 | | | | | + | | | |
+---+---+---+---+---+---+---+---+
6 | | | | | P1| | | |
+---+---+---+---+---+---+---+---+
5 | | | | | + | | | |
+---+---+---+---+---+---+---+---+
4 | | | | | R | | | |
+---+---+---+---+---+---+---+---+
3 | | | | | + | | | |
+---+---+---+---+---+---+---+---+
2 | | | | | P2| | | |
+---+---+---+---+---+---+---+---+
1 | | | | | P3| | | |
+---+---+---+---+---+---+---+---+
a b c d e f g h
P1 is attacked if an enemy piece, and defended if a friendly piece. P2 is
attacked if an enemy piece, and defended if a friendly piece. P1 is also pinned
because of P0, if P0 is undefended or defended yet highly important (king/queen)
if both are enemy pieces. The same for P2/P3.
E7 is what I call a shadow square. It is immediately under attack if P1 moves.
E5 and E3 are attacked by the rook. This is important for board control
calculation.
You end up with this:
+---+---+---+---+---+---+---+---+
8 | | | | |Sat| | | |
+---+---+---+---+---+---+---+---+
7 | | | | | S | | | |
+---+---+---+---+---+---+---+---+
6 | | | | |DAP| | | |
+---+---+---+---+---+---+---+---+
5 | | | | |RAT| | | |
+---+---+---+---+---+---+---+---+
4 | | | | | R | | | |
+---+---+---+---+---+---+---+---+
3 | | | | |RAT| | | |
+---+---+---+---+---+---+---+---+
2 | | | | |DAP| | | |
+---+---+---+---+---+---+---+---+
1 | | | | |Sat| | | |
+---+---+---+---+---+---+---+---+
a b c d e f g h
Sat is a shadow attack.
S is a shadow square
DAP is direct attack + pin
RAT is rook attack
Now, we mask with the bitmaps by color, and we discover that Sat, S and DAP are
always good for the color of R, but of differing values. If you attack your own
piece, it means it is not hanging. If you attack the opponent piece, then you
have (potentially) winning battery (must be calculated, obviously, against all
other attacks).
So a few simple mask operations can tell you all about the chessboard. I
imagine a table could also be precomputed for 0x88. It is important to only try
to do one row or column at a time. Otherwise the tables become too big. This
is a waste both for memory space and also the big tables spill the CPU cache,
and the small ones don't.
Shadows and shadow attacks are also important for defense. It means you can
protect the shadowed piece by moving the one creating the shade.
You could also return half-pins, if you had a mind to (would be pinned if the
front piece moved).
It is also possible to have an unrolled function for each returned bitmap (to
update counts, etc.)
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.