# Find the shortest & best starting move in Mancala (Kalah)

The version of Mancala impelemented in this game is as follows:

The board looks like this:

   O   O   O   O   O   O
@                         @
O   O   O   O   O   O


Each O represents a pit that contains four 'seeds'. The @ is called the 'store' where seeds are accumulated, as points.

Each player takes one side (top or bottom) of the board, and play begins by a player removing the seeds from one pit on their side of the board and 'sowing' them one seed per pit in the adjacent pits, in a counter-clockwise order. A player deposits a seed in their own 'store' when passing it. The opponents 'store' is ignored. If the last seed in a players hand is sown in the 'store' the player can move again, picking any pit on their side of the board.

The version of the game coded for allows for 'relay' play, i.e. a turn ends only when the last seed in the players hand is sown in an empty pit. Otherwise, the player can scoop up the seeds in the last pit sown and continue sowing into the next pit, etc.

If the last seed in sown in an empty pit on the player's own side of the board, they capture the seeds in the pit opposite it (on the opponent's side) and deposit them in their store.

This code searches for two things:

1. The shortest sequences of choices that will win on the first move (>24 points)
2. The sequence that gives the most points on the first move.
using System;
using System.Collections.Generic;
using System.Linq;

namespace Mancala
{
static public class Program2
{
static (int[] seq, int count) shortest, max;

public static void Main(string[] args)
{
Branch(Enumerable.Empty<int>(), new int[] { 4, 4, 4, 4, 4, 4, 0, 4, 4, 4, 4, 4, 4 });
Console.WriteLine($"Shortest: ({shortest.count}) | {string.Join(",", shortest.seq)}"); Console.WriteLine($"Max:          ({max.count}) | {string.Join(",", max.seq)}");
}

static void Branch(IEnumerable<int> seq, int[] initialState)
{
for (int i = 0; i <= 5; i++)
{
var pit = i;
var state = initialState.ToArray();

do {
var hand = state[pit];
state[pit] = 0;
for (int j = pit + 1; j <= pit + hand; j++) state[j % 13]++;
pit = (pit + hand) % 13;
} while (pit != 6 && state[pit] > 1) ;
if (pit < 6 && state[pit] == 1) state[6] += state[12 - pit];  // capture rule
if (state[6] > 24) Update(seq.Concat(new int[] { i }), state[6]);
if (pit == 6) Branch(seq.Concat(new int[] { i }), state);
}
}

static void Update(IEnumerable<int> seq, int count)
{
var vseq = seq.ToArray();
if (shortest.count == 0 || vseq.Length < shortest.seq.Length || vseq.Length == shortest.seq.Length && count > shortest.count)
shortest = (vseq, count);
if (count > max.count || count == max.count && vseq.Length < max.seq.Length)
max = (vseq, count);
}
}
}

• Completely off topic, this was my favorite game on my old Nokia dumbphone. Snake (even Snake II) paled in comparison to Mancala. – Flater Nov 7 '17 at 17:13

Kind of surprised no one else has offered constructive criticisms. Let's get the ball rolling. Keep in mind I don't know anything about Mancala.

Overall code organization could be better. Rather than static methods in Program2 class, I would go with separate class(es). I suggest you review posts on Tic-Tac-Toe, where multiple classes are used for the board versus players versus moves.

There are a lot of magic numbers in the code: 5, 6, 12, 13, and 24 to name a few. I'd suggest using named constants or else change the code a bit, e.g. if 6 is a named constant, sometimes use < Constant instead of 5, and <= Constant for 6. As it is, it gets confusing for someone to follow your logic.

initialState.ToArray() is totally unnecessary, unless you are trying to have a independent clone. Your intent is not apparent from the code. And I find that true about much of your code. It's hard to follow your intent.

You may consider using List instead of the combination of arrays and IEnumerable.

The ValueTuple pair named (seq, count) has a few issues. I think the spelling should be Pascal-cased, with seq spelled out as Sequence. Plus, count seems confusing. It's not the count of the associated sequence but rather seems to the the point tally of the sequence. Thus I would rename count to Points.

I would rather use a class than ValueTuple. You can have a variety of constructors, plus:

• Override ToString() to simplify the 2 times you use it in Main.

• Create specific methods to compare 2 instances for shorter sequence length or higher point tally. This may require implementing IEquatable or IComparable.

• initialState.ToArray() is very necessary, because the subsequent code modifies the state of the 'board' and it needs to start the same for each iteration of the 0->5 loop (it's evaluating the outcomes of different starting choices re. a given state). – Reinstate Monica Nov 8 '17 at 18:10
• I used an Enumerable because the Branch method is recursive, and I need to save the state of the sequence for the next iteration of the loop (like in the previous comment). I could create a new list every time, but I don't see the benefit in that. – Reinstate Monica Nov 8 '17 at 18:14
• @afuna As mentioned earlier, those reasons, i.e. your intent, are not apparent from your code. – Rick Davin Nov 8 '17 at 19:12
• ... but I find it odd to assume that it's totally unnecessary. If you don't understand the flow of the code, that's a valid critique in and of itself - but commenting on code that you don't understand is pointless. – Reinstate Monica Nov 8 '17 at 20:20
• I would suggest that you should accept constructive criticism in the spirit it was offered and welcome it as an opportunity for self-improvement. As you read other C# related posts at CR, you will discover that making the intent of your code clear is usually a highly desired feature. – Rick Davin Nov 8 '17 at 20:57