Chess is played on an 8x8 board. One player has white pieces, one
has black pieces. Each player's pieces include eight pawns, two rooks, two
knights, two bishops, a king and a queen. The various pieces have
different rules for movement. Players move alternately until one player's
king is in a position from which it cannot escape but must be taken, or
there is a draw. There are a number of rules that lead to a draw, all
beyond the scope of this problem. White moves first.
A game is recorded as a log of the numbered moves of pieces, first
white then black. The Portable Game Notation (PGN) standard includes
additional descriptive information about the players and venue.
There are two notations for logging a chess game. The newer,
algebraic notation and the older
descriptive notation. We will write a program that
will process a log in either notation and play out the game, showing the
chess board after each of black's moves. It can also be extended to
convert logs to completely standard PGN notation.
Algebraic Notation
We'll present the formal definition of algebraic notation
including Algebraic Notation (LAN) and Short Algebraic
Notation (SAN). We'll follow this with a summary and
some examples. This section will end with some Algorithm R, used to
resolve which of the available pieces could perform a legal move.
Definition
Algebraic notations uses letters a-h for the
files (columns across the board) from white's left to right, and
numbers for the ranks (rows of the board) from white (1) to black
(8).
Piece symbols in the log are as follows:
Piece
Symbol
Move Summary
Pawn
(omitted)
1 or 2 spaces forward
Rook
R
anywhere in the same rank or same file
Knight
N
2 in one direction and 1 in the other
“L-shaped”
Bishop
B
diagonally, any distance
Queen
Q
horizontal, vertical or diagonal, any distance
King
K
1 space in any direction
The game beings in the following starting position. For white
the pieces are arranged as follows:
White
Black
Piece
a1
a8
rook
b1
b8
knight
c1
c8
bishop
d1
d8
queen
e1
e8
king
f1
f8
bishop
g1
g8
knight
h1
h8
rook
a2-h2
a7-h7
pawns
There are two forms of algebraic notation: short (or standard)
algebraic notation (SAN), where only the destination is shown, and
long algebraic notation (LAN) that shows the piece, the starting
location and the destination.
The basic syntax for LAN is as follows:
[P]frmfr[n]
P is the piece name (omitted for
pawns), f is file (a-h),
r is rank (1-8),
m is move (- or
x) and n is any notes
about the move (+, #,
!, !!, ?,
??). The notes may include = and
a piece letter when a pawn is promoted.
Short notation omits the starting file and rank unless they are
essential for disambiguating a move. The basic syntax is as
follows:
[P]
[m]
[d]fr[n]
The move, m, is only specified for a
capture (x). The optional
d is either a file (preferred) or a rank or
both used to choose which piece moved when there are multiple
possibilities.
In both notations, the castle moves are written
O-O or O-O-O (capital letters,
not numbers). Similarly, the end of a game is often followed with a
1-0 (white wins), 0-1 (black
wins), 1/2-1/2 (a draw), or *
for a game that is unknown or abandoned.
Each turn is preceeded by a turn number. Typically the number
and a . preceeds the white move. Sometimes (because
of commentary), the number and ... preceed the
black move.
The PGN standard for notes is $ and a number,
common numbers are as follows:
1 good move (traditional “!”)
2 poor move (traditional “?”)
3 very good move (traditional “!!”)
4 very poor move (traditional “??”)
Each piece has a legal move. This is a critical part of
processing abbreviated notation where the log gives the name of the
piece and where it wound up. The legal moves to determine which of two
(or eight) pieces could have made the requested move. This requires a
simple search of pieces to see which could have made the move.
A pawn moves forward only, in its same file. For white, the rank
number must increase by 1. It can increase by 2 when it is in its
starting position (rank 7 for white or 2 for black). For black, the
rank number must decrease by 1 or 2. A pawn captures on the diagonal:
it will move into an adjacent file and forward one rank, replacing the
piece that was there. There is one origin for all but the opening pawn
moves (one rank back on the file in which the pawn ended its move);
one origin for an opening pawn move that lands in rank 4 or 5 (two
ranks back on the file where the pawn ended its move); two possible
origins for any pawn capture (one position on a file adjacent to the
one in which the pawn ended its move).
A rook moves in ranks or files only, with no limit on distance.
There are 16 possible origins for any rook move, including the entire
rank or the entire file in which the rook ended its move.
A knight makes an “L-shaped” move. It moves two
spaces in one direction, turns 90-degrees and moves one more space.
From g1, a knight can move to either f3 or h3. The rank changes by 2
and the file by 1; or the file changes by 2 and the rank changes by 1.
There are 8 places a knight could start from relative to its final
location.
A bishop moves diagonally. The amount of change in the rank must
be the same as the change in the file. There are 16 places a bishop
can start from on the two diagonals that intersect the final
location.
The queen's move combines bishop and rook: any number of spaces
diagonally, horizontally or vertically. There are 16 places on the
diagonals, plus 16 more places on the horizontals and verticals where
the queen could originate. Pawns that reach the opposite side of the
board are often promoted to queens, meaning there can be multiple
queens late in the game.
The king is unique, there is only one. The king can only move
one space hoizontally, vertically or diagonally.
The king and a rook can also engage in a move called
castling: both pieces move. When the king and
the closest rook (the one in file h) castle, this is king
side and annoted O-O. The king moves
from file e to file g and the rook from fiel h to file f. When the
king and the queen's side rook (the one in file a) castle, this is
annotated O-O-O. The king moves from file e to file
c and the rook move from file a to file d. Castling can only be
accomplished if (a) neither piece has moved and (b) space between them
is unoccupied by other pieces. Part a of this rule requires that the
game remember when a king or rook moves, and eliminate that side from
available castling moves. Moving the rook in file a eliminates
queen-side castling; moving the rook in file h eliminates king-side
castling. Moving the king eliminates all castling.
Summary and Examples
Here's a suymmary of the algebraic notation symbols used for
annotating chess games. This is followed by some examples.
Symbol
Meaning
a-h
file from white's left to right
1-8
rank from white to black
R, N, B, Q, K
rook, knight, bishop, king, queen
-
move (non-SAN)
x
capture; the piece that was at this location is removed
+
check, a note that the king is threatened
#
checkmate, a note that this is the reason for the end of the
game
++
checkmate (non-SAN), a note that this is the reason for the
end of the game
=
promoted to; a pawn arriving at the opposite side of the
board is promoted to another piece, often a queen.
0-0
castle on the king's side; swap the king and the rook in
positions e1 and h1 (if neither has moved before this point in
the game)
0-0-0
castle on the queen's side; swap the king and the rook in
positions e1 and a1 (if neither has moved before this point in
the game)
e.p.
en passant capture (non-SAN), a note that a pawn was taken
by another pawn passing it. When a pawn's first move is a two
space move (from 7 to 5 for black or 2 to 4 for white) it can be
captured my moving behind it to the 6th rank (white taking
black) or 3rd rank (black taking white).
ep
en passant capture (non-SAN), see
e.p.
?, ??, !, !!
editorial comments (non-SAN), weak, very weak, strong, very
strong
Here's parts of an example game in abbreviated notation:
e4 e5. White pawn moves to e4 (search e3 and e2 for the pawn that
could do this); black pawn moves to e5 (search e6 and e7 for a
pawn that could do this)
Nf3 d6. White knight moves to f3 (search 8 positions: g1, h2, h4,
g5, e5, d4, d2, e1 and g1 for the knight that could do this);
black pawn moves to d6 (search d7 and d8 for the pawn).
d4 Bg4. White pawn moves from d4 (search d3 and d2 for the pawn);
black bishop moves to g4 (search the four diagonals: f5, e6, d7,
c8; h5; h3; f3, e3, and d3 for the bishop that could do
this).
dxe5 Bxf3. A white pawn in d takes a piece at e5, the pawn must have
been at d4, the black pawn at e5 is removed; a black bishop
takes a piece at f3 (search the four radiating diagonals from
f3: e4, d5, c6, b7, a8; g4, h5; g2, h1; e2, d1).
Qxf3 dxe5. The white queen takes the piece at f3; the black pawn in
d4 takes the piece in e5.
Algebraic notation is terse because it is focused on a human
student of chess. It contains just enough information for a person to
follow the game. Each individual move cannot be interpreted as a
stand-alone (or “context-free” statement). Each move's
description only makes sense in the context of the game state
established by all the moves that came before it. Therefore, in order
to interpret a log of chess moves, we also need to maintain the state
of the chess board.
Given that we have a model of the chess board, Algorithm G can
locate the pieces and execute the moves an entire game.
Procedure 42.1. Algoritm G
(Resolve chess moves in SAN notation,
playing out the entire game.) We are given a block of text with a
sequence of chess turns. Assume that line breaks have been removed
and the game ending marker has been removed from the block of
text.
Parse turn into moves. Locate move number, white move and black move. Lines that
don't have this form are some kind of commentary and can be
ignored.
Parse each move. For each move, parse the move locating the piece
(R, B,
N, Q,
K, pawn if none of these), optional file
(a-h) or rank
(1-8) for the source, the
optional x for a capture, the destination
file (a-h) and rank
(1-8), and other material
like + or # for checks,
=x for promotions,
or !, !!,
?, ?? for editorial
comments.
Castling? If the move is simply 0-0 or
O-O-O, move both the king (in file e) and the
appropriate rook. For 0-0 it is the rook in
file h moves to f, the king moves from e to g. For
O-O-O it is the rook in file a moves to d,
the king moves from e to c.
Fully specified from location? If a two-character from-position is given, this is the
starting location. Execute the move with step 7.
Partially specified from location? If a one-character from-position is given (a-h or 1-8),
restrict the search for the source to this rank for file. Use
the piece-specific version of Algorithm S with rank or file
restrictions for the search. After the starting location is
found, execute the move with step 7.
Omitted from location? Search all possible origins for the from-position for this
piece. Each piece has a unique search pattern based on the
piece's movement rules. Use the piece-specific version of
Algorithm S with no restrictions for the search. After the
starting location is found, execute the move with step 7.
Execute move. Move the piece, updating the state of the board, removing
captured pieces. Periodically during game processing, print the
board position. The board, by the way, is always oriented so
that a1 is a dark square in the lower-left.
Next move. Loop to step 2, processing the black move after the white
move in this turn. If the black move is omitted or is one of the
ending strings, skip the black move.
Next turn. Loop to step 1, processing the next turn. If the turn
number is omitted or is one of the ending strings, this is the
end of the game.
We have to design six different kinds of searches for possible
starting pieces. These searches include pawns, rooks, knights, bishops
queens and the king. We'll provide formal algorithms for pawns and
rooks, and informal specifications for the other pieces.
Procedure 42.2. Algorithm P
(Search for possible pawn starting locations.) Given a
destination location, piece color, and optional restrictions on
starting rank or starting file.
First move. If the destination is rank 4 (white) or rank 5 (black),
search two spaces back for the first move of a pawn (from rank 7
or rank 2). If moving this piece will not put the king into
check, this is the stating location.
Previous space. Search the previous space (rank -1 for white, rank +1 for
black) for a move. If moving this piece will not put the same
color king into check, this is the stating location.
Capture. Search the adjacent files one space back for a pawn which
performed a capture. If moving this piece will not put the same
color king into check, this is the stating location.
Procedure 42.3. Algorithm R
(Search for possible rook starting locations.) Given a
destination location, piece color, and optional restrictions on
starting rank or starting file.
To Right. Set r ← +1.
Target. Target position has file offset by r.
Check. If this is off the board, or a non-rook was found, skip to
4. If moving this piece will not put the king into check, this
is the stating location.
Loop. Increment r. Repeat from step 2.
To Left. Set r ← -1.
Target. Target position has file offset by r.
Check. If this is off the board, or a non-rook was found, skip to
8. If moving this piece will not put the king into check, this
is the stating location.
Loop. Decrement r. Repeat from step 5.
To Black. Set r ← +1.
Target. Target position has rank offset by r.
Check. If this is off the board, or a non-rook was found, skip to
12. If moving this piece will not put the king into check, this
is the stating location.
Loop. Decrement r. Repeat from step 9.
To White. Set r ← -1.
Target. Target position has rank offset by r.
Check. If this is off the board, or a non-rook was found, we have
a problem. If moving this piece will not put the king into
check, this is the stating location.
Loop. Decrement r. Repeat from step 13.
Procedure 42.4. Algorithm N
(Search for possible knight starting locations.) Given a
destination location, piece color, and optional restrictions on
starting rank or starting file.
Search the eight possible starting positions for a knight's
move. Four of the positions have a file offset of +1 or -1 and
rank offsets of +2 or -2. The other four positions have file
offsets of +2 or -2 and rank offsets of +1 or -1.
When evaluating a piece, moving this piece cannot put the
king into check.
Procedure 42.5. Algorithm B
(Search for possible bishop starting locations.) Given a
destination location, piece color, and optional restrictions on
starting rank or starting file.
Search radially out the diagonals until edge of board or an
intervening piece or the correct bishop was found. This algorithm
is similar to the rook algorithm, except the offsets apply to both
rank and file. Applying +1 to both rank and file moves north-east;
applying -1 to both rank and file moves south-west. Applying +1 to
rank and -1 to file moves south east; applying -1 to rank and +1
to file moves north west.
When evaluating a piece, moving this piece cannot put the
king into check.
Procedure 42.6. Algorithm Q
Search for possible queen starting locations.) Given a
destination location, piece color, and optional restrictions on
starting rank or starting file.
Search radially out the ranks, files and diagonals until
edge of board or an intervening piece or the correct queen was
found. This combines the bishop and rook algorithms.
When evaluating a piece, moving this piece cannot put the
king into check.
Procedure 42.7. Algorithm K
Search for possible king starting locations.) Given a
destination location, piece color, and optional restrictions on
starting rank or starting file.
Search the 8 adjacent locations. These are all combinations
of -1, 0, +1 for rank offset and -1, 0, +1 for file offset;
skipping the one combination with a 0 offset to rank and a 0
offset to file.
Published under the terms of the Open Publication License
