Raph Koster
Games Are Math

Simple game: flipping a coin. Binary feedback! How much math went into that? Flipping the coin itself was a lot of calculus right there. Physics of precession, etc. More metal carved away on one side or another, so we aren’t looking at 50/50 odds, slight weight bias to tails. Coin and hand elasticity, bounces, etc etc etc. That’s a lot of math for a stupid game.

This is a game grammar approach. Coin is a small model. We learn via Observation, Hypothesis, Experiment, Conclusion. Not thinking about the coin’s precession when flipping it. Input > black box > output. Can start analyzing the feedback then. That is a game grammar model. I think I know how the coin will work. Mental model > intent > intent via tool > actual model > state change > feedback. This talk is all about the internal “actual model” work.

Throw the coin at your opponent! You can always boil the opponent down to math. Simple: space invaders, complicated: your neighbor. All games work this way, in a video game we go as fast as the simulation framerate goes. This is always math, sometimes this is too complex for us to actually get across. Like tossing a coin, games are made of smaller games. Assertion: only that actual model of rules are game design. Actual, core systemic design.

Take turns picking numbers from 1-9, can’t pick a number opponent chooses, objective is to get to 15. This game is mathematically equivalent to Tic tac Toe! Game interfaces lie about what the model is. Throw away everything that you see and think of it in terms of mathematical structure!

There are lots of kinds of math. “Complexity class” . 488 geeky definitions of classes. “How long would it take a computer given a certain amount of resources”. At the bottom of the chart, “we know”, and the top “no clue, maybe after the heat death of the universe”. Bottom half of the chart is “easy”. Always solve in a guaranteed X steps. Polynomial time. “P” problems.

NP = Non Polynomial. Does P = NP? Problem is “hard” if it takes X^2 or x^x. Some have easy solutions, but we don’t know how we get there. The brain is a computer too, but it doesn’t work the same way as the computers we have every day. Different measurable sorts of intelligences, computers are really only good at one (but it’s the one we suck at). 100 Teraflops. Calculate a single flop and you’ll be here a half hour. Different kind of processing. Yet what we do is theoretically computable, and computers are nowhere near catching up.

Logical, learning usage. Crystallized intelligence, learned approaches. Very very slow. Fast part of our brains is faster than our brain – hand out of fire via autonomic before the pain registers with the brain. A lot of thinking is things like keeping balance. “Fluid intelligence”, problem solving, learning, and pattern recognition. So good at some math, sucks at others. Games are training you in specific sorts of math problems. Teaching you to “grok” a case of problems.

Coolest problems are the NP side. Verify quickly but can’t find it quickly. Use approximation instead. NP-Complete.

So why do we care? These are familiar mechanics but the way of looking at them may not be, may open new doors for you.

Karp 21. NP-complete problems.

Graph Isomorphism. Planarity. Graph theory branch of math about relationships between objects. Treat that abstractly. Node, edge, weighted graph, directed graph. Graph theory of MMORPG combat. Monster > tank. Damage, whoever has a bigger weight wins. Healer to Tank, no longer cyclic. Arrow small = aggro management, manipulating weights. Nuker adds in. That’s all RPG combat. So party to tackle a monster is NP-complete. But a computer cannot solve that in any reasonable amount of time. Yet we ask players to do this regularly.

Exact Cover. Set of pieces with weird shapes, fit them so that none overlap and you cover everything. Pentominoes. This is literally in Puzzle Pirates carpentry. Tetris, of course. This is also Sudoku. Stop thinking about how it looks. Given X resources, capable of covering Y tasks and Z tasks to cover, no ability to double up, how do you do as best as you can? Team of friends in a social RPG, or working through a game of Strategic War.

Set packing. What if you can overlap? Convention of foreign ambassadors, speaks English and other languages. You want to make an announcement. Don’t want them to talk to each other, but talk to as many as possible. This is Texas Hold ‘em, or deckbuilding in any deckbuilding game.

Vertex Cover. Blokus. Finding open vertices in the graph. Take away the board, focus on the graph.

A raid is a feedback arc set. Transform it into max flow towards one set. Raid planners are trying to find the optimized vertex cover for the boss!

Graph coloring. Old cartograph problem. This is why MS Project can’t fix your Gantt chart! “Chromatic Valence” = makespan. This is every scheduling game there is! Restaurant City, Sims, etc.

Knapsack Problem. Stuff with weight and value, maximize value while constraining weight. Inventory tetris.

Three dimensional matching. 3-satisfiability. A non-visual application. Red green blue stats. Equippable items adjust these stats, minimum items to get best benefit, whats the maximum usable items? The game of Set = gear management.

Steiner Tree aka Traveling Salesman problem. Center node between a triangle. Equivalent to level design w/roads. Make your maps abstract graphs. Players will seek a steiner tree. Solving of Pac-Man patterns.

Maximum cut. Go through as many of the edges as you can without hitting any twice. Minimum cut, into at least two and smallest number of edges hit. Maximum cut = orc farming, minimum cut = direct path with minimum combat.

Partition problem. Playground team selection. Classic solution is a greedy algorithm. Greedy solves 99% of the time, but there are better ways. Easy if ranges of skills are similar m/n ratio, bit depth of the kids. When it’s not you get into power laws and pvp monsters. Better problem for players to have than developers in matchmaking.

Brain hacks. Algorithms to solve problems but the brain has cognitive bugs in the software. Game design on exploiting the bugs!

Reciprocation, do things for people that did us a favor even if we don’t like them. Even disproprortionately, even if the gift was forced. “free gifts” “custom limited edition items”.

Consistency fallacy. Do things we have made a promise to do or go on record in some fashion. Minor statement on the way to a major one makes them more likely to do the major one. Pull users through open worlds or commit to codes of conduct?

Commitment fallacy. Value things we struggled through difficult times to get. More than stuff that comes easy, regardless of true value. Membership ceremonies? Paying user feel like a member of a secret club? This is why hazing exists in every culture.

Social proof. Do things that we see other people validating. Canned laughter, “most users reuse their towels”. Big implications for community management – can you use claques? The more a person looks like you, the more we consider it to be social proof.

The Liking Problem. We like people who like us. Try to please those who like us. Who’s Who. Join now and help your friend level up in Mafia Wars… automated flattery, fear of snubbing a friend.

Positive Association Error. Put pretty people next to something, we think that it is better.

Authority. Taller people with executive hair climb the ranks. We go along with authority (and with sly sincerity). Underthink our avatars, fail to provide the right NPC models.

Scarcity Principle. Overvalue what is scarce. Crave the censored, Click the forbidden NSFW link! Desire what few have regardless of whether it is worth anything objectively. Competition = value it more!

Linear extrapolation. Only see certain types of curves. Really bad at non-linear extrapolation. Terror attack vs car crash. We tend to use linear curves in design, not surprising players.

“Easy” games. P systems are compelling until an adequate algorithm is developed. Put things right on the edge of their ability or past it but they think they can do it, that’s fun. Operating at the margin of ability.

Sorting, pairing, minimax algo, Hungarian algo, topological sort, cluster identification.

Chess and Go are up in PSPACE / EXPTIME. These have accreted, often less than designed. Folk games.