“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).
