Marbles on a Mancala Board

Question

I would like to introduce an ancient African board game I've just invented. Until someone comes up with a better name, it's called Marble Mancala.

The rules are pretty simple:

• There are two players, taking alternating turns. There are 12 numbered bowls, some with a marble in them, some empty.
• On a turn, the player must take one marble from the board, and
  • optionally, add a new marble to any number of consecutive empty bowls with numbers immediately following the bowl from which the marble was taken.
• The player to take the last marble wins.

For example, in the picture's position, Take from 2 and add to 3, 4, 5, 6 and 7 would be a legal move, resulting in a total of 6 marbles being on the board. Take from 1 would also be legal in the starting position, but since there are no empty bowls immediately following it (bowl 2 already has a marble), no new marbles could be added, and the other player would immediately win with Take from 2.

You have challenged your friend to this game, and you are starting from the position shown in the picture: one marble in bowls 1 and 2 each, rest of the bowls empty. You have won the coin toss, so you get to choose:

Will you go first, or should you let your opponent start?

---

^{_{The Mancala board base image is from Brooklyn Museum, released under the Creative Commons Attribution 3.0 Unported license. The marble is a free image from Pixabay.}}

---

(Not really a) Hint, lifted from the comment section:

You are not supposed to brute-force the game. There is a quite nifty (well, in my opinion, at least) shortcut for figuring out whether it's good to start or not.

Answer 1

You should

Let your opponent start

To prove, let us first do the following

If a bowl contains a marble mark it with a '1', otherwise mark it with a '0'.
Then concatenate the entries in order to form a binary string of length 12.
For example, the starting position in the game above is represented by the string 110000000000.
Now, if we consider this number as a binary number, $s$, representing our state then a single move comprises subtracting a non-negative power of 2 from $s$ (that is, in binary, subtracting a number of the form 1000...000).
So, essentially, this is equivalent to a game of Nim with a single pile of coins where we must remove a non-negative power of 2 from the pile at each step.
There is a simple strategy to winning this game, that is to always leave your opponent with the size of the pile equal to a multiple of 3. This will always be possible as long as the pile your given first is not a multiple of 3 (you can just remove either 1 or 2 coins as required).

Translating this back to our current game, at every step, we must make a move which makes the resulting state, $s$ a multiple of 3. Your opponent's move will then necessarily move the state to not be a multiple of 3 and, in particular, they can never reach 0.

A winning starting configuration is thus determined by whether or not it is a multiple of 3.
If it is not, Player 1 wins. If it is, Player 2 wins.

In this instance $(110000000000)_2 = (11 \times 10000000000)_2$ which is clearly a multiple of 3.
Hence, Player 2 wins with the optimal strategy.

Answer 2

User hexomino already figured out the puzzle, and managed to actually find the very complicated path that was exactly how I came up with the game. To recap:

You can interpret the game position as a binary number (marbles are ones, empty bowls are zeroes). If you do, then every possible move gets exactly mapped, one-to-one, to every possible (binary) subtraction of a non-negative power of two. This reduces the puzzle to another game we have already solved, so we are done.

The game itself is a lot easier to play than that, though, so I'm posting this self-answer to show how.

First, it's very useful to note that in a given board position, every move is uniquely defined by the highest numbered bowl it affects. So instead of saying Take a marble from 2 and add a marble to bowls 3-7 each, we can just say play at 7, and there's going to be exactly one way to do that. Not only is this a nice shorthand way to mark down moves, turns out it's quite crucial in solving the entire puzzle. Below, all moves are given using this notation.

^{(Now that we've established the notation, you may want to take a peek at the final spoiler block to see the surprisingly simple final conclusion.)}

The other, more significant part of the solution is

The balance of marbles in odd and even numbered bowls. Let's call that balance $\Delta$ (Delta). To calculate $\Delta$, simply count the marbles in odd-numbered bowls and subtract the number of marbles in even-numbered bowls.

To see why $\Delta$ so important, let's take a look at how the possible moves affect it:

A play on an odd-numbered bowl with a marble in it removes one odd bowl from the count, so $\Delta$ decreases by one.

A play on an odd-numbered empty bowl, with a marble in the preceding bowl adds one odd bowl, and removes an even bowl, so $\Delta$ increases by two.

A play on an even-numbered bowl with a marble in it removes one even bowl from the count, so $\Delta$ increases by one.

A play on an even-numbered empty bowl, with a marble in the preceding bowl adds one even bowl, and removes an odd bowl, so $\Delta$ decreases by two.

A play on any empty bowl with more empty bowls before it will be equivalent to one of the cases above: if a move affects two adjacent empty bowls, they will cancel each other out, and the remaining highest numbered bowl will have the same parity as the originally played bowl.

Pondering this for a while, we can find these helpful facts:

If we divide $\Delta$ by 3, the remainder will always
* increase by 1, if we play on an odd-numbered bowl.
* decrease by 1, if we play on an even-numbered bowl.

Since we know that the final, winning move leaves a $\Delta$ of exactly zero, and we know that any move either adds one to the remainder $\Delta$ (mod 3), or removes one from it, we can deduce that

* If $\Delta$ is divisible by three, there are no moves that leave $\Delta$ divisible by three, so
* There are no winning moves from a position where $\Delta$ is divisible by three, and
* If $\Delta$ is not divisible by three, there is always a move that leaves a $\Delta$ divisible by three for the opponent.

This gives the winning strategy:

Always play a move that makes $\Delta$ divisible by three.

Using this, we can judge the starting position:

There's one marble in an odd bowl, and one in an even bowl, so $\Delta$ is zero, and it's impossible to play a winning move, so the position is losing.

Therefore, the way to win is to

let the opponent start. Then, whenever the opponent plays on an even-numbered bowl, respond with an odd-numbered bowl (the smallest possible one, if you want the fastest win), and vice versa.

Note that this is exactly the same strategy that @hexomino gives, but instead of doing binary subtraction, decimal conversion and remainder calculations, we are doing the same calculations all in marble binary, which turns out to be quite a lot easier.