Lesson 11. The Complexity of Video Games
I628E – Information Processing Theory

Giovanni Viglietta
johnny@jaist.ac.jp

JAIST – January 27, 2020

Decision problems

instances
x

f (x)

YES
NO

Example: Prime?

instances
Prime 

29
101

13
6

YES

37
24

8

45
89

NO

Basic complexity classes
P: problems decidable in polynomial time (i.e., “efficiently”)
NP: problems verifiable in polynomial time, given a certificate

NP
P

Prime
Reachability
2-Satisfiability

3-Satisfiability
Hamiltonian Path

Observation: P ⊆ NP
Open problem: is P ( NP or is P = NP?

Reductions

problem A

problem B

YES

YES

NO

NO

If A is reducible to B and we can solve B efficiently, then we cansolve A efficiently (given an instance of A, apply the reduction, andsolve the resulting instance of B)

NP-hard problems  -hard
problem

reductions

A problem is NP-hard if all the problems in NP can be reduced toit (i.e., it is at least as hard as every NP problem)

NP-complete problems

NP

NP-hard

NP-complete
A problem is NP-complete if it is NP-hard and it is also in NP(i.e., it is the “hardest problem” in NP)

NP-complete problems: examples

NP
P

Prime
Reachability
2-Satisfiability

NP-C

3-Satisfiability
Hamiltonian Path

Observation: if one NP-complete problem is solvable inpolynomial time, then P = N P = N P -complete

3-Satisfiability

Perhaps the most important NP-complete problem:
3-SAT
Input: a Boolean expression of the form:
positive literals

negative literals(x ∧ ȳ ∧ z ) ∨ (¯x ∧ z ∧ w) ∨ (y ∧ z̄ ∧ w̄) ∨ (¯x ∧ y ∧ w)

clauseOutput: YES if there is a truth assignment to the variables thatmakes the expression true. NO otherwise.

Generalizing (video) games
Guideline: “Expand the board, but do not change the rules”

Generalizing (video) games
Guideline: “Expand the board, but do not change the rules”

Generalizing (video) games
Guideline: “Expand the board, but do not change the rules”

Generalizing (video) games
Guideline: “Expand the board, but do not change the rules”

Add more platforms and enemies, but do not change the “physics”

Generalizing (video) games
Guideline: “Expand the board, but do not change the rules”

Add more platforms and enemies, but do not change the “physics”
Basic decision problem: is a given level beatable?

NP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness framework for platform games
Reduction from 3-SAT to a generic platform game

Start

x

FinishVariable

Variable

x ¬x

y

¬y

Clause

z

x

y

¬y

ClauseVariable¬yz¬x ¬ y ¬ zClause¬z¬x ¬ y ¬ zClauseNP-hardness gadgets

Start
FinishVariable, with mutual exclusion between outgoing paths
Clause, initially locked, and unlockable from three paths
Crossover, unidirectional, single-use, and fixed traversal orderNP-hardness gadgets

Start
FinishVariable, with mutual exclusion between outgoing paths
Clause, initially locked, and unlockable from three paths
Crossover, unidirectional, single-use, and fixed traversal order

Theorem (1)If all the above gadgets are present =⇒ NP-hardSuper Mario Bros. (NES)Super Mario Bros.: NP-hardness

Start gadgetSuper Mario Bros.: NP-hardness

Finish gadgetSuper Mario Bros.: NP-hardness

x = truex = false

Variable gadgetSuper Mario Bros.: NP-hardness

Variable gadgetSuper Mario Bros.: NP-hardness

Variable gadgetSuper Mario Bros.: NP-hardness

Variable gadgetSuper Mario Bros.: NP-hardness

Variable gadgetSuper Mario Bros.: NP-hardness

Variable gadgetSuper Mario Bros.: NP-hardness

check out

check into variable
to variable
to variable

Clause gadgetSuper Mario Bros.: NP-hardness

Clause gadgetSuper Mario Bros.: NP-hardness

Clause gadgetSuper Mario Bros.: NP-hardness

Clause gadgetSuper Mario Bros.: NP-hardness

Clause gadgetSuper Mario Bros.: NP-hardness

Clause gadgetSuper Mario Bros.: NP-hardness

Clause gadgetSuper Mario Bros.: NP-hardness

Clause gadgetSuper Mario Bros.: NP-hardness

Clause gadgetSuper Mario Bros.: NP-hardness

Clause gadgetSuper Mario Bros.: NP-hardness

Clause gadgetSuper Mario Bros.: Crossover gadgetSuper Mario Bros.: Crossover gadgetSuper Mario Bros. 2 (NES)

Clause gadgetMetroid (NES)Metroid: NP-hardness

Clause gadgetMetroid: NP-hardness (Crossover gadget)Donkey Kong Country (SNES)

Donkey Kong Country: NP-hardness

Clause gadget

Donkey Kong Country: NP-hardness

Crossover gadget

The Legend of Zelda: A Link to the Past (SNES)

The Legend of Zelda: NP-hardness

Variable gadget

The Legend of Zelda: NP-hardness

Clause gadgets

The Legend of Zelda: NP-hardness

Crossover gadget

Pokémon (Game Boy)

Pokémon: NP-hardness

Clause gadget

Pokémon: Crossover gadgetMore complexity classes
PSPACE: problems decidable in polynomial space (i.e., using only
polynomially many bits of “memory”)
EXP: problems decidable in exponential time (i.e., not necessarily“efficiently”)

NP
P

Prime
Reachability
2-Satisfiability

PSPACE
NP-C

3-Satisfiability
Hamiltonian Path

EXP

PSPACE-C

Quantified Satisfiability

More complexity classes

NP
P

Prime
Reachability
2-Satisfiability

PSPACE
NP-C

3-Satisfiability
Hamiltonian Path

EXP

PSPACE-C

Quantified Satisfiability

Observation: P ⊆ NP ⊆ PSPACE ⊆ EXP

Theorem: P ( EXP

Hence at least one of the inclusions in the chain is strict

Quantified Satisfiability
Recall that the 3-SAT problem asks if there is a truth assignmentthat satisfies an expression of the form:(x ∧ ȳ ∧ z) ∨ (x̄ ∧ z ∧ w) ∨ (y ∧ z̄ ∧ w̄) ∨ (x̄ ∧ y ∧ w).
In other words, it asks if the following formula is true:∃x, ∃y, ∃z, ∃w, (x ∧ ȳ ∧ z) ∨ (x̄ ∧ z ∧ w) ∨ (y ∧ z̄ ∧ w̄) ∨ (x̄ ∧ y ∧ w).
Generalizing, we can alternate ∃ and ∀ quantifiers, and ask if thefollowing formula is true:∃x, ∀y, ∃z, ∀w, (x ∧ ȳ ∧ z) ∨ (x̄ ∧ z ∧ w) ∨ (y ∧ z̄ ∧ w̄) ∨ (x̄ ∧ y ∧ w).
The QSAT problem asks if a fully quantified Boolean expression istrue. It is the canonical PSPACE-complete problem.

PSPACE-hardness framework

Blueprint of a reduction from QSAT

Start
Finish∃x

Clause∀yClause∃z

Clauseyt∀w

ClauseClausePSPACE-hardness framework

Blueprint of a reduction from QSAT

Start
Finish∃x

Clause∀yClause∃z

Clausey = w = true∀w

ClauseClausePSPACE-hardness framework

Blueprint of a reduction from QSAT

Start
Finish∃x

Clause∀yClause∃z

Clausey = w = true∀w

ClauseClausePSPACE-hardness framework

Blueprint of a reduction from QSAT

Start
Finish∃x

Clause∀yClause∃z

Clause∀w

Clausey = true, w = false

ClausePSPACE-hardness framework

Blueprint of a reduction from QSAT

Start
Finish∃x

Clause∀yClause∃z

Clause∀w

Clausey = true, w = false

ClausePSPACE-hardness framework

Blueprint of a reduction from QSAT

Start
Finish∃x

Clause∀yClause∃z

Clause∀w

Clausey = false, w = true

ClausePSPACE-hardness framework

Blueprint of a reduction from QSAT

Start
Finish∃x

Clause∀yClause∃z

Clause∀w

Clausey = false, w = true

ClausePSPACE-hardness framework

Blueprint of a reduction from QSAT

Start
Finish∃x

Clause∀yClause∃z

Clause∀w

Clausey = false, w = false

ClausePSPACE-hardness framework

Blueprint of a reduction from QSAT

Start
Finish∃x

Clause∀yClause∃z

Clause∀w

Clausey = false, w = false

ClausePSPACE-hardness framework

Blueprint of a reduction from QSAT

Start
Finish∃x

Clause∀yClause∃z

Clauseyt∀w

ClauseClauseDoors and Pressure plates
When stepping on a Pressure plate,a specific Door opens (or closes)

Doors and Pressure plates
When stepping on a Pressure plate,a specific Door opens (or closes)

Doors and Pressure plates
When stepping on a Pressure plate,a specific Door opens (or closes)

Doors and Pressure plates
When stepping on a Pressure plate,a specific Door opens (or closes)

Doors and Pressure plates
Pressure plates can be found anywhere in the level, and they canact on Doors located arbitrarily far from them:
Door “a”aaaPressure plate that
opens Door “a”

Pressure plate thatcloses Door “a”

Next we will see how to implement the PSPACE-hardness
framework with only Doors and Pressure Plates:
Theorem (2)Doors + Pressure plates =⇒ PSPACE-hardPSPACE-hardness framework: implementation
1

Start
Finish

∃x

∀y

∃z

∀w
2

ClauseClauseClauseClauseClause3

Clauseb x1 x2 ... x1 x2 ... a ad y1 y 2 ... y1 y 2 ... a a
d

c

c

c

a

a x1 x2 ... x1 x2 ... b b
y1 y 2 ... y1 y 2 ... b bbdExistential gadget

Universal gadgetPrince of Persia (PC, Amiga)Prince of Persia (PC, Amiga)Prince of Persia (PC, Amiga)

Pressure plate that must be pressedQuake (PC)

Quake (PC)Sonic (Sega Genesis)

Sonic (Sega Genesis)

Adventure games by LucasArts and Sierra

From Pressure plates to Stand-alone Doors
Observation: in our implementation of the PSPACE-hardness
framework, we only used two Pressure plates per Door: one that
opens it, and one that closes it. We can incorporate these threeelements in a single Stand-alone Door gadget:
open
a

a

a

traverse
close

The “open” path may even give the player the option to leave thedoor closed: indeed, choosing not to open a door is never helpful!
Theorem (3)Stand-alone Doors + Crossovers =⇒ PSPACE-hardPSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

close

PSPACE-hardness gadgets
Start & Finish
Crossover, usable multiple times
Stand-alone Door: can be opened, closed, and traversed if
and only if it is open

open

traverse

closeSuper Mario Bros.: Door gadget

traverse

close

traverse
close
open

Super Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetSuper Mario Bros.: Door gadgetLemmings (PC, Amiga)Lemmings (PC, Amiga)Lemmings: Door gadget

closeddoor

Lemmings: Door gadget

The Legend of Zelda: Door gadget

The Legend of Zelda: Door gadget
initialize
start

traverse
close

1

open

2
1

2

1

2

initialize

open

traverse

1

1

initialize

2

close

Donkey Kong Country (SNES)

Donkey Kong Country: Door gadget
traverse

close

close
open

traverse

Donkey Kong Country 2 & 3: Door gadgets
traverse

1
traverse
2

3
open

close
open

1
traverse
traverse

close

open

3

close
A

2
close

Why do we care?
We know for a fact that every level of any “real” game is solvable.
So, why do we study level solvability?

Why do we care?
We know for a fact that every level of any “real” game is solvable.
So, why do we study level solvability?
Player’s perspective: “Which way should I go?”?? ?
One of the paths is certainly right, but which one?
Designer’s perspective: “Is my new level solvable at all?”Conclusions
Single-player games:
Games in P: they have a “simple” winning algorithm. When
this algorithm is discovered, they become uninteresting.
−→ Games with short longevity. :(NP-complete games: they keep challenging the player, andthey have “short” solutions whose discovery requires creativity.
−→ Fun games! :)PSPACE-complete games: they still require ingenuity, butsolving them may take exponentially many “moves”.
−→ Challenging games, but may be tedious. :/What’s next?
Two-player games:
Games in NP: they have “simple” winning strategies.
−→ Games with short longevity. :(PSPACE-complete games: they are challenging, and thewinner is determined after polynomially many moves.
−→ Fun games! :)Examples: Reversi, Gomoku, Go (without ko)
EXP-complete games: they still require ingenuity, but games
may last exponentially many “moves”.
−→ Challenging games, but may be tedious. :/Examples: Checkers, Chess, Go (with Japanese ko)

References
G. Viglietta
Gaming is a hard job, but someone has to do it!
Theory of Computing Systems 54, 2014
G. Viglietta
Lemmings is PSPACE-complete
Theoretical Computer Science 586, 2015
G. Aloupis, E. D. Demaine, A. Guo, and G. Viglietta
Nintendo games are (computationally) hard
Theoretical Computer Science 586, 2015
E. D. Demaine, G. Viglietta, and A. Williams
Super Mario Bros. is harder/easier than we thought
FUN 2016

Assignment 3
In this lesson we saw that Super Mario Bros. levels that contain
only Question-Mark Blocks, Super Mushrooms, and Fire Bars are
NP-hard, and levels that contain only Breakable Blocks, Spinies,
and Fire Bars are PSPACE-hard.
=⇒ NP-hard=⇒ PSPACE-hard
Prove that levels that contain only Breakable Blocks and Spinies
are NP-hard.
=⇒ NP-hard