July 1996 Programmer's Challenge

Connect IV

Mail solutions to: progchallenge@mactech.com

Due Date: 1 July 1996

This month, your Challenge is to write code for a well-known game that will compete against other Challenge entries, as well as against the clock. The game board consists of an NxM array into which two players alternate inserting pieces. Pieces are inserted into the top of a column in the vertically oriented board, so that they drop into the lowest unoccupied cell of that column. The objective is to be the first player to arrange 4 or more pieces into a vertical, horizontal, or diagonal line.

The winner of this Challenge will be determined by a round-robin tournament in which each entry competes against each other entry an even number of times, half of the time playing with the first move, and half playing with the second move. (If the number of entries makes a full round-robin tournament impractical, I'll use another fair tournament scheme.) Each tournament victory will earn two points for the winning entry, and each tie earns one point. The entry with the greatest number of tournament points wins the Challenge. Ties will be broken by execution time, code size, etc.

The prototype for the code you should write is:

long /*yourMove*/ ConnectMove (
  long numCols,      /* number of columns in the game board */
  long numRows,      /* number of rows in the game board */
  void *privStorage, /* preallocated storage for your use */
  long prevMove,  /* column where opponent last moved, 0 .. numCols-1 */
  Boolean newGame,   /* TRUE if this is your first move in a new game */
  Boolean *victory   /* set to TRUE if you claim victory */
                     /*   this move, otherwise set to FALSE */
);
 

For your first move in a new game, your ConnectMove code will be called with newGame set to TRUE. If your opponent made the first move in this game, prevMove will be set to the (origin zero) column that the opponent selected as the first move. If you are to make the first move, prevMove will be set to -1. In the call for the first move of a new game, you will also be provided with a pointer privStorage to 1MB of memory, already initialized to zero, for your use during that game. Finally, the initial call will provide the number of columns (numCols) and rows (numRows) in the board for that game. The number of rows and columns will each be larger than 6 and less than 64.

Alternating calls will be made to your ConnectMove routine and the opposing ConnectMove routine. For the second and subsequent moves in each game, newGame will be set to FALSE, and the values of numCols, numRows, and privStorage will be the same as in the initial call. Each time ConnectMove is called, you should evaluate the move made by your opponent (provided in prevMove) and return the column into which you make your move as the function result. If you believe you have won the game, you should set *victory to TRUE; otherwise you should set *victory to FALSE. Falsely claiming victory or making an illegal move, such as trying to insert a game piece into a column that is already filled, will result in forfeiting that game.

For this Challenge, you may dynamically allocate additional storage beyond that provided by privStorage, provide you deallocate it before returning after each move. You may not use any static storage beyond that provided by privStorage.

To conduct the tournament, the code for multiple entries will be compiled into a single application. In case you are wondering, I will append a unique integer to the name of each routine before compiling so that each ConnectMove routine will be named uniquely.

This will be a native PowerPC Challenge, scored using the Symantec environment. Solutions may be coded in C or C++.

POST PUBLICATION NOTE: To make the round-robin contest feasible, it is necessary to place some limit on the amount of time a solution can consume for a single move. I will disqualify any entry that takes more than an average of 10 seconds to make a single move on my 8500.