mclure%sri-unix@sri-unix.UUCP (07/07/84)
[NOTE: this article will be published in an upcoming issue of the
ICCA Journal (International Computer Chess Association). It is being
made available to 'chess list' subscribers ahead of publication. Any comments
should be mailed to the author at Arpanet address M.MCLURE%LOTS-B@SU-SCORE,
M.MCLURE@SRI-UNIX, or Usenet address sri-unix!mclure]
Bit-map move generation
in chess
by Stuart M. Cracraft
Stanford University
copyright (c) 1984
1. Origin and current descriptions
Bit-map move generation is a time efficient, storage expensive
technique for generating lists of pseudo-legal moves for chess
positions. By pseudo-legal, we mean moves that would be allowed if it
were legal to leave a king in check after the move. Methods of
ensuring only legal moves can be applied to the pseudo-legal move list
to generate only legal moves or the check can be made if and when the
move is executed.
The technique was first described by Soviet researchers G.M.
Adel'son Vel-skii, V.L. Arlazarov, A.R. Bitman, A.A. Zhivotovskii, and
A.V. Uskov in Russian Mathematical Surveys, volume 25, number 2,
March-April 1970 [Adel70]. American researchers Hans Berliner of
Carnegie-Mellon University [Berl74], Larry Atkin and David Slate of
Northwestern University [Slat77] seem to have discovered it
simultaneously or shortly thereafter.
Current descriptions of the bit-map technique are inadequate.
The Soviet article is an obscure mathematical description of the
Soviet chess program in which the technique was first used. It is
presented in a highly mathematical framework that is difficult to
read. "En passant" and castling move generation are not included.
Other descriptions are less comprehensive but usually much
more readable; however, they often leave out move generation for
sliding pieces.
The purpose of this article is to describe the technique
completely. Acknowledgements go to T.A. Marsland for suggesting the
article and technical advice.
A familiarity with computer bit manipulation is assumed.
2. Bit maps
A bit-map is a 64 bit binary number that represents the chess
board. Each bit represents one square. The bits are organized in
rank-by-rank order so that the most significant bit is square a8 and
the least significant is h1. Other orderings can be used, but this
ordering has the advantage of being easily ordered into the
constituent ranks on the chess board without reordering the bits or
rows. An ordering with a1 as the origin is equally useful but has the
disadvantage that the resulting ranks must be read in reverse order to
generate a chess board from White's point-of-view.
Bit-maps represent useful information about the pieces or
squares on the chess board. Each set bit indicates the presence or
absence of a type of piece or a group of squares to which a given
piece may move from a given square.
Examples of bit-maps are: all squares to which a Knight on f3
may move in one turn, all squares to which a Queen on c3 may move in
one turn, all White Knights, all Black Pawns, all empty squares, all
occupied squares. More complex bit-maps are: all squares to which a
Knight on f3 may move in two turns, all squares on which a pinned piece
exists, "en passant" squares, and so forth.
The basic bit-maps that describe a position are called "location"
bit-maps. They indicate the location of friendly and enemy pieces by
piece-type. In octal, the initial chess position is:
White King: 10
Black King: 40000000000000000000
White Queens: 20
Black Queens: 100000000000000000000
White Knights: 102
Black Knights: 41000000000000000000
White Bishops: 44
Black Bishops: 220000000000000000000
White Rooks: 201
Black Rooks: 1004000000000000000000
White Pawns: 177400
Black Pawns: 3770000000000000000
If the computer is White, the friendly piece bit-map is
calculated by taking the logical "and" of the White location bit-maps.
The result is 177777. The enemy piece bit-map is calculated by doing
the same with the Black location bit-maps. The result is
1777770000000000000000. The empty square bit-map is calculated by
taking the exclusive "or" of the bit-map representing all squares and
the friendly piece bit-map. The result is 7777777776. Generating other
bit-maps and pseudo-legal moves is almost as efficient.
In addition to the location bit-maps, we require "move"
bit-maps that indicate to which squares a given piece may move from
any of the available 64 squares.
There are three types of chess pieces. The sliding pieces are
Bishops, Rooks, and Queens. The non-sliding pieces are Kings and
Knights. Pawns are a special case of sliding and non-sliding. Bit-map
move generation treats each of these three cases differently. One
software routine can be used for generating moves for each of these
three types.
3. Knights and Kings
To generate all moves for a Knight resting on square ij, we
retrieve the bit-map for a Knight on ij. This map represents all
squares to which a Knight on ij may move in one turn. If ij equals f3,
the map is 5021000010412 octal. We logically "and" this quantity with
the logical "not" of the bit-map representing all friendly pieces. The
resulting bit-map shows all squares where the Knight can move
pseudo-legally. This same two-step algorithm can be used to generate
moves for a King except that we retrieve the bit-map corresponding to
the legal moves for a King on square ij.
Castling is a special case and is treated later.
4. Pawns
To generate all single-square pawn advances, the bit-map of
all friendly pawns is shifted one rank forward. This results in a
bit-map of all squares directly in front of all friendly pawns. This
quantity is logically "anded" with the empty squares bit-map. The
result is a bit-map of all legal one-square advances of friendly Pawns.
Turning this bit-map into a list of legal moves is not so easy
as with Kings and Knights because the legal moves for multiple Pawns
are embedded within a single binary number. We must match each bit
with its origin bit.
To generate the two-square advances from the Pawn origin rank,
we take the bit-map of the proceeding calculation and logically "and"
it with the bit-map representing all Pawns on the second rank. This
latter bit-map can be obtained by "anding" the Pawn location bit-map
with a bit-map representing all second rank squares. The result of
these calculations is shifted forward yet another rank and "anded"
with the empty squares bit-map. We are left with a bit-map indicating
all two-square Pawn advances from the second rank.
To generate Pawn captures, we shift the friendly Pawns bit-map
one rank forward and one square left for Pawn captures to the left.
This is logically "anded" with the bit-map of enemy pieces. The result
is a bit-map indicating all captures of enemy pieces by friendly Pawns
toward the left. To get captures to the right, we start by shifting
forward one rank and to the right and proceed as above.
"En passant" can be generated by keeping a bit-map for each
side that indicates the last en passant square passed over by a
friendly Pawn, but as an enemy piece in the enemy piece bit-map.
5. Bishops, Rooks, and Queens
To generate moves for pieces such as the Bishop, Rook, and
Queen is more difficult than other types of move generation. This is
because a sliding piece has unlimited scope and radiates in many
different directions. It is not sufficient to use the squares
representing all squares to which the piece can move in one turn,
because there may be enemy or friendly pieces that block the movement,
resulting in squares beyond the blocker that are inaccessible to the
moving piece being counted as legal.
Four auxillary arrays are required. All are constructed at
startup. The Bishop array contains a bitmap for each of the 64 squares
and each of the four rays that extend from the Bishop to the edge of
the board. Similarly, the Rook array contains a bitmap for each of the
64 squares and each of the four rays that extend from the Rook to the
edge of the board. The Queen array is similar except that there are 8
rays.
The final auxillary array is two-dimensional and is indexed by
the 64 possible squares on the board. Each array location contains a
bitmap indicating the moves from the given square to each of the other
63 possible squares given that it is possible to move a sliding piece
to that square in one move. If not, the bitmap is null.
We can use these arrays to find the legal moves for a Bishop
at f3. We calculate the blocker locations for each of the 4 rays
emanating from the Bishop. If no blockers exist, the entire ray in
question is taken as the legal moves in that direction. Now we have
f3 and the blocker square. These two are used as indices into the
distance array described above. The bitmap returned is a list of
squares. If the blocker square is in the enemy piece list, the bitmap
represents all legal moves in that direction for the Bishop. If the
blocker square is in the friendly piece list, we must "exclusive or"
it from the bitmap so that we eliminate the illegal move of a friendly
piece onto another square with a friendly piece.
As each of these rays is calculated, it is added to a bitmap
variable. Once done, the bitmap variable contains all legal moves of
the piece from the current square.
6. Castling
For castling, we must ensure that
1) squares the King passes over and to are not attacked by
enemy pieces and are empty
2) the King is not in check
3) the King and Rook have not moved before.
To calculate conditions #1 and #2, it is helpful to maintain an
auxiliary array. This 64 member array of bit-maps shows all enemy
squares that attack the current square. It is called the "attack map."
If the members of the attack map array location representing the
current King location and the squares the King will pass over all have
zero bits set for the opposite color attackers, we know that #1 and #2
are satisfied if the squares the King passes over are empty.
To calculate condition #3, we maintain a count for each Rook
and King on the board of the number of times it has moved. As long as
the King and Rook in question have never moved, condition #3 is
satisfied.
A secondary attack map is frequently maintained. It is a 64
member array of bit-maps showing all squares to which the piece on the
current square, if any, may move.
7. Why the bit-map technique is preferred
The bit-map move generation technique emphasizes the strongest
characteristic of the modern computer: logical computation with bits.
In no other area of calculation is a computer faster than at the bit
level where "ands", "ors", "exclusive ors", "complements", and
"inclusive ors" are the order of the day. These are frequently carried
out at the rate of 10^6 bits per second or more.
8. A timing test of the bit-map technique
The above scheme was implemented in June, 1984 on a Stanford
University computer, a Digital Equipment Corporation 2060. It was
written in Pascal. Bitmaps were implemented using Pascal sets, a very
convenient software feature for this circumstance. No attempt was made
to optimize the Pascal code.
Although Pascal is a relatively inefficient language, the
resulting timing tests were reasonable. The timing test used the
complex position arising from the double pawn-sacrifice of the
Blackmar-Diemer Gambit, 1 d4 d5 2 e4 dxe4 3 Nc3 Nf6 4 f3 exf3 5 Qxf3
Qxd4 6 Be3 Qb4. This notoriously hoary gambit is known for extremely
sharp positions and is among the most tactical of opening systems.
Not including castling and "en passant", White has 52 legal moves and
Black has 45 legal moves. Our routines did not implement castling and
"en passant" at the time of the test. The timing test consisted of
generating the moves for both White and Black a total of 10000 times
for this position. The total cpu time was 338.863 seconds. Since
970000 moves were generated and stored, the rate is 2863 moves per cpu
second or 1 move every .00035 seconds. For a typical chess position,
containing 38 moves for the side to move, 75 move generations are made
in one cpu second.
In assembly language, the implementation would be at least one
order of magnitude faster and probably much more. Also, a machine with
a 64-bit word would reduce the number of logical operations by 50%,
because two words are required on the above machine for storing a
bitmap. Most chess programs using the bit-map approach only generate
a few moves at a time rather than all the moves at once. If a cutoff
in the search tree occurs, only a few moves need to be generated.
These modifications to the bit-map scheme reduce its calculation time
to significantly smaller fractions of the times mentioned above.
9. The original move generation technique
The original move generation technique is the traditional
Shannon approach [Shan50]. Here, the chess board is represented by a
one-dimensional array of memory locations. Moves for pieces are
calculated by adding an increment to the index representing the
piece's array location. The new location so obtained is inspected. If
it contains a certain value, it is empty or occupied by an enemy
piece, and the move is pseudo-legal. If it contains another value, it
is the edge of the board or a friendly piece and is illegal.
Calculating moves for sliding pieces involves spreading out on the
associated rays, one square at a time, looking at each memory
location. Complex code is required to handle "en passant" and castling
moves.
Naturally, such a technique involves vastly more memory accesses
and arithmetic operations than the bit-map approach. Where the bit-map
may involve a handful of logical operations, the Shannon approach can
use hundreds or even thousands of relatively expensive arithmetic and
memory-accessing operations.
The chief advantage of the Shannon approach is that it is easy
to program and uses little space. It is also a good method for
introducing the computer chess newcomer to move generation. The
bit-map approach is often perceived as unusual and difficult to
understand.
Other move generation techniques have been realized, some
being microcoded in hardware. These implementations are often
blindingly fast compared to their traditional high-level or assembly
language cousins, but they do not exist in great numbers at present.
Bibliography
Adel[70] Adel'son-Vel-skii, G.M., Arlazarov, V.L., Bitman, A.R., Zhivotovskii,
A.A., and Uskov, A.V., Russian Mathematical Surveys, volume 25, number
2, March-April 1970.
[Berl74] Berliner, H., Chess as Problem Solving: The Development of a Tactics
Analyzer, unpublished doctoral thesis, Carnegie-Mellon University,
Pittsburgh, 1974.
[Frey77] Frey, P.W., "An Introduction to Computer Chess," Chess Skill in Man
and Machine, Frey, P.W. (editor), New York, Springer-Verlag, 1977.
[Shan50] Shannon, C.E., "Programming a Computer for Playing Chess,"
Philosophical Magazine, volume 41, 1950, pages 256-275.
[Slat77] Slate, D.J. and Atkin, L.R. "Chess 4.5 - The Northwestern University
Chess Program," Chess Skill in Man and Machine, Frey, P.W., (editor),
New York, Springer-Verlag, 1977.