Last week we were trying to determine how to play the new game Lines’n’Gons:
You and your friend are playing a variant of the game Dots and Boxes. In this variation, your board is now a regular octagon. You take turns drawing lines between two non-neighboring vertices with the following rules:
You can’t cross an existing line
If your line creates a triangular face, you get to claim that face and score +1. If you manage to create two triangular faces, you get both of those faces for +2
You and your opponent proceed until no more lines can be drawn
At the end, whoever has more points wins.
Below is a simple animation to illustrate
Blue goes first. Red goes second and completes a triangle, which secures that face for red. Blue goes next and completes two triangles, securing both for blue.
The questions for this week are:
If both players play randomly, what’s the probability that Player 1 wins?
What is the optimal play for both players?
Under optimal play, what is the outcome of the game?
For those courageous solvers, answer each of these questions for a regular n-gon.
, Josh Arnold, and Vamshi Jandhyala for their submissions! You can check their solutions out here. Despite this being (IMO) a pretty challenging puzzle they all crushed it!
As it turns out, the questions for this puzzle were easiest to answer in reverse order. If you played a few rounds, you will see pretty quickly that—assuming optimal play—any n-gon with an even number of sides has player 1 winning while any odd number has player 2 winning. Why is this the case? Well it helps to first consider what optimal play is for each player. To do this we will consider even boards and odd boards.
An Even Board
With an even board the first player always has an ear—a diagonal that chops off a single triangle—ready to draw. That move does two useful things at once—it scores +1 immediately and leaves behind an odd-sided sub-board (because the original even number minus 1 triangle edge makes the remainder odd). An odd board is awkward for the next player because no matter what diagonal they choose they can’t grab two triangles at once and they’re forced to hand back a board with at least one even polygon. With that even polygon, the first player can repeat the same trick until the polygon is a square and then player 1 can claim 2 points. In this way, player 1 can always win.
An Odd Board
The even board strategy doesn’t work here because that will leave player 2 at the end with a square for +2 and give them the win. In fact, any move player 1 makes will leave one odd sub-board and one even sub-board. Player 2 can now play off that even sub-board with player 1’s even board strategy to ensure a +2 on that board. That does require that they take a -1 overall (if player 1 plays optimally) on the odd sub-board but that still nets out to +1 for a win.
Basically the optimal strategy boils down to: claim an ear when you’re presented with an even sub-board. How you play when this strategy isn’t an option (i.e. you only are presented with odd sub-boards) doesn’t really matter since you will lose anyway.
The Random Game
Moving on to part (a), we need to calculate the probability of winning under random play. This turns out to be more complicated than the previous parts. We first remind ourselves that every move separates the board into two somewhat independent boards. So far, we’ve been calling these sub-boards. This should immediately clue us into a recursive approach. In order to keep track of how these sub-boards influence the larger game, we’ll want to keep track of what the typical scoring outcome looks like for each. Since we only really care about who wins, let’s consider a score difference Δn between player 1 and player 2 for a given board of size n.
As we said before, on any given move, the board is divided into two smaller polygons of size a and b where a+b=n+2. As a part of that same move, a player can score between 0 and 2 points. Let’s call this value S(a,b). It is then your opponent’s turn. From your perspective, their Δn is your -Δn and they can, of course, play on either of the created polygons. Putting this all together, we can write the following recurrence relation.
\(\Delta_n = S(a,b) - \Delta_a - \Delta_b\)
There are, of course, different choices for a and b so we’ll need to average over each of these. Since any given diagonal is equally likely to be selected, we can take a simple average. So how many different diagonals are there? Well, there are n choices for our starting vertex and n-3 choices for our final vertex. We’ll just need to remember that we don’t care about the ‘order’ of our vertices so we’ll divide this product by 2 giving us
\(D_n = \frac{n(n-3)}{2}\)
where Dm is the number of possible diagonals on an n-gon.
We also need to consider whether each of these diagonals scores 0, 1, or 2 points. Scoring occurs when a=3, b=3, or a=b=3 (i.e. triangles are formed). Let’s let Bn(a) be the number of diagonals that divide an n-gon into a polygon of size a and b=n+2-a. If we image fixing the first vertex, then there are only two vertices we can connect to that yield a polygon of size a—the vertex that is a-1 steps clockwise and the vertex that is a-1 steps counter-clockwise. We again need to remember that we don’t care about the ‘order’ of the vertices so we divide by 2. The only exception to this is when a=b, in which case there is only one viable vertex. This give us
\(B_n(a) =
\begin{cases}
n, & \text{if } a \ne b, \\[6pt]
\frac{n}{2}, & \text{if } a = b
\end{cases}
\qquad \text{for } 3 \le a \le n-1
\)
Since any diagonal is equally as likely, the probability of a particular split is just Bn(a)/Dn.
We almost have everything we need but if we recall back to our original recurrence expression, where we had the sum of random variables. Let’s let Δn=δ. Then we can write
\(- \Delta_a - \Delta_b = \delta - S(a,b)\)
While this may look like there’s 3 different random variables here, there only 2, namely Δa and Δb. S(a,b) is fully determined for a given value of a so δ-S(a,b) can be thought of a constant where S(a,b) is shifting the distribution.
Pulling everything together, we have the following recurrence relation.
Note: δ-S(a,b) is the argument of Pa*Pb, not a multiplicative factor.
If program this up and sum over all the values for which δ>0, we find an answer of 59/105. And there we have it!
I’d like to reiterate that Vamshi and Josh had wonderful write-ups. I strongly encourage you to check them out. Josh includes some great plots of the win probabilities across different board sizes.
A plot from Josh’s write-up.
Vamshi included this fantastic flow chart of how the game proceeds.
A plot from Vamshi’s write-up.
Big thanks to them for their hard work! As always, please comment with any thoughts or feedback you had on this problem or if have any ideas for extensions of this problem. Thanks for reading!
