I saw a board game somewhere and I want to know the optimal strategy for it.
The game is played on a triangular board with 21 slots:
The two players, red and blue, take turns to put numbered circles in one of the empty slots. Red goes first. The number on the circle increases from 1 to 10 as the game progresses. The number is not controlled by the players, so for the first move, Red must put a red circle with 1, then Blue must put a blue circle with 1, then Red must put a red circle with 2, then Blue must put a blue circle with 2, and so on (all the way to the number 10).
For convenience, I will refer to the move of putting a circle with the number $k$ in the $m$th slot of the $n$th row $(n, m, k)$
As an example, here is the start of a game:
- Red goes $(1, 1, 1)$
- Blue goes $(5, 1, 1)$
- Red goes $(3, 3, 2)$
- Blue goes $(6, 1, 2)$
- Red goes $(3, 1, 3)$
- Blue goes $(2, 2, 3)$
After the above move, the board looks like this:
After a few more moves the game ends:
To determine the winner, we take the surrounding slots of the last empty slot, which in this game is
- red 7
- red 6
- red 10
- blue 10
and add up the sums of blue and red separately. The sum for blue is $10$ and the sum for red is $7 + 6 + 10 = 23$. Whoever has a smaller sum wins. In this case, blue wins.
What is the optimal strategy for this game so that the player either wins or ties every time?
I tried finding this out myself by writing an AI using a heuristic function and a minimax algorithm. I wrote the AI but it always beats me... And I can't see any patterns in its moves...
I have put the code for the AI onto GitHub. It is written in Swift and can only run on a Mac. Link