How to win ALL marbles in Mancala on your first move, with MATLAB!

Today's guest blogger is Anoush Najarian who leads the MATLAB Performance Team at MathWorks. And while she mostly focuses on helping MATLAB run fast, in her spare time, she likes to use MATLAB for hobby projects in robotics, math, and games.

Contents

Winning at Mancala

Let me tell you what happened when I got tired of losing at Mancala, and decided to write some MATLAB code to play it. Shout-out to my daughter, sixth grader Natalie, for introducing me to the game, and being a partner in these experiments.

The Rules

Now, there are many ways to play the games in the Mancala family. The rule set we wrote the code for is: you pick from any hole, and drop one stone at a time while circling the board in counterclockwise fashion, drop a stone into your home whenever you pass through it. If you drop your last stone into your home, you get a 'free' turn. If you drop your last stone into a non-empty hole, you get to continue with what I call an 'automatic' move, picking up all stones from that hole. In the intial position, there are four stones in every hole.

Is There a First-Player Advantage? (You Bet!)

You know how some games have a first-player advantage? It turns out that in Mancala, you can find a way not only to win (which is nice), but to win all the marbles (awesome), and to do so on your very first move!

% Here is driver code to find (one of many!)
% all-48-marble-win-on-first-move solutions, which runs  in ~20s on my
% laptop!

gametrees = {0 [4 4 4 4 4 4 4 4 4 4 4 4] []};
nummoves = 0;
while nummoves < 50
    newgametrees = {};
    L = size(gametrees, 1);
    [maxscore, ind] = max(cell2mat(gametrees(:, 1)));
    [totalscore, board, winningstreak] = gametrees{ind, :}; % display one highest-score entry
    for g = 1:L
        [totalscore, board, winningstreak] = gametrees{g, :};
        for t = 1:12
            if board(t) == 0, continue, end
            [score, freemove, newboard] = mancalafirstmove (t, board);
            if freemove
                if nummoves<9 || totalscore + score > maxscore * 0.75 % optmization to prune search tree
                    newwinningstreak = [winningstreak, t];
                    newgametrees(end+1, :) = {totalscore+score, newboard, newwinningstreak};
                end
            end
            if totalscore+score == 48 disp('Found 48-marble winning sequence!'); disp(newwinningstreak); return; end
        end
    end
    gametrees = newgametrees;
    nummoves = nummoves + 1;
end

% The driver code calls a move function which will runs through 'automatic'
% moves recursively. Our code generates a 30-step-long sequence of plays
% for the sweeping 48-marble win on your first move!

function [score, freemove, board] = mancalafirstmove (apick, board)
score = 0;
moves = eye(12);
pickspot = apick;
freemove = mancalamove(pickspot);
    function freemove = mancalamove(pickspot)
        numpieces = board(pickspot);
        board(pickspot) = 0;
        addapiece = moves(pickspot, :);
        gain = floor((numpieces-pickspot)/12)+1;
        score = score + gain;
        freemove = (pickspot == mod(numpieces, 12));
        numpieces = numpieces - gain;
        for i=1:numpieces
            board = circshift(addapiece, -1*i) + board;
        end
        if (not(freemove))
            newpickspot = mod(pickspot-numpieces, 12);
            if newpickspot==0, newpickspot=12; end
            if board(newpickspot) > 1
                freemove = mancalamove(newpickspot);
            end
        end
    end
end

Found 48-marble winning sequence!
  Columns 1 through 13
     8     5     4     2     9     5     7    11     9     5     3     9     5
  Columns 14 through 26
     1     2     1    12     1    10     1     3     1     8     1     6     1
  Columns 27 through 30
     4     1     2     1

Let the Battle of the First Move play itself out!

Alternative Rule Sets

Some of the other Mancala rule sets out there include: no 'free' move, no 'automatic' move, only picking from the side of the board you are sitting next to, different number of holes, marbles!

For example, suppose 'automatic' moves and free moves are allowed, but you can only place on your side of the board. Then you still can can win capturing a pretty impressive 42 marbles on your first move! Tiny change on line 18 of the driver code (loop 1:6 instead of 1:12) will give you the sequence of plays to use for this variation!

What's Next?

What we'd really like to build up to here is to use the game-playing code for training the AI. We recently watched exciting videos like Deep Learning in 11 Lines of MATLAB Code, and are eager to try deep reinforcement learning for games.

Let us know about your experiments with coding and modeling games here!

Get the MATLAB code

Published with MATLAB® R2017a