\magnification=\magstep1
\centerline{MONT106Q -- Mathematical Thinking}
\centerline{Group Project on Mancala: ``The Game Played by Kings and Cowherds''}
\centerline{November 16 and 18, 2016}
\bigskip
\noindent
{\it Background}
\bigskip
The name {\it mancala} is an Arabic word (meaning ``transferring'') that 
refers to a whole family of slightly different games.  The family
is of great antiquity and these games are played all over Africa and 
the Middle East.  It is probably fair to say that these games are 
analogous to {\it chess} in European culture -- they are seen as both
a recreation and an intellectual challenge.

\bigskip
All games in this family, sometimes called ``count and capture'' games,
have the same basic idea.  At the start, stones (or seeds, or ... )
are placed in a collection of pits.  During play, players select a pit 
and ``sow'' the stones in that pit into other pits in a definite pattern.  
In the process stones can be ``captured'' and placed into a ``store.''  
The goal is simple -- accumulate more stones in your ``store'' than 
your opponent.  The variations in 
\medskip
\item{$\bullet$}  the layout of the pits, 
\item{$\bullet$}  the numbers of 
stones used, and 
\item{$\bullet$}  the rules by which the game is carried out are almost 
endless.   
\medskip
\noindent
We will look at a comparatively basic form, usually called {\it kalah}.
(Some of you may have seen a commercial version of
a similar game called Oh-Wah-Ree.)
\bigskip
\noindent
{\it How kalah is played}
\bigskip
{\it Kalah} is played on a board with two rows of six pits facing each 
other. Each player ``owns'' a row of six pits, plus a ``store'' to the right 
of the pits.  When the game begins, there are some number  
of stones in each pit (usually four or six), and the two stores are empty.  The players alternate turns.  

\bigskip
In each turn a player begins by selecting one of his pits. All of the stones in 
that pit are picked up and distributed {\it counter-clockwise} around the board, 
placing one stone in each pit. Stones are distributed into the player's own 
``store,'' but the opponent's store is skipped.

\bigskip
\item{(a)}  If the last stone distributed lands in the player's own ``store,'' 
the player gets another turn. 
\item{(b)}  If the last stone lands on an empty pit 
owned by the player and the opponent's pit directly across the board 
contains at least one stone, the player takes all the stones in that 
pit plus the last played stone and puts them all in his or her ``store.'' 
\item{(c)}  Otherwise, the player's turn ends, and the opponent moves.
\item{(d)}  If all of one player's pits become empty, even if it is not his 
or her turn to play, the stones remaining in the pits of the opponent are put 
in the opponent's ``store,'' and the game ends. 
\item{(e)}  The player with the most stones in his or her ``store'' at the end
wins the game.
\bigskip
\noindent
There is a free version of {\it kalah} that can be played online at 
\bigskip
\centerline{\tt http://www.freegaming.de/onlinegames/Puzzle-|-Logic-Games/Mancala.html}
\bigskip
There is also a link to there from the course homepage.
You will try this below (although be careful -- it can be addictive!).
\bigskip
\noindent
{\it Comments}
\bigskip
If you play {\it kalah} a few times against the computer, you should quickly come to the 
conclusion that while the rules are easy and play is simple, understanding
who will win from a given situation, and how to play {\it well} is definitely
not simple(!)  There are subtleties upon subtleties -- just like in chess!
\bigskip
\noindent
{\it Some special positions}
\bigskip
There are a number of special positions from which one of the players
can basically force the game to end by playing {\it all of} the stones
from the pits on his or her side of the board into his or her store.
For example, suppose the pits contain the following numbers of stones:
$$
0, 0, 4, 2, 2, 0
$$
left to right.  Then the player can sow from the rightmost pit with 2
to reach
$$
0, 0, 4, 2, 0, 1.
$$
Since the last stone played landed in the store, the 
player gets another turn and can then continue as follows: 
$$
0, 0, 4, 2, 0, 0.
$$
then
$$
0, 0, 0, 3, 1, 1,
$$
then 
$$
0, 0, 0, 3, 1, 0,
$$
then
$$
0, 0, 0, 0, 2, 1,
$$
then 
$$
0, 0, 0, 0, 2, 0, 
$$
then 
$$
0, 0, 0, 0, 0, 1,
$$
then finally 
$$
0, 0, 0, 0, 0, 0.
$$
All $8$ stones in the player's pits originally have been added
to his/her store, and he/she captures all of his/her opponent's
stones as well!

As one can guess, recognizing and exploiting these (and related) positions
is a key ingredient of {\it kalah} strategy.

\bigskip
\noindent
{\it Mancala strategy and mathematics}
\bigskip
\item{A)}  Play several games against the computer using the link from the 
course homepage.  Did you ever win?  Did you come close?  Can you see
elements of the strategy the program is using?
\item{B)}  Let's say that a pit is ``{\it harvestable}'' if sowing
from that pit ends in the store.  If you analyze the above positions, you will see that we
always played from the {\it rightmost harvestable} pit (when there was a choice -- 
in some cases, there was only one harvestable pit).
Explain why this is {\it always the correct play} if you are in a situation
where you can play all of your stones into your store.  What happens if there
is a choice and you play from a harvestable pit farther to the left?
\item{C)}  With 6 pits as in standard {\it kalah}, there are exactly
17 positions as above where you can get {\it all of your stones to the 
store} if you play correctly 
({\it without} ``wrapping around'' to the opponent's side of the board).  
Find all of them.  (Hint:  If you think about the example
above, you will see that you have, in fact, seen 8 of the 17 already(!))
\item{D)}  What if you start with more than six pits?  Find several additional
positions from which you could force the end of the game if you
started with stones in a row of 7 pits, 8 pits, and 9 pits.  
\medskip
\noindent
There's an interesting ``tidbit'' here.  
The positions we are looking at are called ``winning Tchoukaillon positions''
because there is another ``solitaire'' version of {\it kalah} by that name.  
It has been proved mathematically that 
if you call $s(n) = $ {\it the smallest number of stones for 
which a special position of this type using $n$ pits exists}, then $s(n)$
grows like ${n^2\over \pi}$ as $n \to \infty$.  Who would have thought
{\it mancala} had anything to do with $\pi$?! 
\bye
