---

Look-Aheads:  Between Hard and Soft Strategies

On the border between pure “hard” playing, where iteratively undominated strategies are defined, and pure “soft” playing, where looking forward is limited to the capacity of the human mind, lies an intriguing computer-aided strategy which highlights several formal game-theory concepts, and raises questions about the structure of the game of mancala.  I will call this the “look-ahead” strategy.  The strategy involves looking, from a given point in the game, a certain number of moves or turns forward, but not to the end of the tree.  Payoffs and advantages could be analyzed at that level, then using backward induction, assuming each player makes her best move, a best strategy for the current move could be selected. 

Clearly, the look-ahead strategy differs from true backward induction using the full game tree.  Nonetheless, the strategy raises a number of interesting questions.  Do the optimal plays implied by look-aheads correlate highly to winning plays revealed by true backward induction?  What are the sources of discontinuity, assuming such discontinuities exist?  Do look-aheads with increasing depths tend to converge with the actual game tree, or do gross discontinuities occur regardless of look-ahead depth?  What are the implications for a human player, playing without aid of a computer?

Before actually testing the look-ahead concept with a  computer program, I conducted some analysis using game-theory constructs to reach some hypotheses about how this strategy might actually work.  For simplicity I worked with reduced game trees in which each player has only two options available at each turn, and assumed that no move results in the same player moving again; play always passes to the other player after one move.  Payoff numbers imply the relative change in number of pebbles between the two players’ mancalas.  Consider the following tree:

Payoffs are expressed relative to Mi’s point of view.  Column headings indicate who is making the decision at that point.  Mi, in column three, would maximize her payoff for each of the four scenarios, giving her values of 0, 3, 4, and -2 in each of the column-three boxes (see Figure 5).  Following the backward induction method, we see that ultimately Mi would opt for the first choice rather than the second, and the game would be expected to unfold according to the highlighted cells:

Look-aheads encounter problems from two sources:  first, discontinuities between the partial tree employed and the full tree; and second, differences between payoffs observed by two different players.

In the first case, consider how an additional column of payoff data (replacing the question marks above) could change the entire outcome of backward induction.  An unanswered question at this point in the analysis relates to the persistence of advantage.  If Mi has a 5 pebble advantage over Yo, how “sticky” is that advantage throughout the rest of the game?  If advantage is fairly sticky, then the discontinuities between payoffs at different levels of depth might not completely eliminate the value of the look-ahead strategy.  Further, if payoffs at different levels of depth tended to retain the same relative ordering along the column, even though their absolute measure changed, then the look-ahead method could prove useful.

Experience in playing mancala presents three arguments against the stickiness of advantage.  First, great discontinuities occur when Mi lands a pebble in an empty bin on her side of the board, and Yo has accumulated a large pile of pebbles opposite that empty bin.  Suddenly all of those pebbles go to Mi’s mancala – often five, eight, or even more at one time.  Relative to the number of pebbles needed to win the game – twenty-six – this is a significant discontinuity. 

A second argument is that discontinuity frequently occurs at the very end of the game when Mi runs out of pebbles.  At that time, Yo takes all the pebbles remaining on her side of the board and places them in her mancala.  This discontinuity argues strongly against the likelihood that looking ahead more levels into the game would tend to cause payoffs to converge with the actual game tree:  the greatest discontinuity of all may occur in the very last move of the game.

A third argument challenges the likelihood of persistence of relative positioning of advantage among different branches of the tree.  Unlike chess, strength of board position in mancala is not cumulative.  In chess, if you capture the opponent’s queen, you are more likely to capture a bishop and a knight in subsequent moves; board strength is sticky and cumulative in chess.  Mancala has a continually self re-leveling board.  Experience shows that strength of board position can indeed be created, but it is far more fragile than in chess, and is completely uncorrelated with the number of pebbles in ones mancala.  In chess, a player’s board strength is highly correlated to the number and value of the other player’s pieces which have been removed from the board.  Not so with mancala.

The second source of problems with the look-ahead strategy relates to the players’ own perceptions of payoffs and their beliefs about how each other perceives the payoffs.  Consider Figure 6, in which the numbers in each cell do not represent the backward-induction values, but rather Mi’s relative advantage viewed at each node going forward from column one.  If Mi believes that Yo sees all payoffs that Mi sees, Mi will take the backward-induction path (Figure 7).

However, suppose Mi believes that Yo is not very bright, and looks only one step out in deciding how to play.  Shaded cells in Figure 8 indicate the choices Mi believes Yo would make at each of Yo’s decision nodes.  Mi then calculates her payoff based on her beliefs about Yo, and the game follows the path highlighted in Figure 9, giving Mi a positive advantage of six by the end of the sequence, rather than the negative five she would have suffered had she followed the full backward induction path.

This problem lends itself to the full analysis of beliefs and types of players which was covered in our game theory class.  The above example illustrates not only the problem that beliefs present to the look-ahead method, but also highlights a very real issue of strategy for soft players.  Intellectual horsepower to look forward into the game many levels deep does not by itself give clear advantage.  Having correct beliefs about the kind of player ones opponent is proves equally important.

It may be possible to develop a computer program that could look a large number of moves ahead, but unless in so doing it encountered a complete end of some branch of the tree, this alone would not clearly provide good information about the best next move.

A related issue is the variability of the depth to which human players typically look into the game.  Human players – soft players – learn and make decisions by a variety of methods.  Pattern recognition is a strong factor in how people really play mancala.  While it is unlikely that any normal player without aid of computer, reams of paper, or years of time would be able to evaluate all possible board positions, say, four moves out, an experienced player frequently spots patterns that lead to strategies that are executed accurately over four or more moves.  Consider the following board setup:

It is not unusual for an experienced player lucky enough to find herself in this position to identify the sequence of moves AEDCEF, illustrated in the figures following, which results in the extreme fortune of sixteen pebbles in her mancala.  (“x” denotes the bin just played from.)