November 1997 Programmer's Challenge

PENTE®

Reaching once again into the closet where we store board games, I found the game of Pente®, The board physically resembles the board used in GO, but the game strategies are simpler.

Pente® is played by two players who alternate placing stones on a 19x19 grid. The objective is to win the game by getting five or more stones in a row or, alternatively, by capturing five or more pairs of your opponent's stones. Your Challenge is to write code that will play the game of Pente® and accumulate the most points (described below) in the minimum time.

The prototype for the code you should write is:

typedef struct Capture {

  Point stone1;

  Point stone2;

} Capture;

void InitPente(

  long boardHalfSize  /* e.g., 9 for a 19x19 board */

                     /* all coordinates between -boardHalfSizeand +boardHalfSize */

);

void Pente(

  Point opponentsMove,      /* your opponent moved here */

  Boolean playingFirst,     /* ignore opponentMove */

  Point *yourMove,          /* return your move here */

  Capture claimCaptures[],  /* return coordinates of captured pairs here */

  long *numCaptures,        /* return number of claimCaptures here */

  Boolean *claimVictory     /* return true if you claim victory with this move */

);

void TermPente(void); /* deallocate any dynamic storage */

Captures take place by bracketing two adjacent stones of your opponents. Given the position

---BWW---

... Black can capture the two White stones by playing ...

---BWW---

---BWWB--

... after which the two White stones are removed ...

---BWW---

---B B--

Captures can occur horizontally, vertically, or diagonally. Note that no capture occurs if White moves into the unoccupied square below:

---BW-B--

Multiple captures can occur on a single move.

The game ends when one side captures five pairs of the opponent's stones, or when one side places five stones in a straight line, either horizontally, vertically, or diagonally. When one side obtains an unblocked row of four stones, called a tessera, a win is imminent. Therefore, an unblocked row of three stones, called a tria, is a serious threat that should be blocked unless a stronger offensive move exists.

The first player's first move must be at the origin (0,0).

To neutralize the advantage that the first player has, the first player's second move is restricted to be three or more intersections away from the center of the board (i.e., the h or v coordinates of first player's second move must both be greater than or equal to 3 in absolute value).

At the start of the game, your InitPente routine (and that of your opponent) will be called with the half-width of the board in boardHalfSize (between 9 and 15, inclusive). The Pente routines will then be alternately called, providing the location of your opponentsMove (unless you are playingFirst). You should place a stone in an unoccupied location and return that location in yourMove. In addition, if your move captures any adjacent pairs of your opponent's stones, you should report the number of captures in numCaptures, and the locations of the captured pairs in claimCaptures. If your move results in victory, either by achieving 5 of your stones in a row, or a cumulative capture of 5 pairs of your opponent's stones, you should set claimVictory to true. At the end of the game, TermPente will be called, where you should deallocate any dynamically allocated storage.

Board coordinates are expressed as distance from the center square in ordered (v,h) pairs, so that the center intersection is at (0,0), and the corners of the standard board are at (-9,-9), (-9,9), etc.

At the end of the game, points will be awarded as follows:

  5 points for the player who achieved 5 stones in a row

  1 point for each capture

  1 point for each distinct sequence of 4 stones in a row remaining on the board

One point will be deducted for each second of execution time used during a player's turns, including the time taken by the InitPente and TermPente routines. Both the game winner and the game loser will accumulate points. It is possible to earn negative points. The Challenge winner will be the entry that accumulates the most points in a round-robin tournament of all entries, where each entry plays each other entry at least twice, half of the time playing first and half playing second.

Your code may allocate up to 10MB of dynamic storage, including both explicit calls to NewPtr/malloc and allocation of dynamic objects. This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.

Pente® is published by Pente Games, Inc.