November 2001 Programmer's Challenge
Seega
Mail solutions to:
progchallenge@mactech.com
Extended Due Date: 11:59pm ET, Monday, 12 November 2001
While rummaging through a dresser drawer, I ran across a collection of magnetic board games put out by a company called Midnite Snack. The company advertises them as ancient games from all over the world. I don’t know how popular these games are across the world, but some of them looked like they might make interesting Challenge problems. This month, your Challenge is to write code that plays the game Seega.
The prototype for the code you should write is:
typedef struct Position {
int row; /* 0..boardSize-1 */
int col; /* 0..boardSize-1 */*
} Position;
typedef struct Board {
int boardSize;
/* odd integer >= 5 */
char cell[];
/* board Position (row,col) is cell[ row*boardSize + col ] */
/* cell[]==0 is an empty cell */
} Board;
void InitGame(
int boardSize,
/* number of rows and columns, odd integer >= 5 */
char pieceValue,
/* value assigned to your pieces, 1..numberOfPlayers */
Boolean playFirst,
/* TRUE if you place pieces first (and move second) */
int stalemateThreshold
/* stalemate will be declared after this number of moves without a capture */
);
void PlacePieces(
const Board board,
/* board state before you place pieces */
Position *placePiece1,
/* place a piece at *placePiece1 */
Position *placePiece2
/* place a piece at *placePiece2 */
)
void MovePiece(
const Board board,
/* board state before you move a piece, updated by test code */
Boolean followUpMove,
/* TRUE if you must make another capture with the last piece moved */
Position *moveFrom,
/* location you are moving from, (-1,-1) if you cannot move */
Position *moveTo,
/* location you are moving to, (-1,-1) if you cannot move */
Boolean *blocked
/* return TRUE if you cannot move */
);
void TermGame(void);
Seega is played on a 5x5 board, which we will be generalizing to an nxn board, for odd values of n no smaller than 5. Each player has 12 pieces, or in the general case, (nxn-1)/2 pieces. The game is played in two phases. In the first phase, players take turns placing two pieces anywhere on the board except for the center square. After both players have placed all of their pieces on the board, the player who last placed a piece moves one piece horizontally or vertically (not diagonally). An opponent’s pieces are captured when they are between, horizontally or vertically, the piece moved by the player and another of the player’s pieces. More than one piece can be captured on a single move. When a player captures one or more of his/her opponent’s pieces, the capturing player makes another move if another capture can be made with the same piece. No piece in the center of the board may be captured. A piece that is moved between two opponent pieces is not captured. If a player cannot move, it becomes the opponent’s turn to move again. The player who captures all of his opponent’s pieces wins the game. In the event both players retain pieces, and no more captures can be made, the player with the most pieces on the board wins the game.
Your InitGame routine will be called with the game parameters, the size of the board (boardSize), the value assigned to your pieces (pieceValue), whether you will be the first person to place pieces on the board (playFirst), and the number of moves without a capture before a stalemate is declared (stalemateThreshold).
When it is your turn to place pieces on the board during the first phase of the game, your PlacePieces routine will be called. You will be given the current state of the board, and should return the locations of the next two pieces you place on the board.
Your MovePiece routine will be called when it is your turn to move. Again, you will be given the current state of the board. You should return the location of the piece that you chose to move, and the location you move it to. The test code will remove any pieces captured by your opponent, and call MovePiece again if another capture can be made by the piece you moved. If your code is called to make another move with the same piece, the flag followUpMove will be TRUE.
When a game is over, your TermGame routine will be called. You should return any dynamically allocated memory and perform any other necessary cleanup.
Any illegal move will result in loss of the game. Illegal moves include attempting to move a piece from a cell where you do not have a piece, or attempting to move to an occupied square, or a followUpMove with a different piece than moved previously.
Entries will be evaluated by conducting a round-robin or other fair tournament. Each entry will be given the same number of opportunities to play first against each of its opponents. The winner will be the entry that has the best win-loss record. One win (or fraction of a win) will be deducted for each second of cumulative execution time. The Challenge prize will be divided between the overall winner and the best scoring entry from a contestant that has not won the Challenge recently.
Our experiment with new development environments has been less than successful — no entries were submitted using alternative environments for either the September and October Challenges. So this will be a native PowerPC Challenge, using the CodeWarrior Pro 7 environment. Solutions may be coded in C or C++.
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".
|
Slashdot
Digg
del.icio.us
reddit
newsvine
Y! MyWeb
