Mancala

Play the game.

Download the source code.

I remember that one of my first assignments in a computer science class in college was to implement a Mancala game with a computer opponent. I've decided to recreate it here on my site.

Mancala refers to a whole family of games with slight variations on a theme. The basic theme is that a series of pits are organized in a circle with a number of stones dropped into each pit. Each player has one of the pits designated as a home pit. The object is to outscore your opponent by moving more stones into your home pit. Players take turns by taking the stones from one of the pits and distributing them one-by-one into the adjacent pits in a counter-clockwise fashion.

Like I said, that's just the basic idea. The exact rules vary widely. The game originated from Africa, and the exact rules changed in different regions. For my program, I chose to implement the following rules:

• Each side has 6 pits in addition to the player's home pit.
• Except for the home pits, each pit starts with 3 stones.
• Players may move only their own pits.
• If the last stone in a move lands in the player's home pit, then that player gets a free move.
• If the last stone in a move lands in an empty pit on the player's side, then that player captures the opponent's stones in the opposite pit and transfers them into the previously empty pit.

Implementation

In college, the project was implemented as a C console application that rendered a text representation of the game board after each move. The computer opponent's moves were driven by nested if-then-else logic that gave precedence to getting as many free moves as possible, followed by maximizing the number of stones captured from the opponent, followed by minimizing the number of stones transferred to the opponent's side of the board.

For the version here on cnauroth.net, my first step was to create an object-oriented library that encapsulates the objects in the game and their rules for interaction. This is compiled into a DLL that gets deployed to the bin folder of cnauroth.net.

For me, the most interesting aspect of this project was revisiting the logic for the computer opponent. I took a very different approach compared to the college project. This version performs an alpha-beta search, recursively searching for the move that's most likely to maximize the computer opponent's score while minimizing the human player's score. The idea was inspired by a conversation with Tim Fliss, a former co-worker at Amazon, who had used the algorithm in an online chess program.

After coding and testing the library, I created an .aspx page as a driver. The state of the player's game is maintained in session state. Server-side event handlers manipulate the state of the game in response to player actions. After each move, the game board is rendered with the number of stones present in each pit.

Future Plans

In the future, I'd like to expand the library to support as many variants of the game as possible. To support this, I'll need an architecture that can support plugging in the logic for the various rules at certain points in the execution of the game. I've tried to lay the groundwork for that as much as possible in the current object-oriented implementation.

I'd also like to try tweaking the implementation of the computer opponent. It might be interesting to create configurable parameters on the main algorithm and simulate games between two computer opponents to determine which algorithm performs best.