Aug 97 Challenge
Volume Number: 13
Issue Number: 8
Column Tag: Programmer's Challenge
Programmers Challenge
by Bob Boonstra, Westford, MA
Stratego®
In recognition of Deep Blue's chess victory over Garry Kasparov (and I would have said
"In celebration of...", except that I have mixed feelings about the outcome), we return
to our series of board game tournament Challenges. This month, you will be writing a
program to play the game Stratego. Stratego is a board game played on a rectangular
10x10 grid. Each player begins the game with 40 pieces, one of which is a Flag. The
object of the game is to find and capture the opponent's flag.
The pieces provided to each player at the beginning of the game, in order of descending
rank, are as follows (quantity in parentheses): Marshall (1), General (1), Colonels
(2), Majors (3), Captains (4), Lieutenants (4), Seargent (4), Miners (5), Scouts
(8), and Spy (1). In addition, each player is given Bombs (6) and a Flag (1). At the
start of play, each player places his pieces in the four rows nearest his side of the
board such that their rank, which is visible from one side of a piece but not from the
other, is hidden from the opponent. Players alternate making moves, with Red moving
first, then Blue. Each turn consists of either moving a piece into an open square, or
striking an opponent's piece in an adjacent square. Except for the Scout, Flag, and
Bomb pieces, each piece can move one square forward, backward, or sideways (but not
diagonally) on a given turn. Flags and Bombs cannot move at all. Scouts can move any
number of open squares forward, backward, or sideways (but again, not diagonally).
If a piece is moved into an adjacent square occupied by an opponent, the move is
referred to as a "strike", which results in the lower ranking piece being removed
from the board, and the higher ranking piece moving into the square formerly occupied
by the losing piece. When both pieces involved in a strike are of equal rank, both
pieces are removed. A Marshall defeats a General, a General defeats a Colonel, etc. The
Spy is the lowest ranking piece, and is defeated by any other piece, except that a Spy
defeats a Marshall when the Spy initiates the strike. Any piece except a Miner striking
a Bomb is removed (and the Bomb remains in its original position). When a Miner
strikes a Bomb, the Bomb is removed and the Miner moves into the square formerly
occupied by the Bomb. The Flag and the Bomb cannot move and cannot initiate a strike.
The game ends when a player strikes the opponent's Flag.
Your code will be competing in a round-robin tournament against other Challenge
entries. The prototype for the code you should write is:
#define kBoardSize 10
typedef enum { kUnknown=0,
kMarshall=1,kGeneral,kColonel,kMajor,kCaptain,
kLieutenant,kSergeant,kMiner,kScout,kSpy
typedef enum {kRed=1,kBlue=2} PlayerColor;
typedef struct PieceType {
PieceRank thePieceRank; /* rank of a piece */
PlayerColor thePieceColor; /* color of a piece */
typedef PieceType Board[kBoardSize][kBoardSize];
/* Used to provide test code with board configuration. Red starts
in rows 0..3, Blue starts in rows 6..9 */
/* Squares [4][2], [4][3], [4][6], [4][7] and [5][2], [5][3], [5][6],
[5][7] are water