February 2001 Programmer's Challenge

Trilite

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm ET, Tuesday, 6 February 2001 (deadline extended)

Tic-Tac-Toe is a trivial game. There are less than 9! possible games, far fewer if symmetry is taken into account, and certainly few enough for the outcome to be calculated in advance. But there is a variant of Tic-Tac-Toe that allows many more possible move sequences, and for which there may or may not be a guaranteed winning solution. This month you are going to have an opportunity to compete in the game of Trilite against your Challenge peers.

Trilite is like Tic-Tac-Toe in the sense that it is played on a 3x3 board, where two players alternate occupying squares with the objective of occupying three positions in a row. It differs from
Tic-Tac-Toe in that a player may occupy only three positions at a time. When a player occupies a fourth position, one of the three previously occupied positions, the one that has been occupied the longest, becomes vacant. So after any move, there are always three vacant positions on the board, and one more that is about to become unoccupied when the current player occupies one of the three vacant positions. Sounds simple, right?

The prototype for the code you should write is:

typedef enum {       /* numbering system for Board positions */
   kNoPosition=-1,
   kTopLeft=0, kTopCenter, kTopRight,
   kCenterLeft, kCenter, kCenterRight,
   kBottomLeft, kBottomCenter, kBottomRight
} BoardPosition;

typedef enum {       /* possible values for a Board Position */
   kEmpty=-1,
   kPlayer1Staying=0, kPlayer1Disappearing,
   kPlayer2Staying, kPlayer2Disappearing
} PositionValue;

typedef PositionValue Board[9];  /* state of the Board */

BoardPosition PlayTrilite(
   const Board triliteBoard,     /* current state of the Board */
   BoardPosition opponentPreviousPlay,
    /* the BoardPosition your opponent last played */
   int playerNumber,  /* 1 if you are player 1, 2 if you are player 2 */
   Boolean newGame    /* true the first time you are called for a new game */
);

For each game of Trilite, your PlayTrilite routine and that of your opponent will be called alternately until one of you wins by occupying three positions in a row, horizontally, vertically, or diagonally. The first time PlayTrilite is called for a new game, newGame will be set to TRUE. When newGame is TRUE, playerNumber will indicate whether you are the first (playerNumber==1) or second (playerNumber==2) player. Each time PlayTrilite is called, the BoardPosition last occupied by your opponent will be provided as opponentPreviousPlay. Finally, the current state of the Board will be provided to you as triliteBoard.

Trilite board positions have five possible values. Unoccupied positions have the value kEmpty. Positions occupied by player 1 have the value kPlayer1Staying or kPlayer1Disappearing, with the latter value distinguishing the position that will become empty following player 1’s next move. The position marked as disappearing is the one played 3 turns ago. Similarly, positions occupied by player 2 have the value kPlayer2Staying or kPlayer2Disappearing.

A sequence of moves works like this. Suppose the game has been going on for at least three pairs of turns, and it is player 1’s turn to play. The Board will have six occupied positions, three by player 1 and three by player 2. One position for each player will be marked as "disappearing" on the next move. Player 1 will occupy one of the three remaining unoccupied positions, and — at the same time — the kPlayer1Disappearing position will become kEmpty. If player 1 now occupies three positions in a row, s/he is the winner. Otherwise, player 2 then occupies one of the three empty positions and the kPlayer2Disappearing position becomes kEmpty. Note that a player may not reoccupy the position about to disappear — the opponent is the first player with a chance to occupy that position. The astute reader might detect one element of a potential game strategy here.

Test code for this Challenge is available.

You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".