Feb 01 Challenge
Volume Number: 17
Issue Number: 2
Column Tag: Programmer's Challenge
Programmer's Challenge
By Bob Boonstra, Westford, MA
Trilite
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
typedef enum { /* possible
values for a Board Position */
kEmpty=-1,
kPlayer1Staying=0, kPlayer1Disappearing,
kPlayer2Staying, kPlayer2Disappearing
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 positions that will become
empty following player 1's next move. 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.
Entries will compete against one another in a tournament structured so that each entry
plays each other entry an even number of times, half playing first, and half playing
second. If the number of entries is large, some other fair tournament scheme will be
used. A game will be considered drawn when a time limit and a move count limit, not
specified as part of the problem statement, are exceeded.
The winner will be the entry that scores the most points, where each game won is
worth 1000 points, each game drawn is worth 500 points, and 1 point is deducted for
each millisecond of execution time. The Challenge prize will be divided between the