Life, Complexity, and Roguelikes

While two-player strategy games (Go, Chess) are very important in our culture, and puzzles (both pen-and-paper and computer-based) are quite popular, roguelikes are not as well understood by the gamers in general. I think this is because that, while at times they feel similar to puzzles or Chess, puzzlers and Chess players will look for things they know from their favorite games. Chess players will look at roguelikes weird because the monsters do not move intelligently. Puzzlers will be annoyed because sometimes they will lose roguelikes due to bad luck, and perceive that as bad design. However, roguelikes do not need being designed to be always solvable, nor intelligent opponents, because they bring something fundamentally new to the table. This post is about what I believe to be an interesting parallel between game design and complexity theory.

Let us start with “boring” things in life: cleaning up your room, getting from home to work/school and back every day… These things are boring, because you follow a specific, deterministic algorithm, without any space for creativity. In gaming, we have grinding — you do not do anything challenging or creative, but you become more and more powerful; this is also boring, by roguelike standards at least. Computers are great at following such deterministic algorithms, and nowadays many of such boring tasks are performed by computers; cleaning corresponds to sorting, getting from home to school corresponds to pathfinding, and algorithms for these tasks are well known. However, an existence of a fixed algorithm is not sufficient — that algorithm also needs to run in feasible time. In complexity theory, the running time is usually considered to be feasible if it is polynomial in the size of the input (an approximation, but it leads to a beautiful theory), so we call this Deterministic Polynomial Time, or P for short.

In practice, not everything we do has to be deterministic. In statistical research, we randomly select a sample from a population, and we hope that the results of analysing that sample will still hold for the whole population. There is a chance that we had bad luck while selecting a sample, and we obtain incorrect results; but that chance can be generally made very low. We also have Monte Carlo algorithms, which work in similar way: they run in feasible time, but they are based on randomness, and there is a low chance that they yield an incorrect result (the Rabin-Miller primality test is a well known example). In complexity theory, this is called Bounded-Error Probabilistic Polynomial Time, or BPP for short. In the usual definition of BPP, one gets the correct result with probability of at least 2/3; however, the test can be repeated — if we repeat 4000 times and take the most frequent answer (“majority voting”), the error probability is below 10–100, which is zero for all the practical purposes. This is a bit more exciting than full determinism, but not much… And computers are still very good at performing such algorithms, and do not mind repeating them 4000 times.

Now, typical puzzles and puzzle games are more interesting. The player who solves the puzzle does not follow any specific algorithm; however, their solution is verified by a computer (or checked manually, for more oldschool puzzlers), and that verification is done in polynomial time. We call this Non-deterministic Polynomial Time, or NP for short. The word non-determinism used in complexity theory suggests some kind of randomness, but in fact this is very different from randomness, as we assume that the player is generating their solution in an intelligent, rather than random way — they do their best to find a solution to the puzzle. Most people believe that P does not equal NP, which means that, in general, fast deterministic algorithms do not exist for solving such kinds of puzzles: even if it is possible to verify a solution in feasible time, it might not be possible to feasibly find one with a deterministic algorithm. Many people believe mathematics to be boring because it feels to them like performing fixed algorithms with no creativity; but people who love mathematics have seen good math problems, and know how creative it really is. Finding a solution to a good math problem is challenging and creative, even though you use a deterministic algorithm to verify the correctness of such a solution. For example, it was found very recently that 33 is a sum of three cubes: 33=8866128975287528³+(-8778405442862239)³+(-2736111468807040)³. It is very easy to verify that this solution is correct, but it was extremely hard to find it!

Some people think that NP means Non-Polynomial; this is incorrect. As seen above, NP is still restricted in its own sense: we do not have to solve the problem in feasible time, but we do have to check the answer in feasible time. There are complexity classes over NP, and we can get the next major complexity class by relaxing further restrictions. For example:

• Sokoban is a puzzle where, even though the puzzle does not have too many elements, it is possible that executing the solution will take more time — exponentially many in the size of the puzzle. When we no longer restrict the verification time to be polynomial, but instead we only force it to run in feasible memory (i.e., everything fits on a small puzzle board), we get the complexity class Non-deterministic Polynomial Space, or NPSPACE. (Non-deterministic because the Sokoban player still does not follow a deterministic algorithm, but they think creatively, in a non-deterministic way.)
• We have said that the puzzle solver does their best to find a solution to the puzzle. Two-player games such as Chess or Go are more complicated: there is also another player, as intelligent and creative as the first one, who does their best to destroy that solution. The two players alternate their turns, so if the whole game ends in feasible time, we call this Alternating Polynomial Time, or AP.
• In the definition of NP, we have assumed that the algorithm who verifies the solution is deterministic. But why not allow them to use randomness? The intelligent and creative player has to show they can solve the puzzle; but the puzzle is randomized rather than fixed, and verified by a program that uses randomness (but does not do their best to destroy our solution). This complexity class is called Interactive Polynomial Time, or IP. As with BPP, we allow some error due to the nature of randomness: the player may be very unlucky and lose even if they should win, or very lucky and win even if they should lose. These events should be rare, though (probability below 1/3 in the standard definition of IP).

Now, all the complexity classes roughly introduced above (NPSPACE, AP, IP) are actually the same class, commonly called PSPACE (Deterministic Polynomial Space — yes, it is known that PSPACE=NPSPACE, i.e., non-determinism does not make things harder when we only want space to be feasible rather than time). We suspect that PSPACE is harder than NP though, just as we suspect that NP is harder than P. In fact, we even do not know whether PSPACE is harder than P: even though it may not be possible to execute a solution to Sokoban in feasible time, it is possible that there exists a feasible algorithm to tell whether we will eventually win.

Now, what that has to do with roguelikes? Well, puzzle games such as Sudoku or most computer-based ones correspond to NP, as well as Sokoban (assuming that the designer was actually not sadistic enough and the solution can actually be executed in polynomial time). Games such as Chess and Go correspond to AP=PSPACE (assuming that we add extra rules which restrict the game to feasible time, otherwise they may be harder than PSPACE). Roguelikes correspond to IP: even if the enemies in roguelikes are not intelligent, they are potentially as complex as games against an intelligent opponent!

A catch is that Sudoku and Minesweeper (a fixed Minesweeper puzzle, not the random game) are NP-complete, and (polynomially restricted and generalized) Chess and Go are PSPACE-complete; this means that they are the hardest problems in their respective complexity classes, any other NP (PSPACE) can be reduced to them. We do not know yet any PSPACE-complete roguelike, although it would be possible to extract one from Shamir’s proof that IP=PSPACE (probably not a very interesting one, though).

Some thoughts and consequences related to all this:

• Enemies in roguelikes are usually stupid, but that is perfectly fine! Roguelikes do not need intelligent enemies to be as complex as games played against intelligent opponents. In many roguelikes, enemies who move randomly are actually considered the most dangerous ones — because they could by chance move in an intelligent way, and if they do and your strategy does not take that into account, you lose!
• It is also perfectly fine that not every run in a roguelike can be won. If you lose, simply play again (and you will win eventually). If you win by insane luck (rather than by skill), play again, and probably you will not win. If a roguelike designer tried to eliminate the probability of losing altogether, they would have to sacrifice the complexity, as they would be back at the less complex NP. (Of course both NP and PSPACE seem to be above the capabilities of both humans and computers, so it does not really matter. But we still lose the fun of roguelikes.)
• One problem with two-player games is that it may be difficult to find a good opponent. I often have problems finding people to play two-player games against, because they assume that I would crush them easily (probably incorrectly — if that would be the case, the game would not be interesting for me and I would not offer it). Computers do not really solve this — in my experience, AI is just a deterministic algorithm, that the player has to understand, and exploit its weaknesses. That turns such games into NP (or IP if there is some randomness); roguelikes with their predictable AIs win there, because the challenge is more clear.
• As said above, the probability of getting a wrong answer in a BPP algorithm or an interactive proof (IP) is 1/3 by definition, but we only need to repeat the algorithm many times to make that probability practically zero. Similar methods are used by roguelike designers. For example, in HyperRogue, the Orb Strategy Mode provides you with Orbs, which can save you from an otherwise unwinnable situation; however, the number of Orbs is limited. This corresponds to the “majority voting” used in probabilisitic algorithms: it practically eliminates the probability of a good player losing the game, or a bad player winning. Other roguelikes have this in form of resource management; in fact, resource management is one of the high value factors in the Berlin Interpretation. However, this is not really necessary — HyperRogue Classic, and some of the puzzle roguelikes, do not do this; that is still fun (and in some cases probably even more exciting), because if you really lose the game due to bad luck, you can always play again. I believe the most popular games based on randomness (Minesweeper, solitaires…) are actually pretty bad at this; in my experience, you often solve a Minesweeper board almost completely just to run into a wild guess in the end.
• One thing that games such as Go and Chess have is symmetry. If someone plays Go much better than me, they will crush me, even though it is completely obvious that I had an advantage (Go has a great handicap system); at the same time, I can see that the game is very deep: just as X crushes me, I crush a newbie easily, and a world champion would crush X. Roguelikes are asymmetric, with an alien opponent that is based on randomness, rather than intelligence similar to ours. Most great roguelikes are fair: the best players can win 20 games in a row. However, because of asymmetry, a newbie will not know what mistakes they are making, and assume that the game can be won only with insanely good luck.

The most popular indie game designers seem to be more excited about deterministic puzzle games than roguelikes. On the other hand, I find roguelikes much more exciting, because they are more like real life: there can be no solution, or there can be multiple solutions. This also happens in multi-player games, but they need a worthy opponent, and finding one might be difficult. (I have seen the recent puzzle hit Baba is You praised for having multiple solutions; however, in roguelikes, this is given.) In a typical puzzle game you mostly find what the designer has put in it; in a roguelike, or a two-player game, the developers do not know these solutions themselves. Roguelikes have a strong tradition of not being created for money, but from the desire of creating a game that is interesting to the developer themselves. In general, creative activities, such as programming, game design, or scientific research, are also like this: there can be no solutions, a solution may require so deep understanding that years have to pass before we arrive there, or there can be multiple solutions. I do not play puzzle games that much myself, because programming HyperRogue is much more interesting (especially, I do not feel attracted to programming puzzle games — why should I play them when I can program real things?). This might be one of the reasons why there seems to be an extraordinarily high proportion of creative types among roguelike players — sometimes it seems that every roguelike player is also a roguelike developer themselves.