April 1998 Programmer's Challenge

Mancala

A stocking stuffer from this past Christmas provided the inspiration for this month's Challenge. Santa gave me a two player travel game called Mancala which might provide some amusement the next time I travel by car or by plane, provided the ride is smooth enough to keep the small stones inside the bowls of the game board. I thought it might make for an interesting Challenge tournament.

The basic Mancala game consists of a board with 14 hollowed-out bowls arranged in an oval form, one large bowl at each end of the board, and six smaller bowls facing each of two players seated opposite one another. Each player "owns" the large bowl, or "mancala", positioned to his right, and the six small bowls closest to him. The game starts with each small bowl containing four stones. The game begins with the first player picking up all of the stones in one of his small bowls, dropping one stone in the bowl to the right, the second stone in the second bowl on the right, continuing around the board in counterclockwise fashion until the stones he picked up are gone. The second player then picks up the stones in one of his small bowls, drops them one at a time in the bowls to the right, etc. The game ends when one player cannot move (i.e., no stones remain in that player's small bowls). The winner is the player with the most stones in his mancala. There are a number of variations to the game, and the specific restrictions on our Mancala Challenge tournament are explained below.

The prototype for the code you should write is:

#if defined(__cplusplus)
extern "C" {
#endif

Boolean Mancala(
long board[], /* on entry, board[i] is number of stones in bowl i */
/* on exit, board reflects the results of your move */
const long boardSize, /* number of bowls in the board, including mancalas */
void *privStorage, /* pointer to 1MB of storage for your use */
const Boolean newGame, /* true for your first move of a game */
const Boolean playerOne, /* true when you are the first player */
long *bowlPlayed, /* return the number of the bowl you played from */
long *directionPlayed /* return 1 if you played counter-clockwise, */
/* return -1 if you played clockwise */
);

#if defined(__cplusplus)
}
#endif

Each time your Mancala routine is called, you will be provided with a board[] array that indicates the number of stones in each bowl, including the Mancalas, at the beginning of your turn. The boardSize parameter will indicate the number of bowls in the board - in the standard Mancala game, this would be 14, but in our Challenge it might be any even number between 8 and 32, inclusive. The mancala for the first player will be board[0], while the mancala for the second player will be board[boardSize/2]. You will also be provided a pointer privStorage to 1MB of storage, preinitialized to zero, for each of your moves in a single game. For your first move of a game, newGame will be TRUE, otherwise newGame will be false. If you are the first player, playerOne will be TRUE for each of your moves, otherwise playerOne will be FALSE. You should return the index of the bowl you played from in bowlPlayed, and you should return the direction you chose to move in directionPlayed. You should also update your view of the number of stones in each bowl in board[].

There are a number of rule variations for Mancala. We will play with the following additions to the standard rules:

• the board will contain between eight and 32 bowls, instead of the standard 14.
• at the beginning of the game, each small bowl will have between two and 16 stones (instead of the standard four), with the same number in each bowl
• players do not drop stones into their opponent's mancalas.
• players may choose to move either counter-clockwise or clockwise on a given move.
• if a player drops the last stone into his mancala, he gets to move again (my test code will call your Mancala routine again)
• if a player drops the last stone into one of the empty bowls (board[i]) on his side of the board, he takes that stone, plus all the stones in his opponent's bowl directly across from his bowl (board[boardSize-i]) and places them in his mancala
• the game ends when one player has no stones in any of his small bowls and cannot move. The other player then places all remaining stones from his small bowls into his mancala.

At the end of the game, each player will be credited with one point for each stone in his mancala, minus one point for each 100ms of cumulative execution time. The Challenge winner will be the entry that accumulates the most points in a round-robin tournament where each entry competes against each other entry twice for each set of game parameters, once playing first, and once playing second.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.

Programmer's Challenge
progchallenge@mactech.com
<www.mactech.com/>

Bob Boonstra
boonstra@ultranet.com
<http://www.ultranet.com/~boonstra>