This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American
Now is your chance to prove some theorems without knowing what they mean! Chris Staecker, a mathematician at Fairfield University, created the game Nice Neighbors to get crowd-sourced solutions to problems from a field called digital topology. Whether that means anything to you or not, you might be able to help Staecker and his colleagues prove some theorems.
A screenshot from an unsolved 9-point level of Nice Neighbors. Screenshot from Nice Neighbors by Chris Staecker..
Game play is simple: drag points around and see if you can make it so you don’t have any red lines but at least one of the spaces is empty. Some levels of the game have been solved, and some haven’t. If there’s a beaker in the lower right corner of the game window, then you’re playing an experimental level that may or may not have a solution. If you solve it, you’ve managed to prove a new theorem about digital homotopy!
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
If you want to play without reading anything about math, don’t let me stop you. But if you’re interested in the math behind the game, read on.
Digital topology is a variation of classical topology that studies spaces with a finite number of points. It’s worth asking why we might want to be able to do topology on finite spaces. The word digital suggests the answer: the motivation comes from computer graphics and digital images. Every image we see on a computer is made up of a finite number of pixels, and it would be nice to be able to say that two images are related in some way just using information about those pixels. For example, can we tell a “B” from a “D,” no matter how they’re oriented, using only information about what colors of pixels are next to each other? That’s a question for digital topology. That’s right, one of the potential future applications is in making CAPTCHAS—those distorted images of words that websites employ to determine whether a user is human—easier for computers, and therefore harder for us, in a wiggly, blurry arms race.
Classical topology is the study of properties of shapes that remain the same no matter how you stretch or bend them, as long as you don’t tear them. Classical topology is most helpful for understanding spaces with an infinite number of points, such as a plane or a sphere—it isn't a good tool for studying a space with only a finite number of points in it.
The key difference between classical and digital topology is the definition of continuity. We are used to thinking about the continuity of a function as something to do with its graph. The graph of a continuous function can’t jump up or have a hole in it. This definition depends on being able to measure distances between points in the plane and being able to make those distances arbitrarily small. That’s all well and good, but it doesn’t help us very much when it comes to finite spaces where there is a limit to how small distances between points can get. If you only have three points in your space, there are at most three distances, and one of them has to be the smallest. Our normal idea of continuity doesn’t work very well if there is a minimum (nonzero) distance between points. In digital topology, continuity isn't based on distances (for the more abstract topologists out there who prefer to be free from the constraints of a metric, it isn't based on open sets either) but on connections between points in the space.
A digital image is a finite collection of points along with information about which ones are connected to each other. A map between two digital images is called continuous if every pair of points that are connected in the original images is mapped to a pair of points that are connected in the new image (or to the same point). In classical topology, the idea of homotopy is based on being able to scoot paths around in a continuous way, like sliding a rubber band around on a basketball. The definition of digital homotopy is just the same as in classical topology, but with a different definition of continuity. The new definition has some unexpected consequences that you can read about in a paper Staecker wrote with his summer research program students Jason Haarmann, Meg Murphy, and Casey Peters.*
The summer project the game is based on was to determine which digital images were irreducible, that is, which ones were not homotopic to digital images with fewer points. In their research, they categorized digital images of seven points or fewer and discovered criteria for two digital images to be homotopic. These criteria led to the rules for the online game.
The fact that they have only classified images up to seven points should assuage your CAPTCHA-related fears. Digital topology won’t make it harder to post your very important opinions about rainbow cakes and/or communism just yet. The difficulty of the problem grows very quickly as the number of points increases. Nice Neighbors is an effort to extend the classification to eight- and nine-point spaces. They were able to reduce the number of cases to 160 for the eight-point case and 3,251 for the nine-point case (which is more impressive if you know there are 11,117 possible digital images of eight points and 261,080 of nine).
Technically, the game can only show that digital images are reducible. To show conclusively that an image is irreducible amounts to showing that something doesn’t exist, which is harder than showing that something does exist by finding it. But if a lot of users fail to solve one of the levels, that’s pretty strong evidence that the image is irreducible, and Staecker or other researchers can try to prove conclusively that the image is irreducible. Currently, there are approximately 30 unsolved eight-point images, and Staecker thinks they’re probably irreducible. Only a few hundred of the nine-point levels have been solved, so there’s still plenty to do.
When Staecker first got the idea to make the game, he wasn’t sure whether it would be any fun. “With normal games, you have some idea of what you want the game to be about, and then you make the game, and you maybe change the rules to make it easier or harder or more fun,” he says. “That’s not really possible with this one. I had the rules first and had to make the game around them. It kind of had to be designed the way it was, and whether it was going to be fun or not wasn’t really up to me."
Staecker was inspired to by the graph theory game planarity.net. As the name suggests, the goal of that game is to rearrange a picture of a graph until it’s obviously planar, that is, until none of the edges cross each other. Both Planarity and Nice Neighbors are surprisingly addictive, so play at your own risk!
*This sentence originally misspelled Casey Peters' name. Sorry, Casey!