{"id":2297,"date":"2017-05-22T09:02:31","date_gmt":"2017-05-22T14:02:31","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=2297"},"modified":"2017-04-23T09:16:20","modified_gmt":"2017-04-23T14:16:20","slug":"how-to-win-all-marbles-in-mancala-on-your-first-move-with-matlab","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2017\/05\/22\/how-to-win-all-marbles-in-mancala-on-your-first-move-with-matlab\/","title":{"rendered":"How to win ALL marbles in Mancala on your first move, with MATLAB!"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>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.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#548ff4fe-0217-4e6b-b95a-1ddda6e433ba\">Winning at Mancala<\/a><\/li><li><a href=\"#a7d8ead7-8e1a-499d-b104-2a7d385db486\">The Rules<\/a><\/li><li><a href=\"#c9451af8-00cd-4b64-9cb4-a22af11daa72\">Is There a First-Player Advantage? (You Bet!)<\/a><\/li><li><a href=\"#8e8b8800-de66-4936-bdd6-0c94ebcefdce\">Alternative Rule Sets<\/a><\/li><li><a href=\"#26658ebc-700c-417f-b4ff-4295594271e1\">What's Next?<\/a><\/li><\/ul><\/div><h4>Winning at Mancala<a name=\"548ff4fe-0217-4e6b-b95a-1ddda6e433ba\"><\/a><\/h4><p>Let me tell you what happened when I got tired of losing at <a href=\"https:\/\/en.wikipedia.org\/wiki\/Mancala\">Mancala<\/a>, 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.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2017\/mancala_board.jpg\" alt=\"\"> <\/p><h4>The Rules<a name=\"a7d8ead7-8e1a-499d-b104-2a7d385db486\"><\/a><\/h4><p>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.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2017\/mancala_board_schematic.png\" alt=\"\"> <\/p><h4>Is There a First-Player Advantage? (You Bet!)<a name=\"c9451af8-00cd-4b64-9cb4-a22af11daa72\"><\/a><\/h4><p>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!<\/p><pre class=\"codeinput\"><span class=\"comment\">% Here is driver code to find (one of many!)<\/span>\r\n<span class=\"comment\">% all-48-marble-win-on-first-move solutions, which runs  in ~20s on my<\/span>\r\n<span class=\"comment\">% laptop!<\/span>\r\n\r\ngametrees = {0 [4 4 4 4 4 4 4 4 4 4 4 4] []};\r\nnummoves = 0;\r\n<span class=\"keyword\">while<\/span> nummoves &lt; 50\r\n    newgametrees = {};\r\n    L = size(gametrees, 1);\r\n    [maxscore, ind] = max(cell2mat(gametrees(:, 1)));\r\n    [totalscore, board, winningstreak] = gametrees{ind, :}; <span class=\"comment\">% display one highest-score entry<\/span>\r\n    <span class=\"keyword\">for<\/span> g = 1:L\r\n        [totalscore, board, winningstreak] = gametrees{g, :};\r\n        <span class=\"keyword\">for<\/span> t = 1:12\r\n            <span class=\"keyword\">if<\/span> board(t) == 0, <span class=\"keyword\">continue<\/span>, <span class=\"keyword\">end<\/span>\r\n            [score, freemove, newboard] = mancalafirstmove (t, board);\r\n            <span class=\"keyword\">if<\/span> freemove\r\n                <span class=\"keyword\">if<\/span> nummoves&lt;9 || totalscore + score &gt; maxscore * 0.75 <span class=\"comment\">% optmization to prune search tree<\/span>\r\n                    newwinningstreak = [winningstreak, t];\r\n                    newgametrees(end+1, :) = {totalscore+score, newboard, newwinningstreak};\r\n                <span class=\"keyword\">end<\/span>\r\n            <span class=\"keyword\">end<\/span>\r\n            <span class=\"keyword\">if<\/span> totalscore+score == 48 disp(<span class=\"string\">'Found 48-marble winning sequence!'<\/span>); disp(newwinningstreak); <span class=\"keyword\">return<\/span>; <span class=\"keyword\">end<\/span>\r\n        <span class=\"keyword\">end<\/span>\r\n    <span class=\"keyword\">end<\/span>\r\n    gametrees = newgametrees;\r\n    nummoves = nummoves + 1;\r\n<span class=\"keyword\">end<\/span>\r\n\r\n<span class=\"comment\">% The driver code calls a move function which will runs through 'automatic'<\/span>\r\n<span class=\"comment\">% moves recursively. Our code generates a 30-step-long sequence of plays<\/span>\r\n<span class=\"comment\">% for the sweeping 48-marble win on your first move!<\/span>\r\n\r\n<span class=\"keyword\">function<\/span> [score, freemove, board] = mancalafirstmove (apick, board)\r\nscore = 0;\r\nmoves = eye(12);\r\npickspot = apick;\r\nfreemove = mancalamove(pickspot);\r\n    <span class=\"keyword\">function<\/span> freemove = mancalamove(pickspot)\r\n        numpieces = board(pickspot);\r\n        board(pickspot) = 0;\r\n        addapiece = moves(pickspot, :);\r\n        gain = floor((numpieces-pickspot)\/12)+1;\r\n        score = score + gain;\r\n        freemove = (pickspot == mod(numpieces, 12));\r\n        numpieces = numpieces - gain;\r\n        <span class=\"keyword\">for<\/span> i=1:numpieces\r\n            board = circshift(addapiece, -1*i) + board;\r\n        <span class=\"keyword\">end<\/span>\r\n        <span class=\"keyword\">if<\/span> (not(freemove))\r\n            newpickspot = mod(pickspot-numpieces, 12);\r\n            <span class=\"keyword\">if<\/span> newpickspot==0, newpickspot=12; <span class=\"keyword\">end<\/span>\r\n            <span class=\"keyword\">if<\/span> board(newpickspot) &gt; 1\r\n                freemove = mancalamove(newpickspot);\r\n            <span class=\"keyword\">end<\/span>\r\n        <span class=\"keyword\">end<\/span>\r\n    <span class=\"keyword\">end<\/span>\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><pre class=\"codeoutput\">Found 48-marble winning sequence!\r\n  Columns 1 through 13\r\n     8     5     4     2     9     5     7    11     9     5     3     9     5\r\n  Columns 14 through 26\r\n     1     2     1    12     1    10     1     3     1     8     1     6     1\r\n  Columns 27 through 30\r\n     4     1     2     1\r\n<\/pre><p>Let the Battle of the First Move play itself out!<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2017\/mancala_play.gif\" alt=\"\"> <\/p><h4>Alternative Rule Sets<a name=\"8e8b8800-de66-4936-bdd6-0c94ebcefdce\"><\/a><\/h4><p>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!<\/p><p>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!<\/p><h4>What's Next?<a name=\"26658ebc-700c-417f-b4ff-4295594271e1\"><\/a><\/h4><p>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 <a href=\"https:\/\/www.mathworks.com\/videos\/deep-learning-in-11-lines-of-matlab-code-1481229977318.html\">Deep Learning in 11 Lines of MATLAB Code<\/a>, and are eager to try deep reinforcement learning for games.<\/p><p>Let us know about your experiments with coding and modeling games <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=2297#respond\">here<\/a>!<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_b3c1f832fbde4c858fd6fb987f5b0577() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='b3c1f832fbde4c858fd6fb987f5b0577 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' b3c1f832fbde4c858fd6fb987f5b0577';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2017 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_b3c1f832fbde4c858fd6fb987f5b0577()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2017a<br><\/p><\/div><!--\r\nb3c1f832fbde4c858fd6fb987f5b0577 ##### SOURCE BEGIN #####\r\n%% How to win *all* marbles in Mancala on your first move, with MATLAB!\r\n%\r\n% Today's guest blogger is Anoush Najarian who leads the MATLAB Performance\r\n% Team at MathWorks.  And while she mostly focuses on helping MATLAB run\r\n% fast, in her spare time, she likes to use MATLAB for hobby projects in\r\n% robotics, math, and games.\r\n%\r\n%% Winning at Mancala\r\n% Let me tell you what happened when I got tired of losing at \r\n% <https:\/\/en.wikipedia.org\/wiki\/Mancala Mancala>, and decided to write some\r\n% MATLAB code to play it.  Shout-out to my daughter, sixth grader Natalie, for\r\n% introducing me to the game, and being a partner in these experiments. \r\n%\r\n% <<mancala_board.jpg>>\r\n%\r\n%% The Rules\r\n% Now, there are many ways to play the games in the Mancala family.  The\r\n% rule set we wrote the code for is: you pick \r\n% from any hole, and drop one stone at a time while circling the board in\r\n% counterclockwise fashion, drop a stone into your home whenever you pass\r\n% through it. If you drop your last stone into your home, you get a 'free'\r\n% turn. If you drop your last stone into a non-empty hole, you get to\r\n% continue with what I call an 'automatic' move, picking up all stones from\r\n% that hole.  In the intial position, there are four stones in every hole.  \r\n% \r\n% <<mancala_board_schematic.png>>\r\n%\r\n%% Is There a First-Player Advantage? (You Bet!)\r\n% You know how some games have a first-player advantage? It turns\r\n% out that in Mancala, you can find a way not only to win (which is nice),\r\n% but to win all the marbles (awesome), and to do so on your very first\r\n% move! \r\n\r\n% Here is driver code to find (one of many!)\r\n% all-48-marble-win-on-first-move solutions, which runs  in ~20s on my\r\n% laptop!\r\n\r\ngametrees = {0 [4 4 4 4 4 4 4 4 4 4 4 4] []};\r\nnummoves = 0;\r\nwhile nummoves < 50\r\n    newgametrees = {};\r\n    L = size(gametrees, 1);\r\n    [maxscore, ind] = max(cell2mat(gametrees(:, 1)));\r\n    [totalscore, board, winningstreak] = gametrees{ind, :}; % display one highest-score entry\r\n    for g = 1:L\r\n        [totalscore, board, winningstreak] = gametrees{g, :};\r\n        for t = 1:12\r\n            if board(t) == 0, continue, end\r\n            [score, freemove, newboard] = mancalafirstmove (t, board);\r\n            if freemove\r\n                if nummoves<9 || totalscore + score > maxscore * 0.75 % optmization to prune search tree\r\n                    newwinningstreak = [winningstreak, t];\r\n                    newgametrees(end+1, :) = {totalscore+score, newboard, newwinningstreak};\r\n                end\r\n            end\r\n            if totalscore+score == 48 disp('Found 48-marble winning sequence!'); disp(newwinningstreak); return; end\r\n        end\r\n    end\r\n    gametrees = newgametrees;\r\n    nummoves = nummoves + 1;\r\nend\r\n\r\n% The driver code calls a move function which will runs through 'automatic'\r\n% moves recursively. Our code generates a 30-step-long sequence of plays\r\n% for the sweeping 48-marble win on your first move! \r\n\r\nfunction [score, freemove, board] = mancalafirstmove (apick, board)\r\nscore = 0;\r\nmoves = eye(12);\r\npickspot = apick;\r\nfreemove = mancalamove(pickspot);\r\n    function freemove = mancalamove(pickspot)\r\n        numpieces = board(pickspot);\r\n        board(pickspot) = 0;\r\n        addapiece = moves(pickspot, :);\r\n        gain = floor((numpieces-pickspot)\/12)+1;\r\n        score = score + gain;\r\n        freemove = (pickspot == mod(numpieces, 12));\r\n        numpieces = numpieces - gain;\r\n        for i=1:numpieces\r\n            board = circshift(addapiece, -1*i) + board;\r\n        end\r\n        if (not(freemove))\r\n            newpickspot = mod(pickspot-numpieces, 12);\r\n            if newpickspot==0, newpickspot=12; end\r\n            if board(newpickspot) > 1\r\n                freemove = mancalamove(newpickspot);\r\n            end\r\n        end\r\n    end\r\nend\r\n\r\n%%\r\n% Let the Battle of the First Move play itself out!\r\n%\r\n% <<mancala_play.gif>>\r\n%\r\n\r\n%% Alternative Rule Sets\r\n% Some of the other Mancala rule sets out there include: no 'free' move, no\r\n% 'automatic' move, only picking from the side of the board you are sitting\r\n% next to, different number of holes, marbles!  \r\n%\r\n% For example, suppose 'automatic' moves and free moves are allowed, but\r\n% you can only place on your side of the board.  Then you still can can win\r\n% capturing a pretty impressive 42 marbles on your first move!  Tiny\r\n% change on line 18 of the driver code (loop 1:6 instead of 1:12) will give\r\n% you the sequence of plays to use for this variation!  \r\n%\r\n\r\n%% What's Next?\r\n% What we'd really like to build up to here is to use the game-playing code\r\n% for training the AI.  We recently watched exciting videos like \r\n% <https:\/\/www.mathworks.com\/videos\/deep-learning-in-11-lines-of-matlab-code-1481229977318.html Deep Learning in 11 Lines of MATLAB Code>, \r\n% and are eager to try deep reinforcement learning for games. \r\n% \r\n% Let us know about your experiments with coding and modeling games\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=2297#respond here>!\r\n##### SOURCE END ##### b3c1f832fbde4c858fd6fb987f5b0577\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2017\/mancala_play.gif\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>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.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2017\/05\/22\/how-to-win-all-marbles-in-mancala-on-your-first-move-with-matlab\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[33,69],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/2297"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=2297"}],"version-history":[{"count":2,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/2297\/revisions"}],"predecessor-version":[{"id":2299,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/2297\/revisions\/2299"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=2297"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=2297"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=2297"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}