Transcript Document
Some Chess-specific Techniques
• Chess is played on an 8x8 board
• 8 is a power of two
• Computers are especially good at handling powers of two
This happy accident has been exploited in chess programs in two main ways:
• move generation speedups
• bitboard representations
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
1
Move generation: the obvious way
A natural way to represent the board is with an 8x8 array,
• containing values 1..12 representing black pawn, ... white king
• indexed by
rank running from 0 to 7
file running also from 0 to 7
When a chessman move is being considered, the new rank and file must satisfy
rank ≥ 0 and rank ≤ 7 and file ≥ 0 and file ≤ 7
• A rook can move in a ray over several empty squares,
along a file {rank := rank ± n} or along a rank {file := file ± n}
• A bishop can move in a ray over several empty squares, along a diagonal
{rank := rank ± n; file := file ± n}
• A queen can do either the above.
• Knights, Kings and (usually) Pawns do not move in rays.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
2
Move generation with vector-based board - 1/3
It is faster to access a 1-dimensional vector than a 2-dimensional array.
8x8 board may be linearised so that 64 elements of a vector [0…63] correspond
to squares a1, b1, c1, d1, e1, f1, g1, h1, a2, b2, … g8, h8
• Then a rook moves from square X
to X - n (stopping after a multiple of 8)
or to X + n (stopping short of multiple of 8)
or to X ± 8n (stopping before going negative
56 57 58 59 60 61 62 63
or going beyond 63)
48 49 50 51 52 53 54 55
• A bishop moves from square X
40 41 42 43 44 45 46 47
to X ± 9n
32 33 34 35 36 37 38 39
to X ± 7n
24 25 26 27 28 29 30 31
• A knight moves from square X
16 17 18 19 20 21 22 23
to X±10, X±17, X±15, X±6
http://csiweb.ucd.ie/Staff/acater/comp4031.html
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
Artificial Intelligence for Games and Puzzles
3
Move generation with vector-based board - 2/3
For all piece types, the legality of moves must be checked.
• Checking a proposed move does not go off the top or bottom of the board is
easy, just check {X ≥ 0 and X ≤ 63}
• Checking a proposed move does not go over the left or right edge of the
board is not as easy as that; effectively you must decompose X into its rank
& file components.
Can do this fairly cheaply since divide-by-8 and modulo-8 can be done
with a rightshift operation and a bitwise-and operation, respectively.
• The top/bottom check can be made cheaper by exploiting these facts:
all numbers 0-63 have a ‘0’ in bit position 7 (from least significant)
negative numbers, and also numbers 64-127, have a ‘1’ in bit position 7
so whenever {X & 64} is non-zero then X is not valid
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
4
Move generation with vector-based board - 3/3
The board vector need not be exactly the right size. It can be bigger than needed.
It is useful for it have 128 elements. (Actually only 120 is enough!)
Chessboard squares can be mapped to vector elements as follows:
a1,b1,c1,d1,e1,f1,g1,h1, ,
1st rank
,
,
,
,
,
,
8 unused elements
, a2,b2,c2,d2,e2,f2,g2,h2,
2nd rank
This allows both rank and file parts of an index to be checked in one operation:
• indices with a ‘1’ in bit 8 are negative or greater than 127
• +ve indices with a ‘1’ in bit 4 are in the range 8-15, 24-31, 48-55, …
they correspond to vector elements not mapped to any square.
When (X & #x88) is nonzero X is invalid. This is the “Hex-88 Trick”.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
5
Bitboards
Rather than use a vector containing codes identifying chessmen, many programs
use a collection of several 64-bit vectors, using one bit per chessboard square.
The technique was pioneered by “Kaissa”, a Russian program of the 1970s
which ran on a computer with 64-bit words; as today’s “Alpha” chips.
Each “bitboard” uses ‘1’ bits to represent different things about a square.
This square is occupied.
This square is occupied by a bishop.
This square is occupied by white.
This square is occupied by a rook.
This square is occupied by black.
This square is occupied by a queen.
This square is occupied by a pawn.
This square is occupied by a king.
This square is occupied by a knight.
•Making a move then involves changing at least three of these bitboards.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
6
“Ordinary” moves of knight and king
• These pieces move fixed distances in any of 8 directions.
• They capture any enemy piece occupying their target square.
• There is no need to consider any squares other than source and target.
• For each type of piece,
and for each source bit position,
– up to eight bitmaps can be constructed and stored
– to represent the up-to-8 possible targets for that piece type starting
from that source square
• If say the “d5” bit is set in the “white” and “knight” bitboards,
• then consider the eight d5-knight bitmaps in turn
• check that {WhiteBitboard & currentbitmap} is zero, if so
zero the “d5” bit in the occupied, white, & knight bitboards
zero target bit in the black, pawn, bishop, rook, queen, & king bitboards
set to one the target bit in the occupied, white, & knight bitboards
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
7
Rook moves
Rooks (and Queens) can move in rays, along ranks or along files.
• all squares they pass over must be unoccupied
• the final square may be unoccupied or occupied by an enemy piece
For each square, a bitmap can specify the other squares a rook (or queen) could
reach if unimpeded.
To see if a rook (queen) could actually reach a particular square involves
checking the occupied bitboard against a substring of bits. (If a bitwise AND
returns nonzero, the square cannot be reached)
• It is better then to use four separate bitmaps - attack bitboards - for the four
different directions of movement.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
8
Flipped bitboards
Checking substrings of bits involves forming substrings of bits.
This is easily done by bit-shifting when the bits in a bitstring are consecutive in
memory. For the bitboard organisation shown before, that makes it easy to
manipulate attack bitboards for attacks along a rank, but not along a file.
By using additional bitboards, flipped on their sides, this too is made easy.
a8
b8
c8
d8
e8
f8
g8
h8
h1
h2
h3
h4
h5
h6
h7
h8
a7
b7
c7
d7
e7
f7
g7
h7
g1
g2
g3
g4
g5
g6
g7
g8
a6
b6
c6
d6
e6
f6
g6
h6
f1
f2
f3
f4
f5
f6
f7
f8
a5
b5
c5
d5
e5
f5
g5
h5
e1
e2
e3
e4
e5
e6
e7
e8
a4
b4
c4
d4
e4
f4
g4
h4
d1
d2
d3
d4
d5
d6
d7
d8
a3
b3
c3
d3
e3
f3
g3
h3
c1
c2
c3
c4
c5
c6
c7
c8
a2
b2
c2
d2
e2
f2
g2
h2
b1
b2
b3
b4
b5
b6
b7
b8
a1
b1
c1
d1
e1
f1
g1
h1
a1
a2
a3
a4
a5
a6
a7
a8
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
9
Bishop moves
Bishops (and Queens) can move in rays, along diagonals. Again,
• all squares they pass over must be unoccupied
• the final square may be unoccupied or occupied by an enemy piece
For each square, a bitmap can specify the other squares a bishop (or queen) could
reach if unimpeded.
As before, in order to generate substrings of bits easily it would be necessary to
transform the bitboards. This (complex) transformation has the name “rotated
bitboard”.
The term “rotated bitboard” has come to apply to flipped bitboards as well as the
two transformations to follow:
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
10
Rotating a bitboard for a1…h8
1. Cut bitboard along a diagonal
http://csiweb.ucd.ie/Staff/acater/comp4031.html
a8
b8
c8
d8
e8
f8
g8
h8
a7
b7
c7
d7
e7
f7
g7
h7
a6
b6
c6
d6
e6
f6
g6
h6
a5
b5
c5
d5
e5
f5
g5
h5
a4
b4
c4
d4
e4
f4
g4
h4
a3
b3
c3
d3
e3
f3
g3
h3
a2
b2
c2
d2
e2
f2
g2
h2
a1
b1
c1
d1
e1
f1
g1
h1
Artificial Intelligence for Games and Puzzles
11
Rotating a bitboard for a1…h8
a8
b8
c8
d8
e8
f8
g8
h8
a7
b7
c7
d7
e7
f7
g7
h7
a6
b6
c6
d6
e6
f6
g6
h6
h7
a5
b5
c5
d5
e5
f5
g5
h5
g6
h6
a4
b4
c4
d4
e4
f4
g4
h4
f5
g5
h5
a3
b3
c3
d3
e3
f3
g3
h3
e4
f4
g4
h4
a2
b2
c2
d2
e2
f2
g2
h2
d3
e3
f3
g3
h3
a1
b1
c1
d1
e1
f1
g1
h1
c2
d2
e2
f2
g2
h2
b1
c1
d
e1
f1
g1
h1
a8
b8
c8
d8
e8
f8
g8
h8
a7
b7
c7
d7
e7
f7
g7
a6
b6
c6
d6
e6
f6
a5
b5
c5
d5
e5
a4
b4
c4
d4
a3
b3
c3
a2
b2
1. Cut bitboard along a diagonal
2. Rearrange halves to make parallelogram
a1
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
12
Rotating a bitboard for a1…h8
a8
b8
c8
d8
e8
f8
g8
h8
a7
b7
c7
d7
e7
f7
g7
h7
a6
b6
c6
d6
e6
f6
g6
h6
h7
a5
b5
c5
d5
e5
f5
g5
h5
g6
h6
a4
b4
c4
d4
e4
f4
g4
h4
f5
g5
h5
a3
b3
c3
d3
e3
f3
g3
h3
e4
f4
g4
h4
a2
b2
c2
d2
e2
f2
g2
h2
d3
e3
f3
g3
h3
a1
b1
c1
d1
e1
f1
g1
h1
c2
d2
e2
f2
g2
h2
b1
c1
d1
e1
f1
g1
h1
a8
b8
c8
d8
e8
f8
g8
h8
a7
b7
c7
d7
e7
f7
g7
a6
b6
c6
d6
e6
f6
a5
b5
c5
d5
e5
a4
b4
c4
d4
a3
b3
c3
a2
b2
1. Cut bitboard along a diagonal
a1
3. Squash to make new square
http://csiweb.ucd.ie/Staff/acater/comp4031.html
2. Rearrange halves to make parallelogram
a8
b1
c2
d3
e4
f5
g6
h7
a7
b8
c1
d2
e3
f4
g5
h6
a6
b7
c8
d1
e2
f3
g4
h5
a5
b6
c7
d8
e1
f2
g3
h4
a4
b5
c6
d7
e8
f1
g2
h3
a3
b4
c5
d6
e7
f8
g1
h2
a2
b3
c4
d5
e6
f7
g8
h1
a1
b2
c3
d4
e5
f6
g7
h8
Artificial Intelligence for Games and Puzzles
13
Rotating a bitboard for a8…h1
1. Cut bitboard along a diagonal
a7
a6
b6
a5
b5
c5
a4
b4
c4
d4
a3
b3
c3
d3
e3
a2
b2
c2
d2
e2
f2
a1
b1
c1
d1
e1
f1
g1
a8
b8
c8
d8
e8
f8
g8
h8
b7
c7
d7
e7
f7
g7
h7
c6
d6
e6
f6
g6
h6
d5
e5
e6
g5
h5
e4
f4
g4
h4
f3
g3
h3
g2
h2
h1
3. Squash to make new square
http://csiweb.ucd.ie/Staff/acater/comp4031.html
a8
b8
c8
d8
e8
f8
g8
h8
a7
b7
c7
d7
e7
f7
g7
h7
a6
b6
c6
d6
e6
f6
g6
h6
a5
b5
c5
d5
e5
f5
g5
h5
a4
b4
c4
d4
e4
f4
g4
h4
a3
b3
c3
d3
e3
f3
g3
h3
a2
b2
c2
d2
e2
f2
g2
h2
a1
b1
c1
d1
e1
f1
g1
h1
2. Rearrange halves to make parallelogram
a7
b6
c5
d4
e3
f2
g1
h8
a6
b5
c4
d3
e2
f1
g8
h7
a5
b4
c3
d2
e1
f8
g7
h6
a4
b3
c2
d1
e8
f7
g6
h5
a3
b2
c1
d8
e7
f6
g5
h4
a2
b1
c8
d7
e6
f5
g4
h3
a1
b8
c7
d6
e5
f4
g3
h2
a8
b7
c6
d5
e4
f3
g2
h1
Artificial Intelligence for Games and Puzzles
14
Using rotated bitboards
Programs that use rotated bitboards do so for the sake of efficiency of the logic
for move generation and attack detection.
They use many precomputed bitboards, using memory to gain speed.
Whenever a move is made, a few more bitboards must be kept up to date:
• Regular file-oriented bitboards, for occupied, white, black, pawn etc.
often separating further: blackpawn, whitepawn, blackknight, …
• Flipped, rank-oriented versions of all of those.
• Rotated a1-h8 versions, and
• Rotated a8-h1 versions
With true 64-bit machine words, the bitwise operations are very fast.
With 32-bit words, even if a language allows 64-bit integers, benefits are less.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
15
Some online references
supertech.lcs.mit.edu/~heinz/dt/node8.html
(beware, rank & file confused in 1st paragraph)
www.onjava.com/pub/a/onjava/2005/02/02/bitsets.html?page=last&x-showcontent=text
atlanchess.com/html/rotated_bitboards.html
www.fzibi.com/cchess/bitboards.htm
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
16