THE MATHEMATICS OF PLINK

Main Content

Part of the motivation for building Plink was to explore the beautiful mathematics behind how pieces shuffle when the board is rotated. This shuffling action gives rise to a number of fascinating questions, some of which are active subjects of research among professional mathematicians.

Cycles and repeated rotation

If you rotate the Plink board enough times in the same direction, you'll eventually see the board start to cycle through a fixed sequence of patterns. In mathematical language, we say that the configuration of the Plink board is eventually periodic under rotation. The period of a given configuration, that is the number of rotations it takes to return to its starting point, behaves in a very interesting manner as you change the number of pieces and blockers.  This suggests the following question: What is the maximum period of a Plink board with n pieces, and how does this number grow as n increases?  As it turns out, this question  is equivalent to the notorious  Riemann Hypothesis.  The Riemann Hypothesis has been unsolved for over 150 years,  is widely considered one of the most important problems in mathematics.  In fact, it is one of the Clay Millenium Problems, worth $1,000,000  to the first person who solves it! 

The shape monoid

The way in which left and right rotations relate to one another in Plink offers another fascinating level of mathematical structure. One way to study this relationship is to ignore the colors and numbers of the pieces and simply focus on which positions on the Plink board are occupied by pieces or gates. We refer to this as the shape of the Plink board. If there are no blockers present, it turns out that there are at most 4 different shapes that can be reached from a given position. With blockers, however, things are much more complicated. The picture to the left shows the shapes that can be reached from a single position with 5 pieces. Each dot represents a different shape, each green arrow represents a clockwise rotation, and each blue arrow represents a counter-clockwise rotation. Mathematically, this structure is called a two generator monoid. Plink offers a very rich collections of such objects, which suggests the following question: Which monoids appear as shape monoids of Plink boards?. Though this question is not worth $1,000,000, but I'd gladly offer some prize money to the first person who can tell me the answer.

Stability

One interesting feature of Plink is that certain shapes are unstable. These are shapes that we can get to from a given starting position but that, after some sequence of rotations we can never return to again. It's important to understand stability when designing Plink puzzles - after all, if the target shape is unstable then it's possible to mess up the puzzle in such a way that it can't be solved without starting over. Luckily, it's an interesting mathematical fact that after enough random rotations, we always end up with a shape that is stable, i.e. we can get back to it no matter which rotations we do. These shapes lie in what are called stable attractors and a single Plink monoid can have several of these. More generally, the Plink monoid break up into strongly connected components (SCCs), which are regions of mutually accessible configurations. These SCC's fit together into what's called a component graph, which has a special structure that mathematicians call a directed acyclic graph (DAG). This raises the following question: Which DAGs appear as component graphs for a configuration on an n-by-n Plink board?

Permutation Groups

A sequence of rotations that returns the Plink board to its initial shape usually shuffles the pieces in the process. In solving Plink puzzles, we're often faced with the following question: how many different shuffles like this are possible? Mathematically, these collections of shuffles are called permutation groups.. Many interesting groups show up in on the Plink board, which leads to another interesting question about Plink: Which permutation groups appear within Plink for an n x n board?





The variability of the Plink board leads to some interesting challenges, both as a human player and in designing Plink AI. A strategy that is successful for one game set-up may be useless for another, so programming successful AI to play Plink requires finding a highly adaptable algorithms. On the other hand, the complexity of Plink is high enough that simple search algorithms aren't computationally feasible. In order to design AI that is adaptable, the Plink App's AI is programmed using a mixture of qualitative case-based strategy and Monte Carlo simulations that simulate hundreds of game outcomes to see which moves are the most promising. While this approach works relatively well at first, after a bit of practice a good human player can learn to beat it pretty quickly. This raises the following question: What's the best way to build AI that can play Plink effectively across all board configurations?