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

Problem

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);
}
}
}
``````

Solution

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.