---

Findings

Rick and I then set up six computers to begin processing all of Yo’s responses to the CF opening, restricting Mi’s second turn to A or E depending on Yo’s first turn.  Yo had nine possible responses to CF, namely G, HI, HJ, HK, HL, I, J, K, and L.  By this time Rick had upgraded the program with a counter feature that showed, for each branch of the tree explored, how many terminal states the computer reached in solving that branch; i.e., how many games the computer had to play in order to determine the character of a move.  We discovered the computer was processing millions of games in brief seconds, and billions of games per hour.  Hope mounted.

After four days of processing, the computers had tested some 500 billion games and had shown that the CF opening was indeed a sure-win strategy for most responses by Yo.  Only two of Yo’s responses remained unproven.  Then Rick discovered a bug in the way the program evaluated a terminal state, and all our testing thus far was invalidated.  That was not so bad; we still had time to recover from a four day set-back.  Rick corrected the bug immediately.  The discovery was more disconcerting when we found that the corrected program had a much slower execution speed.  Branches of the tree which had taken minutes to solve previously were now taking hours, and some which had taken hours were now still unresolved after days.  Our only hope would be to seek to build more intelligence into the program. 

We had already observed that the program in its present form spent a lot of its time exploring branches of the tree that would never be played in a real game.  For instance, if Mi has the option of winning the game in the next move by playing A, or extending the game by another fifty turns by playing from B, the computer might spend hours processing B, C, D, E, and F before coming around to spotting the easy win of A.  If we could define some simple rule by which the computer would eliminate “stupid” moves, or at least attempt more promising moves first, without slowing execution speed too much by adding an evaluation step to each node, we might see significant performance improvement.

We had observed that a starving strategy is often effectively employed in the last few moves of the game.  Rick added a feature to the program by which the computer could be instructed to test all moves for both players up to depth n, and then only to test moves beyond n which did not result in Mi (or Yo, as specified by the user) placing additional pebbles on the opponent’s side.  We called this a “reduced game.”  The player whose plays were thus limited is called the “bold player.”  If the computer then returned “win” for the bold player, it would be a definitive win.  If it returned “lose,” the game would be inconclusive; perhaps the bold player could have won by making a play beyond depth n which placed pebbles on the opponent’s side.  The program could then be run again, setting n to a higher value, or testing the same branch of the tree with the other player being bold.  This required more hands-on manipulation, but did speed the processing of many branches of the tree substantially.  A later refinement caused the computer to return not “lose” but “????” if the bold player did not have a decisive win, to help distinguish definitive losses from “you should have tried harder” losses.

After another week or so of running tests and refining the program, we had the happy results:  CF is, indeed, a sure-win strategy for Mi as the opening player according to the backward-induction method, taking the full game tree in scope.  Furthermore, our strategy of playing E as Mi’s second turn if Yo plays G or HG, and A for a raid if Yo plays anything else on her first turn, was also proven.  We had scored a major victory in our experiment.

A few nagging questions remained.  Just because we proved a single opening strategy was a sure-win by backward induction didn’t necessarily mean there was any correlation between opening strategies that looked strong from a soft-player perspective and those that were backward-induction winners.  We only had a sample size of one.  Furthermore, I still wondered about the relationship of these two distinctly different approaches to the third approach of look-aheads.

Time for the analysis was running out, and I was preparing to settle for the findings we had made thus far, when Rick emailed me a jewel – a new program that allowed a user to play out a game of mancala with the computer interactively, with a built-in “look-ahead” function (see Exhibit 4 for instructions on downloading and running Mancala.exe).  The look-ahead function could be set to any depth of turns, but execution speed made any depth beyond nine impractical.  The look-ahead function returned  an integer for each of the available next moves, showing the advantage of the current player at the specified depth, assuming each player made her best available moves and that both viewed payoffs at the same level of depth.

Now we could test correlation among the three approaches to the game.  Furthermore, if look-aheads did correlate to backward-induction strategies, then the look-ahead computer program could give us hints to helping the computer solve backward induction games more efficiently.  For example, if we wanted the search program (backward induction) to test a particular branch of the tree, we could use the look-ahead program to find the best candidate for a sure-win.  We could then tell the search program to test that best candidate move first.

The results were quite surprising.  After a weekend of running such back-and-forth tests, using the look-ahead function to find a best candidate and the search program to prove it, I was able to solve conclusively all but two of the ten opening moves of the game.  The remaining two are still slowly in process.  The following table shows the results:

 

Very surprisingly, of the eight openings solved, I found perfect correlation between winners and players who have positive advantage using 10-deep look-aheads.  Even more surprisingly, the opening move we had identified as strongest according to soft strategy turns out to yield the highest advantage of all the possible opening plays, using nine-deep and ten-deep look-aheads!  Also, the two openings which have proven hardest to solve (CB and CD) have nine-deep advantages near zero.  The opening move D, which was finally proven to be a sure-win for Yo, was the third hardest opening to solve, and has a nine-deep advantage of zero.

After using the look-ahead function extensively to help the computer “guess” which move to attempt first as I solved the remaining opening plays, I continued to discover high correlation between look-ahead values and backward induction winners.  (I used the look-ahead function not just for the opening move, but often several moves deep into the game when the search program seemed to have particular difficulty getting beyond a given node.)  As expected, there were exceptions and discontinuities, but I discovered that the higher the look-ahead advantage of a given move, the higher was the likelihood that that move was a backward induction winner.

This implies some level of “stickiness” or persistence of advantage through the game.  Though much more could be done to study this, I wanted at least to see a plot of look-ahead advantage of the opening moves through the first ten levels.  The following table shows the values:

A graph provides a more meaningful way to observe the relationships:

This graph provides unfortunately only one data point – a view from only one node in the game – and thus any general conclusions drawn from this graph about persistence of advantage at all nodes throughout the game would be invalid.  However, the pattern, even at this one data point, is interesting to observe.  At this single point at least, it does appear that advantage seems to be not only persistent, but largely cumulative (“the rich get richer, the poor get poorer”).

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