# Abalone Migration

Abalone is a 2-player board game. Here's a brief explanation from Wikipedia:

The board consists of 61 circular spaces arranged in a hexagon, five on a side. Each player has 14 marbles that rest in the spaces and are initially arranged as shown below.

For each move, a player moves a line of one, two or three marbles one space. The move can be either in-line (serial in respect to the line of marbles) or broadside (parallel to the line of marbles), as illustrated below.

Challenge:

There is only one set of marbles on the board with initial state as in the above picture (it doesn't matter which color you choose). At least how many moves does it takes to migrate all your marbles to your opponent's initial space?

## 2 Answers

The answer is either 30 or 31.

murgatroid99's answer actually shows that at least 30 moves are required. That is, it actually takes a minimum of 88 marble moves to get from the starting position to the ending position, which means it takes at least 88/3 > 29 moves.

On the other hand, here is an explicit strategy that involves 31 moves. Start by pushing forward two adjacent "vertical threesomes" (like the one in the example move for white above and the threesome immediately to its right. Then you have 3 marbles in the first row, 6 in the second (thought of as two groups of three), 3 in the third, and 2 in the fourth. You can move the 2 in the fourth to the bottom row in 5 moves and then use 6 moves on each of the remaining horizontal groups of three into the final position.

If we move all of the marbles from the start position to the end position, the average marble ends up a distance at least 6 from its starting position. In the best case, each move results in 3 marbles each 1 hop closer to their final position. A single side has 14 marbles. Therefore, at least 28 moves are required to move all marbles on one side from their starting positions to their final positions.

• I assume you simply did 6*14/3=28. This is assuming you can always move 3 balls at a time towards the goal. You may be able to, but can you prove it? Right now this isn't an answer, its just a guess. Dec 2, 2014 at 10:56
• It's not a guess, it's a lower bound. The question says "at least how many moves does it take?" and I showed that it takes at least 28 moves. It's not the best answer to the question, but it is an answer. Dec 2, 2014 at 18:08