Too Much Free Time

Discussion and reviews of games for NES, Intellivision, DOS, and others.

Archive for June, 2015

Classic Nintendo Games are (NP-)Hard by Aloupis et al.

Posted by Tracy Poff on June 21, 2015

I came across an interesting paper on arXiv, “Classic Nintendo Games are (NP-)Hard” by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta. The paper is originally from 2012, but it’s been updated in February of this year with additional results. It’s been mentioned a few times on the web, but I didn’t see anyone give a satisfactory explanation of what the paper is really about. I’m not an expert, but I’ll give it a go.

First, though, the abstract:

We prove NP-hardness results for five of Nintendo’s largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to Super Mario Bros. 1, 3, Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games except Zelda II: The Adventure of Link; all Metroid games; and all Pokemon role-playing games. For Mario and Donkey Kong, we show NP-completeness. In addition, we observe that several games in the Zelda series are PSPACE-complete.

What does it all mean?

I’ll go into some detail shortly, but I’d like to describe in broad strokes what this is (and isn’t).

The authors look at how hard it is to answer the question: given a particular level layout, a starting point, and a finish point, is it possible to get from the start to the finish?

This isn’t about the levels actually in the games–in fact, it isn’t really about the level design at all. What it is about is the rules of the games. Super Mario Bros., for example, has several well-known rules:

  1. Mushrooms make small Mario big.
  2. Touching enemies (or some other hazards) makes big Mario small, or kills small Mario.
  3. Mario can break bricks only if he’s big.
  4. Stars make Mario temporarily invulnerable.
  5. Mario can jump to a height of 4 tiles, or 5 when running.

There are more rules, but you see the point. Importantly, the authors specify that their results are about an idealized version of the rules. In other words, glitches don’t count. Sorry.

What the authors prove is that if you turn someone loose with a level editor, they can design a level for which it is very hard to determine whether it’s even possible to complete.

They do this by showing that you can implement a problem called the 3-satisfiability problem (or 3-SAT) in each of the games. Think of someone using redstone to make Tetris in Minecraft, and you’ve got the general idea. 3-SAT is known to be NP-complete (read as: difficult), and the game it’s implemented in must be at least as hard as 3-SAT. Those problems are called NP-hard.

Details

The 3-satisfiability problem is to determine if, given a boolean formula of a certain form, it is possible to set the variables (which can be either true or false) in such a way that the whole formula comes out true. A two-variable example of 3-SAT might be:

(y is TRUE | x is TRUE | x is TRUE)
    AND
(x is FALSE | y is TRUE | y is TRUE)
    AND
(x is FALSE | y is FALSE | y is FALSE)

(Don’t be alarmed by the duplication. The reason for writing that way will be apparent later.)

The 3 in 3-SAT means that each clause (the parts in parentheses) can have at most 3 components. In this case, each has only two distinct components–one is repeated.

All three clauses must be true for the formula to be true, and a clause is true if any of its components (which are separated by pipes) is true. In logic-speak, it’s a conjunction of several disjunctions.

It’s pretty easy to see that this expression is true if y is true (satisfying the first part) and x is false (satisfying the other two). But what if there were fifty or a hundred or a billion sub-expressions? That would be harder to tell.

Requirements for 3-SAT

To be able to implement 3-SAT, you need a few components. You need:

  1. A starting point
  2. A finishing point
  3. A way to pick whether a variable is true or false
  4. A way for those choices to either impede or allow progress
  5. A way to let paths cross without being able to change from one path to another

That last one is so that you can build big, complex paths. Without it, you’d be able to backtrack and mess things up.

The authors implement these components in ‘gadgets’, which are basically self-contained rooms or screens that can be connected to each other. They’re the building blocks of the satisfiability puzzle.

Gadgets in Super Mario Bros.

I’ll take a brief look at how the authors build these gadgets for Super Mario Bros., as an example. This is going to be pretty much the same as what the authors say in the paper, so if you’re feeling industrious, you can look at the paper and see how they put it.

Start

The start gadget is just where Mario starts the level–there’s nothing to it. In general, the authors want Mario to be big throughout the level, so they put a mushroom at the beginning that will be required at the finish.

Finish

Again, this is trivial. It’s just the flagpole. To make sure Mario stayed big throughout the level, you have him enter the screen with the flagpole in a corridor with a brick he must break to reach the flagpole.

Finish gadget

Variable

To pick whether a variable is true or false, Mario is given a screen with two possible paths–a vertical drop to either the left or right. Say left means “x is true” and right means “x is false”. It doesn’t matter which. The drops are long enough that Mario can’t get back up, so once a choice is made, Mario can’t go back and also take the other path.

Clause and Check

This is the most interesting (and important) gadget in Super Mario Bros. Take a look at it:

Clause and Check gadget

After making a choice and dropping from the Variable gadget, Mario will be led to a series of Clause gadgets. He enters one of the small open areas from the bottom–each one of them will have a path from a Variable gadget that leads to it.

Each block contains a star, which will be trapped in the ‘fence’ when Mario hits the block. Later, Mario will come through the top part (that’s the Check part of the gadget) and collect the star so that he can run through the Firebars. If Mario gets to the Check gadget without having hit the star block (thus satisfying the disjunction), he can’t proceed–the Firebars will kill him.

Remember our example of 3-SAT from earlier?

(y is TRUE | x is TRUE | x is TRUE)
    AND
(x is FALSE | y is TRUE | y is TRUE)
    AND
(x is FALSE | y is FALSE | y is FALSE)

Imagine that the gadget pictured corresponds to the top disjunction, (y is TRUE | x is TRUE | x is TRUE). Then Mario will reach the left star block if he picked “y is TRUE” by dropping down the left side of the corresponding Variable gadget, and the middle and right star blocks by picking “x is TRUE” by dropping down the left side of that particular Variable gadget.

But what if Mario picked “x is false” and “y is false”? Then he’d never get to the blocks and release the star, so when he got to the Check gadget, the Firebars would kill him. That means that both variables being false isn’t a solution to the expression, and (equivalently) taking the right path at both variable gadgets won’t let Mario finish the level.

Crossover

This is just a utility to let paths cross without Mario backtracking and making two different choices for one Variable.

Crossover gadget

If Mario comes in from the lower path, he can break the bricks and keep going up.

If he comes in from the upper path, he can run into the Goomba to become small, head to the right, pick up the mushroom from the block, break the brick, and continue to the right.

Small Mario can’t break the bricks in the middle to go up, and big Mario can’t get through the narrow paths to go to the right. Big Mario also can’t break the bricks and then go back, because the drop on the left is too far for him to get back up.

Putting it all together

You can string together as many Variable, Clause, and Check gadgets as you need to make as big of a problem as you want. Since we know that 3-SAT is NP-complete, and we’ve just implemented 3-SAT in Super Mario Bros., we know that SMB is NP-hard.

Congratulations! If you’ve made it this far, then you’ve got the major idea of (part of) the paper. Pick up your CS degree on the way out the door.

Other games, other problems

I won’t go into detail about the other sections of the paper, but if you’ve read this far, you should be able to read the paper and see what is being done. The proofs for other Mario games just make some modifications to the gadgets we looked at above.

The proofs for the Zelda games are different. They still work by implementing an NP-hard problem, but it’s a different problem, and they implement it using the sliding blocks in the Zelda series.

If you want to know about the other games, or get more details, take look at the paper.

Caveat lector

I’ve done my best, here, but I’m not an expert. I’ve got a BS in math, not a doctorate in computer science. If I’ve made some terrible mistake, it’s all my fault (and I’d appreciate it if you’d let me know!), and I apologize for anything misleading, confusing, or dangerous that I’ve written. Always wear proper safety equipment when proving theorems.

Bibliography

[Aloupis2012v3]
Greg Aloupis & Erik D. Demaine & Alan Guo et al., Classic Nintendo Games are (NP-)Hard, (2012-03-08).

Posted in General Commentary | Tagged: , , , , , , , , , , | Leave a Comment »

TIS-100

Posted by Tracy Poff on June 19, 2015

370360_2015-06-17_00004

Recently, I saw a new game from Zachtronics Industries, TIS-100, which was released on Steam as an early access title on the first of June. In some ways, calling it a game is overstating it: it’s little more than a collection of programming problems, with a little story to give it some structure. The catch is that you’re programming in an assembly language on a virtual machine with unusual architecture; problems beyond the simplest will generally require you to take advantage of parallelism (which is the primary distinguishing feature of the VM), resulting in novel solutions for ordinary problems.

370360_2015-06-17_00005

Obviously, a game like that has a rather limited target audience. Case in point: I have myself previously created a little VM with a fake assembly language to play with. The game is clearly made just for me, but how many others are likely to be similarly interested? About 11,000,1 so far. It’s a minor hit.2

The concept of programming as gameplay isn’t new. Indeed, Zachtronics’s earlier game, SpaceChem, is also an exercise in parallel programming, though dressed up in fancier clothes. Way back in the mists of time,3 Robot Odyssey challenged players to program the titular robots to solve puzzles. And on the more-programming-than-game end of the spectrum, we have Core War4 and a multitude of web sites in the vein of Project Euler or CodinGame.

I’ve been enjoying TIS-100, but more than that, I think it’s singularly impressive to release a game of this kind. Certainly, there are games that trade on their difficulty (Super HexagonI Wanna Be the Guy, etc.) and some that take pride in their difficulty of interaction (Surgeon SimulatorAmpu-Tea, QWOP, etc.), and simple ‘retro-style’ graphics are de rigueur for indie games, but the very minimalistic functionalism of TIS-100 is astounding.

TIS-100 is difficult because the thinking required to solve the puzzles is difficult. It is perhaps inaccessible, because it consists of nothing else but the tools to solve the puzzle. Its graphics are simple because everything you need to solve the puzzles is a text-mode interactive debugger, and that’s what you get. Like a sudoku puzzle or a crossword, TIS-100 is a completely pure puzzle game: the game takes place in your head, and the software keeps score.

It is not by chance that TIS-100 so distinguishes itself from other games. During the production of Infinifactory, Zach Barth, the founder of Zachtronics, wanted to make a game with a smaller team–something more-indie-than-indie–to get back to his roots as an indie developer. The project turned out to be too great in scope, but from its wreckage was salvaged a programming minigame which became TIS-100.5 Viewed as an indie developer’s attempt to make something even more indie, with the understanding that it was a small part of something larger, the design makes sense.6

The game’s manual, too, reflects the niche targeted by the game. Who reads a manual, you ask? When it is positioned as a technical document describing the instruction set of a virtual machine, the answer to that question is: programmers. The manual is presented as the in-universe manual for the TIS-100 computer, previously the property of the player character’s Uncle Randy, including handwritten notes and highlighting. This was part of Zachtronics’s attempt to make a game with “an irresistible value proposition. For us, that’s a game with a 14-page technical manual that we designed, printed out, marked up and scanned back in again.”7 The manual is reminiscent of the feelies accompanying Infocom games, among others, in years past.8

370360_2015-06-18_00001

Like its predecessor, SpaceChemTIS-100 encourages players to perfect their solutions, optimizing for either execution speed, least number of nodes used, or least instructions–goals which are often contradictory, requiring multiple solutions.

Perhaps unsurprisingly, given that it is a game about programming, the players of TIS-100 have created some auxiliary tools, including TIS-100 PAD,9 which allows users to more easily share solutions, and a variety of TIS-100 (the virtual machine, not the game) emulators.10

In addition to this unsolicited community participation, with the release of the specification editor, which allows players to make their own puzzles, a puzzle design contest was announced. Twenty-five puzzles will be selected from the submissions for an official bonus campaign.

The feel of TIS-100 is both nostalgic and quite modern. It’s an intriguing combination, and I recommend it to anyone still interested after hearing me call it “a collection of programming problems.” Coders, no prior experience with assembly is needed. Others, if you like this game–try coding. You’ll probably like that, too.

Bibliography

[Barth2012]
Zach Barth, Postmortem: Zachtronics Industries’ SpaceChem, Gamasutra (2012-06-13).
[Dewdney1984]
Alexander K. Dewdney, In the game called Core War hostile programs engage in a battle of bits, Scientific American 250, 5 (1984), 15–19.
[McIlroy1971]
M. Douglas McIlroy & Robert Morris & Victor Vyssotsky, Letter to Aleph-Null (1971-06-29).
[Wawro2015]
Alex Wawro, ‘Things we create tell people who we are’: Designing Zachtronics’ TIS-100, Gamasutra (2015-06-09).

  1. According to SteamSpy
  2. As of this writing, it has 270 positive reviews and 2 negative reviews on Steam
  3. 1984, actually. It was released a year later for DOS, according to MobyGames
  4. Also from 1984, described in a Scientific American article, [Dewdney1984]. It’s based on a still earlier programming game, Darwin, which was played in 1961 and described publicly in 1972. See [McIlroy1971] for more. 
  5. The details of TIS-100‘s inception, and more, are discussed in an interview published by Gamasutra, [Wawro2015]. 
  6. However, Barth wrote in a post mortem of SpaceChem, [Barth2012], that SpaceChem was too difficult and inaccessible. New titles were forthcoming: “New titles, I might add, that are hopefully more accessible than SpaceChem!” 
  7. From [Wawro2015]. 
  8. Back when you got something for your money! Even application software used to have much more bulk to it
  9. Source available on GitHub
  10. Just have a look at the results of this search. But watch out, if you’d like to avoid spoilers! The puzzle solutions are code, after all, so a number of people have posted those, as well. 

Posted in 2015, Full Review, Good, Puzzle, Windows | Tagged: , | Leave a Comment »