Goal
The game of mancala is played by two players. Players alternate turns and attempt to accumulate the most points by accumulating marbles in their respective bins. There are many different variations of mancala and this implementation includes some of them.
The Board
The board consists of 12 pits and 2 bins. Each side of the board contains 6 pits and at each end of the board is a bin. The human's pits are the 6 pits on the lower half of the board plus the bin on the right end. The computer controls the pits on the top half of the board and the bin on the left end. Play moves counterclockwise. The game begins by placing 4 marbles in each pit.
Gameplay
By default, the human player has the first move. On any given turn, a player chooses any of its non empty pits.After selecting a pit, the player grabs all of the marbles and places them one by one into adjacent pits in a counterclockwise progression. After the final pit on the bottom row, the human player places a marble into its bin, and then continues placing the remainder of the marbles in the row of the opponent. In the event that this continues down the other side of the board. A player does not place a marble in the bin of its opponent.
On any turn, if a player places the final marble of a progression into its bin, this player recieves another turn. Furthermore, if the final marble of a turn lands in an empty pit, this player may claim all of the marbles in the opposite pit, and place them in their bin. And finally, the first player that ends a turn with no marbles in their home row, claims all remaining marbles on the board and places them in their bin.
End Game
The player with the most marbles at the end of the game wins.
Variations
This applet provides many different variations of the gameplay outlined above. Under the options menu, the user may choose which player moves first (human or computer). Also, there are many variations on the appropriate action at the end of a turn. Under the default rules, landing in an empty pit, a player claims all marbles in the opposite pit. This may be changed such that players never take marbles, players only take marbles if they land in an empty pit in their home row, and finally, a player takes the marbles in the opposite bin plus its own marble.
The user may also spefify the actions taken at the end of the game. Currently, the first user to empty their home row (at the end of their turn) claims all remaining marbles. This may be changed such that the first out forfeits the remaining marbles, or that neither player recieves them.
And finally, the user can specify anywhere from 1 to 10 marbles per pit.
Interface
This mancala implementation comes with a robust menu based interface. The many options allow the user to specify the AI depth (number of turn changes), the speed of the animation, and the view. The view settings include multiple color schemes and an alternate board, as well as varying font sizes.
Process--for those interested in more info.
To implement the mancala game, we focused on making things as general as possible to accomodate many different variations in play. To begin, we keep track of the current state of the board using a 2 x 8 array. This array stores the number of marbles in each pit, the number of marbles in each bin, whose turn it is, and the current search depth. Using this single object, we use a standard minimax search algorithm with alpha beta pruning to compute the best move given a certain search depth.
The first point to highlight, is that the depth is measured in turn changes. Since players may move more than once per turn, we are able to specify whether we are minimizing or maximizing by checking whose turn it is. Again, to facilitate a general algorithm, we use a basic heuristic to evaluate board position. Essentially, we take the difference between the number of marbles in each bin, with enormous bonuses or penalties for wining or losing. Since our process is generalized, the most important function is the successor function. In our case, this is the move function. Given a board position and a an index representing the pit to be selected, this function returns the new board. It is in this method that all of the variations are accounted for. Because of the generalized form of the code, our mancala player easily exhibits different strategies based on the style of game being played.
Would you like to see the source code or download the program? You can get the files you need here. If you can't see the whole applet, you can press F11 for fullscreen mode or change your screen's resolution.
UW Madison >> CS department >> Tim's website >> Mancala