---

Structural Analysis of the Game

Mancala is a "Trivial Game"

A seasoned game theorist might find self-evident the notion that macala is a trivial game.  For me this discovery was revolutionary.  As a casual player, my intuition was that the game began with both players on equal footing, but that as the game unfolded, there came a point beyond which Yo could not win, regardless of her strategy, assuming Mi subsequently made her optimal response to each play made by Yo.  It was the search for this watershed moment in the game that led to the discovery that the game is, in principal, determined from the outset.  In other words, my intuition was that there existed winning states, losing states, and indeterminate states.  I eventually concluded that there are no indeterminate states in the game.  The process by which I reached this conclusion I now know by its formal name, “backward induction.”  My reasoning was as follows.

By inspection, every mancala game comes to a definite end.  Taking turns inevitably forces pebbles into the mancalas, thus pushing the game to a conclusion.  The last move of the game determines a definitive win, loss, or tie for Mi.  For simplicity I will treat only the case in which Mi wins by taking the last turn, but the other cases are similarly proven.  For the board to be in such a state that Mi had the opportunity to win in one turn, that state was (by definition) a winning state.

Yo must have chosen a strategy in the previous turn that left the board in a winning state for Mi.  If all of Yo’s choices in her last turn left the board in winning states for Mi, then Yo’s board was in a losing state.  If Yo had at least one available move which would have left the board in a losing state for Mi, then Yo would eventually win, thus Yo’s state would have been a winning state.  But what if, in addition to winning and losing strategies available to Yo, there was also a strategy whose ultimate outcome was not determined?

The answer is that there is a lot of difference between “not known” and “not determined.”  If all the immediate children of a node are identified (winners, losers, draws), then the node itself can be identified as follows:  A node is a winner if none of its children are winners.  A node is a loser if at least one of its children is a winner.  A node is a draw if none of its children are winners, but at least one is a draw.  (This description applies strictly as stated only to nodes in which the play passes to the other player for all of its children.  The exception, in which for one or more children of the current node, the same player gets to make another move, is similarly proven.)

Since we have shown that all games end, it follows that all ultimate descendants of any node are definable (meaning, as winners, losers, or draws).  All of their immediate parents are thus also definable, as then are their grandparents, great grandparents, and so on, up to the very top of the tree.

Though this argument is not an elaborate, formal “proof,” it embodies the logic underlying such a proof, and must suffice here as evidence that mancala is, in fact, a trivial game.

Size of the Game Tree

Having reached that conclusion, then, the next question is “so what?”  As others have established, both tic-tac-toe and chess are also trivial games, but one has a game tree with some 10¹²⁰  terminal states, and the other only a small handful.  Quoting Adam Brandenburger, “The problem with mathematicians is that they view numbers like 50 and 10¹²⁰ as being equally finite.”  Questions that come to mind are:  Is the game tree small enough that strong openings could be memorized down to such a level that the remainder of the game could be played by inspection to a more-or-less certain win?  Is it small enough that a computer (or reasonable number of computers together) could solve it in a reasonable period of time?  Is it small enough to be studied and analyzed, such that the character of the opening move could be identified?  Before plunging directly into solving the tree, Rick and I made several attempts to estimate its size and solvability.  The findings shaped the approaches we eventually took in our attempts to solve it.

I first made some back-of-the-envelope calculations on the size of the tree.  Since players seldom have pebbles in all six of their bins, the number of choices available at each move seem to be, on average, between four and five.  Let us suppose that the average is 4.5.  The next step is to determine how many moves, on average, a game lasts.  There are many moves in which no pebbles land in a mancala.  There are also some moves in which multiple pebbles land in a mancala, as when an opponent’s pebbles are captured.  On average I assumed that .75 pebbles land in a mancala per move.  At that rate, it would take 66.66 moves for a mancala to reach 25 pebbles – the point at which the game ends.  So, with 4.5 choices per move, over a series of 67 moves, a rough estimate of the number of unique games (and terminal states) is 4.5⁶⁷, or approximately 6 x 10⁴³.  While this is an insignificant fraction of the size of chess’s game tree, in itself it is still a very, very big number; one beyond the scope of any computing resources currently at my disposal.

What if I’ve overestimated?  Taking an extremely conservative estimate, assume there are on average three choices per move, with games lasting on average 35 moves.  This still results in 3³⁵ or roughly 5 x 10¹⁶ games.  At least this is a named number – 50 quadrillion – but in its raw form, still beyond the likely scope of my present computer resources.  It might be a small enough number, however, to be taken on with a more elegant solution.  For instance, in 50 quadrillion games, how many states are duplicated?  If we could eliminate duplication in the analysis, we would certainly reach a much smaller number.  Also, how many of those games are nonsense games?  For example, if Mi can win in the next move by playing A, but could spin the game into another 20 moves by playing B, she would in real life never play B.  If we could add a little intelligence to the computing process there might be hope of tackling the program.

Approaches and Problems to Solving the Game Tree

A major fork in deciding how to attack the problem is whether to take a depth-first or a breadth-first approach.  A breadth approach would first evaluate all the starting moves, then the all of the second generation, then all of the third, and so on.  A depth approach would go from the first move straight down the tree to the end of the first game, then play the next game, and so on.  Rick’s first approach was a small program that looked breadth-first and reported back the total number of states (non-duplicating nodes) encountered when all games had been played to the end. 

He ignored the number of pebbles in the mancalas in defining unique states, as they do not affect the structure of the board itself (the choices open to each player and the outcomes of those choices).  The number of pebbles in the mancalas does impact strategy, as a player who has the option at some point of going out in two turns or extending play for several more turns might choose to go out sooner if she already has almost half the pebbles in her mancala, but might choose to extend the game if her mancala is presently deprived.  However, her payoff from any subsequent unfolding of the game will be independent of her current advantage.  For this reason, and to simplify the first approach as much as possible, Rick ignored the mancala-count.

On the first execution, Rick tested the program for a game beginning with only one pebble in each bin.  He ran the program until each game had absolutely ended; not just to the point at which the winner had been determined.  In this setup, he identified 93,757 unique states encountered during the games.  Execution took forty seconds.  So far, so good.

Next he attempted to analyze a game beginning with two pebbles per bin.  After five hours, the program had found 4,207,691 states, and had only processed games in which 24, 23, or 22 pebbles were still in play.  This was not looking promising.  A major constraint going forward would be the sheer size of memory required to store all the states encountered.  If, at a minimum,  a state could be stored in 64 bits of data (8 bytes), then we would need over two megabytes of memory to store just the 4 million states encountered in this brief run.  Even under the most optimistic assumptions, we could foresee needing countless terabytes of storage to process the full 4-pebble-per-bin game. 

This approach also had the problem of an exponential decay of efficiency.  At the 1,000^th state, we needed to search only 999 states for duplicates.  At the 1 billionth state, each new state would require hours of searching to eliminate duplicates.  Though we had some ideas of ways to reduce search time, the breadth-first approach was seeming increasingly problematic.

At that point Rick created a spreadsheet (see Exhibit 2) to calculate the theoretical maximum number of unique states in a game with x bins and y pebbles.  Rick explains the calculation:

For one bin there is just one way to distribute N stones.  Each time you add a bin, you can have 0 stones in the new bin and N stones in the other bins, or you can have 1 stone in the new bin and N-1 stones in the other bins, or you can have 2 stones in the new bin and N-2 stones in the other bins, etc.  In this way the first column is all 1's and each other entry is computed as the sum of the entries in the previous column up to that row.  I added two extra bins to represent the two mancalas.  The given values are upper bounds.  Obviously a relative few of the states can not be achieved.  For example, with no stones in either mancala there are only 10 valid states as compared to 280 billion as given in the table. Also, since the table shows there are 203 million ways to put 48 stones in 8 bins (thus avoiding 6), then 406 million states have one player with no stones.  However, these exceptions are very small compared to the total.  I'm pretty sure that a game with 48 stones will have a large fraction of the states being valid.  Even if only one out of 100 distributions is valid that's still 66 billion states.  (I think it will be closer to the 6.6 trillion upper bound.)

 

6.6 trillion was an encouraging number.  Still a very large number, but much smaller than my earlier 50 quadrillion estimate.  (My estimate was for total number of terminal nodes; the new number was total unique states.  Many of the nodes are duplicates.)

Rick opted to shift gears and try a depth-first approach.  He used an elegantly simple programming technique known as recursion, which does not need to remember the entire set of states visited, but only the moves in its current run down the tree.  The recursive program is also elegant in that its main engine does not require a lot of complex code.  It uses a simple “loop” function to move up, down, and across the tree, and then evaluates each node in the tree according to a simple common instruction set regardless of its position in the tree.  The program literally races through the tree searching for winning states.  When a winning state is found at depth x, it moves back up to depth x-1 and reports that as a losing state, then moves up to x-2, exploring peers of the move it has just made at that level, until all have been exhausted or a winning move is encountered, and so on up and down the tree.  The program terminates as soon as it has explored enough moves to declare the starting point a winning state, or, having explored all possible moves to all possible conclusions and finding no sure win, to declare the starting point a losing or drawn state.  Though simple in concept, recursion is a powerful programming technique because of its speed of execution and minimal memory requirements.

Rick has continued to refine the program again and again, incorporating some of my ideas and many of his own. The current version at the time of this writing is 14.  Many features have been added and it has become quite an evolved creature.  The program allows the user to input any given starting point – any state, real or theoretical.  We call this program the “search” program.  (See Exhibit 3 for a full description of its operation, interpretation of its output, and instructions for downloading and using it.)

Upon initial use, our first surprise was the program’s lightning speed of execution.  It solved the 1-pebble, 2-pebble, and 3-pebble-per-bin games in seconds.  The initial findings supported my conclusion that the game has no indeterminate states; that even from the opening move, all states can be defined as winning,  losing, or draw.  The program reported that the 1-pebble-per-bin game results in a draw for the first player if she plays from C or E; all other opening plays result in a loss.

On the downside, we estimated that solving the 4-pebble-per-bin game would take weeks, even on Rick’s 400-Mhz Pentium III.  We were not without hope, however.  Several factors gave encouragement.  First, since the program could be given any starting point to work with, we could set up multiple computers, each testing a state of the game resulting from a different opening turn.  Since the first player (Mi) in the 4-pebble game has six moves from which to choose, one of which leads to a second move for Mi with five choices, this implies ten possible opening turns for Mi.  If this parallel-processing approach would cut the processing time down from ten months to one month, we might have an outside shot at completing the project.  If it cut the time from ten weeks to one week, we should be in very good shape.  The difficulty was in estimating execution time.

Another advantage of the parallel processing approach derives from the nature of the recursive routine:  it stops searching as soon as it can declare a state a  winner.  If, out of ten opening turns, only one is a winner, then finding that winner might take one week if it is the first play, or nine months and one week if it is the last play tested by the program.  Using ten computers, as soon as one computer identified an opening move as a winner, all the other computers could stop processing immediately.  The potential gains from parallel processing were high.

After several test runs, I was still doubtful of our prospects of completing the analysis by the end of the semester.  The program zipped through some branches of the tree speedily, then hung on other branches for hours.  One more refinement could cut the execution time not just to one tenth, but perhaps to one hundredth the expected time required for solving the entire game.  The refinement would be to identify the opening turn we deemed most likely to succeed.  We could then divide Yo’s responses to that opening among the various computers, solving the second-turn plays rather than the first-turn plays.  We would, in short, be testing the hypothesis that a given opening turn was a sure win, instead of solving for the character of all opening turns.  Identifying the best candidate would force us out of a mechanical analysis of the game and into the more subjective study of strategy.

More by Fritz Dooley...

How to make a 350% return trading options Excel Monte Carlo simulation tutorial Calculate calendars in your head like a savant