August 1997 Programmer's Challenge

Stratego®

Mail solutions to: progchallenge@mactech.com
Due Date: MIDNIGHT, EDT, 1 August 1997

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 or the code you should write is:

#define kBoardSize 10

typedef enum { kUnknown=0,

  kMarshall=1,kGeneral,kColonel,kMajor,kCaptain,

  kLieutenant,kSergeant,kMiner,kScout,kSpy,

  kBomb,kFlag

} PieceRank;

typedef enum {kRed=1,kBlue=2} PlayerColor;

typedef struct PieceType {

  PieceRank  thePieceRank;    /* rank of a piece */

  PlayerColor thePieceColor;  /* color of a piece */

} PieceType;

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 and cannot be occupied */

typedef struct PiecePosition {

  long row; /* 0..9 */

  long col; /* 0..9 */

} PiecePosition;

typedef struct MoveResult {

  PieceType attacker;       /* after a strike, returns rank of attacker */

  PieceType defender;       /* after a strike, returns rank of defender */

  Boolean attackerRemoved;  /* true after a strike against a piece of equal or greater

                              rank, or against a bomb when the attacker is not a Miner */

  Boolean defenderRemoved;  /* true after a strike by a piece of equal or greater rank, or

              against a bomb when the attacker is a Miner, or against a Marshall by a Spy */

  Boolean victory;          /* true after a strike against the Flag */

  Boolean legalMove;        /* true unless you

       - move into an occupied square, or

       - move or strike in a direction other than forward, backward, or sideways, or

       - move more than one square (except Scouts), or

       - move a Bomb or a Flag,

       - move into Water, or

       - strike a square not occupied by an opponent, or

       - make any other illegal move */

} MoveResult;

void PositionPieces(

  void *privStorage,       /* 1MB of preinitialized storage for your use */

  PlayerColor playerColor, /* you play red or blue, with red playing first */

  Board *theBoard          /* provide the initial position of your pieces */

);

typedef void (*ReportYourMove)(

                           /* Callback to inform test code of move and get results */

  PiecePosition *moveFrom, /* piece you are moving or using to strike */

  PiecePosition *moveTo,   /* destination square or square being struck */

  Boolean strike,          /* false indicates a move, true indicates a strike */

  MoveResult *results      /* returns identity of struck piece and other info */

);

typedef void (*GetOpponentMove)(

                           /* Callback to get results of opponents last move */

  PiecePosition *moveFrom, /* piece opponent moved or used to strike */

  PiecePosition *moveTo,   /* destination square or square struck */

  Boolean *strike,         /* false indicates a move, true indicates a strike */

  MoveResult *results      /* returns identity of struck piece and other info */

);

Boolean /* TRUE claims victory or illegal opponent move */ MakeAMove(

  void *privStorage,         /* 1MB of storage from PositionPieces */

  PlayerColor playerColor,   /* you play red or blue, with red playing first */

  GetOpponentMove *GetMove,  /* callback used to find about opponents last move */

  ReportYourMove *ReportMove /* callback used to make a move */

);

Your PositionPieces routine will be called at the beginning of each game so that you provide the initial position of your pieces. If your playerColor is kRed, you should occupy rows 0..3 of the board, otherwise you should occupy rows 6..9. You should set theBoard[row][col].thePieceColor to your playerColor and theBoard[row][col].thePieceRank to the PieceRank you are placing on each square. As indicated in the typedef for theBoard, eight squares in the middle rows of the board are water and cannot be occupied by pieces of either side.

Note that theBoard is used only to pass your initial position to the test code - you may choose your own data structure to keep track of your pieces and the knowledge gained about your opponent's pieces as the game progresses. PositionPieces will be provided with 1MB of preallocated storage pointed to by privStorage. This storage will be initialized to zero before PositionPieces is called and will persist between moves. You should not allocate any additional dynamic storage beyond that provided by privStorage. Small amounts of static storage are permitted.

The normal move sequence consists of finding out via the GetMove callback where your opponent moved on the previous turn, determining your next move, and finding out the results of that move via the ReportMove callback. Your MakeAMove code should include something like this:

  if (!firstMove || (playerColor==kBlue)) {

    (*GetMove)(&opponentMoveFrom,&opponentMoveTo,

                    &opponentStrike,&opponentResult);

  }

  /* respond to opponent move, and calculate your move */

(*ReportMove)(&myMoveFrom,&myMoveTo,myStrike,&myResult);

  /* process results of move */

You provide ReportMove with the location from which and to which you are moving (moveFrom and moveTo, respectively), and set strike to TRUE if your move strikes one of your opponent's pieces. The callbacks will populate a MoveResult data structure to reflect the results of your opponent's last move or your current move. Flags are set to indicate whether the attacker or defender (or both) are removed as the result of an attack, and PieceType fields are populated when an attack reveals information about a piece. The key to winning a game is properly interpreting the movement and tactics of your opponent, deciding when and where to strike, and using the information gained in those strikes to best advantage.

MakeAMove should return TRUE when you claim victory or when the callback indicates that an illegal move has been made.

The Challenge will be scored by a tournament where each entry plays against each other entry an even number of times, half playing first and half playing second. Another fair tournament schedule might be used if a large number of entries are received. For each game, the winner will earn game points for the victory, minus an amount based on the execution time used to compute the moves, as follows:

game points = 10 - execution time in seconds

The loser will earn zero points and will not be penalized for the execution time expended in defeat. No points will be awarded for a tie. The player with the most total points for all games in the tournament will be the winner.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.

Stratego is ® 1960 in the U.S. Patent Office and is (c) 1961 by the Milton Bradley Company.

A number of questions about this Challenge have been answered on the Programmer's Challenge mailing list. Check here for the Q&A archive.