Mathematicians tried to prove how hard The Witness is - with surprising results

"Each clue type ended up offering a whole interesting problem to study."

The Witness is a curious, persnickety game. On one hand, it is heralded as a champion of pretentiousness. On the other, it is widely lauded for its mathematical complexity. The Witness' rules are mapped by symbols on its chessboard grids, and although they look quite simple, there's a lot more going on than meets the eye - so much so that some study what exactly makes The Witness' problems difficult at a doctoral level.

Erik Demaine, a professor in computer science at MIT, primarily focuses on research and teaching, and often combines the two by tasking students with solving open problems in groups. To do this, Demaine uses a highly collaborative style of research called supercollaboration.

According to Demaine's site - linked above - supercollaboration is an innovative research method where researchers solve complex problems without concern over authorship or ego. It is, quite literally, supercollaborative, in that positive and effective teamwork takes precedence over individual input. If you're especially interested, I've embedded a video of a class taught using a supercollaborative model below.

Demaine was one of the main authors of a 2018 paper called Who witnesses The Witness?, which provides an exemplary case of supercollaborative research while simultaneously extrapolating what makes The Witness a game worth studying for doctoral mathematicians and computer scientists: primarily, its difficulty.

For those unacquainted with the term "witness" in a maths context, it's a specific value subbed into an existential statement - basically, it is an entity used to differentiate between something existing, something existing in at least one case, and something existing given certain conditions. In the case of The Witness, the lower-case witness has to do with the ways in which puzzles are actually solved - it's about which strategy is successful, and what path(s) through a grid represents that.

So, who witnesses The Witness? As it turns out, it is remarkably difficult to tell - and that's why it's so academically enticing.

Demaine's team often studies games in order to search for efficient algorithms, and to analyse computationally-intractable problems as a means of tracing innovative solutions that are often derived out of left-field.

"In general, we wanted to try to delineate the boundary between computationally easy and computationally hard aspects of The Witness' puzzles," Demaine says. "Some puzzles use one clue type, while others use a mixture of clue types. We wanted to understand which mixtures make puzzles that are hard for computers to solve, and thus probably [also] difficult for humans, and which are actually easy for computers to solve - though that doesn't mean they're necessarily easy for humans."

"The latter is rare in general when analysing puzzles in this way, so the monominoes case was pretty exciting," he adds.

Hardness proofing is one of the key aims of Demaine's research and teaching. The art of proving hardness is difficult: it involves finding a proof for why a problem is difficult by transforming or reducing it into a separate problematic form. Along the way, interesting algorithms that can be applied elsewhere are discovered - grappling with the computationally difficult begets solutions for simplication, which means arriving at something that is ultimately easier to use by further complicating what's under the hood.

Adam Hesterberg is another researcher credited on Who witnesses The Witness? Although he was a PhD student in maths at MIT when he started working with Demaine, he now studies computer science at the post-doctoral level. To him, The Witness looked "computationally interesting".

"I hadn't played The Witness until we decided to work on its computational complexity, although I do do similar logic puzzles," he tells me. "I like board games, either German-style economic resource management games like Gaia Project or anything by Vlaada Chvátil, after whom I named my apartment. Our research group occasionally writes papers on other games."

Demaine's group started work on Who witnesses The Witness? in 2016, two years before it was published as a FUN (from the International Conference of Fun with Algorithms) paper in 2018. It would eventually culminate in a full journal paper co-authored by 10 academics from across three departments at MIT, and one university in Germany.

They're not solely focused on The Witness, though: Demaine's group grapples with computational systems in a variety of other games, too, usually applying the same hardness proofs in order to prove difficulty and discover alternative algorithms.

"The computational complexity of games and puzzles is a topic dear to my heart which I've been studying since around 2000," Demaine explains. "My first paper was about Clickomania, which we recently revisited."

Demaine points to his papers on Tetris being NP-complete - meaning it can be solved by a restrictive class of brute force search algorithms - and Super Mario Bros. being PSPACE-complete, which is a lot more complex - as some of his most popular achievements in the field to date. But what makes The Witness stand out? "When The Witness came out, it seemed like a natural game to tackle, offering a variety of different puzzle/clue types within it," Demaine explains. "Because part of playing the game is figuring out what the clues actually mean, we first warned the group we were going to study The Witness, and encouraged those who wanted to avoid spoilers to play the game and figure things out for themselves.

"A couple of weeks later, we jumped into analysis, and each clue type ended up offering a whole interesting problem to study."

Jeffrey Bosboom, who has been a PhD student at MIT since 2011 and co-authored Who witnesses The Witness?, first encountered The Witness when it was brought up during one of the team's weekly supercollaboration sessions. "That means I was spoiled about most of the puzzle types," he tells me. "But I don't feel being spoiled reduced my enjoyment when I played it; the intro puzzles in each area are didactic anyway, and it was still fun to feel the transition from explicit knowledge (being able to tell someone the meaning of a symbol) to implicit knowledge (looking at a puzzle and immediately recognising what the solution must be)."

One of the most unusual things about The Witness' puzzles is some are Sigma_2-complete, Demaine notes. For those who are a bit unsure what that means - which I certainly was! - Sigma_2-completeness refers to a point in the polynomial hierarchy, which features a variety of different levels of problem-solving complexities.

NP-completeness involves solving problems using brute force; Sigma_2-completeness is a step up from that; and PSPACE-completeness is more complex yet again, having to do with polynomial time (the amount of time it takes for a computer to solve a problem) and time complexity (the computational complexity of the amount of time it takes a computer to run a specific algorithm).

It's a little difficult to parse, but according to Demaine The Witness' puzzles - at least the ones featuring "antibodies," which I'll get to in a minute - are planted firmly in the middle of the three, existing as "a level up from the usual NP-completeness, while being far below PSPACE-completeness common to puzzles that require exponentially many moves - like sliding blocks or Rush Hour".

The clues labelled as "antibodies" in the paper, which are the logic rules that cancel the effect of other clues in the same region of a given puzzle, have an inherent "necessity" qualifier that requires a slightly more hypothetical approach to problem-solving. This increases the computational complexity and provides an interesting array of problems that can be transformed into one another in order to come up with new, efficient algorithms (transforming one problem into another form is also a quality of Sigma_2-completeness).

"Another unusually interesting case was The Witness with just monomino clues," Demaine adds. A monomino is a single square of a polyomino, which is a shape formed by stitching equally-sized squares together. The Witness features grids in both forms.

"[It] reduces to hexagons on the boundary of a puzzle, which both turn out to be solvable by an efficient algorithm," Demaine adds. Reduction is the transformation of a problem into another, more complex variant of itself, and is often used in the study of hardness, whereas "hexagons" refers to edges or vertices that must be visited to satisfy a solution. As Demaine notes, this is an important stage of discovering and defining algorithms.

"In such puzzles, the goal is effectively to find a path visiting specified vertices and/or edges on the boundary of a planar graph, which is a kind of subset Hamiltonian path problem," he says. "Our algorithm to solve this problem is of interest beyond just puzzles."

"Subset Hamiltonian path fits into the broader field of graph algorithms (not puzzle analysis), so it contributes to that broader field," Demaine adds. "We were originally just trying to solve a fun puzzle - monominoes in The Witness - and we encountered a graph problem of broad interest, and then solved it because we wanted to solve the puzzle.

"But the contribution ends up being much broader than 'we solved a puzzle' - we also came up with a graph algorithm that might help solve other problems."

"My favourite puzzle in The Witness is the audio-less audio puzzle in the anechoic chamber room in the town," says Bosboom. "It's an easy puzzle, just checking you understand the correspondence between the two different types of audio puzzle panels, but it's the puzzle that gave me the most pronounced feeling of thinking along with the puzzle designers.

"In terms of my academic career, The Witness is a very rich source of interesting problems in computational complexity, that is also popular and interesting to many other people," he adds. "It's a very good - [but] not perfect - game. There's nothing mystical about it."

In Demaine's eyes, most games are sufficiently interesting to hazard study from the perspective of computational complexity. "Even games with minor amounts of puzzling can be pretty interesting," he explains. "For example, two of our co-authors on The Witness wrote another FUN 2018 paper about how cooperation in games like Team Fortress 2 or Super Smash Bros. or Mario Kart makes these games computationally very, very difficult."

"It's hard to formalise what it means for a game to be 'fun,' " he adds. "But I think one reason people like playing games is because they're challenging, and this research formalises what it means for a game to be challenging, so we get at some fundamental aspect of fun in games."

According to Demaine, there are researchers who complain that studying games is recreational, with the implication that the field is a waste of time.

"But I think recreational computer science research is an important avenue of study," he says. "In particular, it gets students excited about doing research, and it makes the research especially fun to do."

Will you support Eurogamer?

We want to make Eurogamer better, and that means better for our readers - not for algorithms. You can help! Become a supporter of Eurogamer and you can view the site completely ad-free, as well as gaining exclusive access to articles, podcasts and conversations that will bring you closer to the team, the stories, and the games we all love. Subscriptions start at £3.99 / $4.99 per month.

ncG1vNJzZmivp6x7psHRqJ6apZWne6%2Bx02iYq6yZmLmmv45rZ2toXWWEbnyWZqSarJioeqbEz56pratdlr%2BmedKtrJ2xmaO0bsDHnmSwoaSjsrS%2FjLCgraBdqMKzvNGiqqKml2K%2Fpr%2FUpaus