Human versus Computer

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.)

 

 

 

 

 

 

Pattern recognition is the driver of such far-sightedness.  Players learn over time to recognize the following patterns which were present in Figure 10:

§         Yo had a large concentration of pebbles in bin L.  This alerts Mi to look for ways to capture them by landing in bin A with the last pebble of a turn.

§         Mi knows that in order to capture Yo’s pebbles in bin L, she will first have to empty her own bin A.

§         Since Yo’s concentration of pebbles was in L, Mi would have to loop all the way around the board in order to land a pebble in A.  The most natural candidate for looping around the board is bin F.  A little counting reveals that bin F needs eight pebbles to reach the target.

§         An experienced player frequently looks for moves that will allow her to move again – bins with exactly enough pebbles to land the last one in her mancala.  Bin A is the only such candidate.

§         Experienced players also know that by sequencing plays correctly, one bin can be filled to the correct number of pebbles for hitting the mancala by playing first from another such bin to the left of the bin in question.

§         Mi plays through the moves in her head, counting the pebbles accumulating in bin F to see if she can reach her target of eight.  She finds that she can, and thus executes the strategy.  Yo is left wondering what hit her.

 

Now consider Yo’s response:

 

Her head still reeling, Yo evaluates the situation.  Despite the coup, Mi has only two bins with pebbles left on her side.  If Yo can play two turns without feeding more pebbles over to Mi’s side, she will force Mi to end the game, and the large accumulation of pebbles on Yo’s side of the board will be swept into her mancala.  Yo also recognizes a pattern:  empty bins on Mi’s side, with pebbles cued up ready to capture more pebbles from Yo.  Yo can sacrifice four pebbles from J or H and still win the game.  Playing J would put another pebble on Mi’s side in a position (A) to threaten the six pebbles (or seven after playing J) in K, provided Mi first empties B.  Best just to sacrifice the four in J.  That leaves only two bins for Yo – I and H – which can be played without putting more pebbles on Mi’s side and without forcing herself to take another turn by landing a pebble in her mancala.  After further playing out the consequences in her mind, she safely plays H on this move; Mi then plays B; Yo plays IGH; leaving Mi the only option of D, ending the game with Yo winning 26 – 22.  This end-game illustrates the abrupt discontinuities that can abound in a carefully thought out game.  The moral of the story:  in contemplating her great coup, Mi became too engrossed in her own view of the board, and forgot to look at the board she would be leaving to Yo and the end of her strategy.

Discontinuities and beliefs notwithstanding, one observation argues strongly for the validity of the look-ahead strategy.  It is this:  if there were no consistent correlation between look-ahead advantage and winning, then mancala would be a random game (except for the end-game), and would not reward foresight, concentration, and mental prowess.  Experience and the game’s very survival through time argue strongly that the look-ahead strategy must hold at least some value.

Perhaps the problems we have identified with look-aheads lie primarily in an incorrect measure of payoff.  In real play, players evaluate moves not only by how many pebbles will ultimately land in the mancala as an immediate result, but also by relative board strength.  Ultimately, the value of board strength results in pebbles in the mancala, and thus might be expected to be captured in a still-deeper look-ahead.  A more accurate measure of payoff, however, might help to iron out some of the discontinuities.  For instance, if payoff were calculated as some weighted combination of pebbles in ones mancala plus pebbles in play on ones own side of the board, this might reduce the discontinuities at the last play of the game.