Placing stones on vertices of polygon

We have an $n$-gon with $n\geq 3$. Players $A$ and $B$ place a stone alternately on one of the unused vertices that is not adjacent to a vertex with a stone. The player who cannot move loses. Who has a winning strategy?

If $n$ is even, $B$ can win by placing a stone at a vertex diametrically opposite the vertex that $A$ just placed a stone on. For $n=3,7$, $A$ wins, but for $n=5$, $B$ wins.

Solutions Collecting From Web of "Placing stones on vertices of polygon"

Summary

It turns out that this game is very closely related to a well-known game known as Dawson’s Chess, which is equivalent to the Octal Game with code “0.137”. Using the Sprague-Grundy Theorem combined with a winning strategy for Nim, it is relatively straightforward to analyze small games like this (e.g. your game for small $n$), and with a tool known as the “(Guy-Smith) Octal Periodicity Theorem”, some Octal games, including this one, become easy to give a relatively efficient computer strategy for all $n$. It turns out that $A$ has a winning strategy for $n\equiv7,11,23,27,31\text{ mod }34$ and in the three exceptional cases $n=3$, $n=17$, and $n=37$. In all other cases, $B$ has a winning strategy.


Changing the rules

Note that the first move always removes three vertices from consideration, and leaves a consecutive run of $n-3$ available vertices. After that, we don’t have to worry about polygons/circles anymore, as all of the following game states will just involve zero or more consecutive runs. You can play this game on some small runs at Tom Ferguson’s “Dawson’s Chess” page. Note that $A$ has a winning strategy on an $n$-gon precisely if the next player to move on a run of $n-3$ vertices does not have a winning strategy.

To connect this game to existing general theory, we can reconceptualize it: instead of placing stones on runs which often eliminate possibilities of placing stones in the adjacent spots, imagine there are stones already there and when you pick a stone to remove, you remove any adjacent stone(s) as well (as if the Xs and Os on Tom’s Dawson’s Chess page all represent removed stones).

You can remove one stone from a run precisely if the run was only one stone long, so that you leave zero runs behind. You can remove two stones from a run if it’s at the end of the run, so you that you leave zero or one runs behind. You can remove three stones from a run anywhere, so you can leave zero or one or two runs behind (and those two runs can have any lengths that add up to the right total). You can never remove more than three stones from a run. Games with rules like these are traditionally encoded in a “number” with Octal digits. In this case, the code is $0.(2^0)(2^0+2^1)(2^0+2^1+2^2)=0.137$.


Who wins?

Since the original question was “who has a winning strategy?”, rather than “what is the winning strategy, I won’t re-present an introduction to the relevant theorems in detail.

If you don’t already know about the strategy for Nim or the Sprague-Grundy Theorem and how they can be applied to similar games, you can read one or more of the following:

  • Tom Ferguson’s class notes on the subject
  • MJD’s notes in their tidy blog post about using this theory to solve the game in the question for $n$ up through $23$.
  • Lim Chu Wee’s series of blog posts which are also class notes building up the relevant theory (posts I through V)
  • The lecture notes Misère Games and Misère Quotients by Aaron N. Siegel through page 10.
  • My own long-winded series of blog posts building up the relevant theory (posts I.1 through I.6).
  • Chapter 7 of the undergraduate textbook “Lessons in Play: An Introduction to Combinatorial Game Theory” by Albert, Nowakowski, and Wolfe (although a bit of reading of other chapters may be needed first).

Because of the strategy for Nim (how Grundy values combine), it suffices to know the Grundy/Nim values for a single “heap” (in our context, a run of stones). If you calculate enough of these, you will see a pattern. The sequence appears to be eventually periodic. For Octal games, there is a theorem attributed to Guy and Smith that says an apparent periodicity that goes on for long enough is guaranteed to continue forever. You can read about it on page 11 of Misère Games and Misère Quotients by Aaron N. Siegel, in this blog post of mine or as Theorem IV.2.7 in the graduate textbook “Combinatorial Game Theory” by Aaron N. Siegel.

In the case of the game 0.137, checking the values for runs/heaps of length up to 180 is enough to confirm that the pattern continues forever. The following is a table of the values for a run of length $m$ for $0\le m\le135$ (read top to bottom, left to right) with exceptional values undelined:

\begin{array}{r|cccc}
m & \text{0+} & \text{34+} & \text{68+} & \text{102+} \\
\hline
0 & \underline{0} & \underline{0} & 8 & 8 \\
1 & 1 & 1 & 1 & 1 \\
2 & 1 & 1 & 1 & 1 \\
3 & 2 & 2 & 2 & 2 \\
4 & 0 & 0 & 0 & 0 \\
5 & 3 & 3 & 3 & 3 \\
6 & 1 & 1 & 1 & 1 \\
7 & 1 & 1 & 1 & 1 \\
8 & 0 & 0 & 0 & 0 \\
9 & 3 & 3 & 3 & 3 \\
10 & 3 & 3 & 3 & 3 \\
11 & 2 & 2 & 2 & 2 \\
12 & 2 & 2 & 2 & 2 \\
13 & 4 & 4 & 4 & 4 \\
14 & \underline{0} & 4 & 4 & 4 \\
15 & 5 & 5 & 5 & 5 \\
16 & \underline{2} & 5 & 5 & 5 \\
17 & \underline{2} & \underline{2} & 9 & 9 \\
18 & 3 & 3 & 3 & 3 \\
19 & 3 & 3 & 3 & 3 \\
20 & 0 & 0 & 0 & 0 \\
21 & 1 & 1 & 1 & 1 \\
22 & 1 & 1 & 1 & 1 \\
23 & 3 & 3 & 3 & 3 \\
24 & 0 & 0 & 0 & 0 \\
25 & 2 & 2 & 2 & 2 \\
26 & 1 & 1 & 1 & 1 \\
27 & 1 & 1 & 1 & 1 \\
28 & 0 & 0 & 0 & 0 \\
29 & 4 & 4 & 4 & 4 \\
30 & 5 & 5 & 5 & 5 \\
31 & \underline{2} & 3 & 3 & 3 \\
32 & 7 & 7 & 7 & 7 \\
33 & 4 & 4 & 4 & 4 \end{array}

Since Dawson’s Chess is so well known, this sequence is A002187 at the On-line Encyclopedia of Integer Sequences. Since $0$ is the only Grundy value corresponding to a second-player win in Dawson’s Chess, they represent values $m$ for which $A$ wins the polygon game on an $m+3$-gon. Since the pattern repeats forever, the win/loss result is as stated in the beginning:

$A$ has a winning strategy for $n\equiv7,11,23,27,31\text{ mod }34$ and in the three exceptional cases $n=3$, $n=17$, and $n=37$. In all other cases, $B$ has a winning strategy.