Awesome paper on games math

 Posted by (Visited 18704 times)  Game talk  Tagged with: , ,
Jan 272012
 

Giovanni Viglietta of the University of Pisa has posted up a paper called “Gaming is a hard job, but someone has to do it!”. 

In it, he not only analyzes a variety games to determine their complexity class, but he also arrives at a few metatheorems that are generically applicable for all game design. In other words, “include these features and your game gains fun.”

Remember, according to the Theory of Fun, pattern mastery and learning is why the brain plays games. And if you recall my presentation on Games Are Math, I made the case that entire classes of “tasty” problems can be described in mathematical terms (specifically, complexity class), because they are problems that always feel like they are on the margin of our ability.

So if you make use of these specific sorts of math problems — which are actually represented in the game as not looking like math at all, mind you — you are effectively inserting exactly the sort of problem that the brain finds most interesting.

These are not the only sort of problem the brain likes, of course — there ae psychological challenges, social challenges, physical challenges, emotional challenges, and so on. But an enormous amount of what we tend to call “gameplay” falls under the mathematical realm.

Among the metatheorems that Viglietti identifies:

Metatheorem 1. Any game exhibiting both location traversal and single-use paths is NP-hard.

Metatheorem 2. If a game features doors and pressure plates, and the avatar has to reach an exit location in order to win, then:
a) Even if no door can be closed by a pressure plate, and if the game is non-planar, then it is P-hard.
b) Even if no door is controlled by two pressure plates, the game is NP-hard.
c) If each door may be controlled by two pressure plates, then the game is PSPACE-hard.

Metatheorem 3. If a game features doors and k-switches, and the avatar has to reach an exit location in order to win, then:
a) If k > 1 and the game is non-planar, then it is P-hard.
b) If k > 2, then the game is NP-hard.
c) If k > 3, then the game is PSPACE-hard.

Despite the jargon, these are immediately applicable to your games right now, and phrased in game terms are fairly simple features.

The paper goes on to provide proofs and examples for games ranging from Boulder Dash to Doom.

  10 Responses to “Awesome paper on games math”

  1. Some may be thinking the doors and pressure plates sound prosaic, but it basically applies to any sequential causal dependencies. Good find!

  2. Yeah, I had one tweet response say “so what?”… I guess the applicability is not clear. I think it’s great.

  3. At some point an entire class of puzzles becomes solved for a given player (quite possibly in a previous game) and stops being fun. I can’t remember the last time I came to a pressure plate puzzle and actually enjoyed it.

    Generally, I think adding a ubiquitous puzzle class actually detracts from the fun of your game rather than adding to it (cf. Tower of Hanoi puzzles in Bioware games for an example).

  4. Particular puzzle classes should be viewed in a manner far more abstract that that. As a previous comment pointed out, these can be represented in radically different forms and still fit the same mathematical structure.

  5. I don’t know the terms, and I’m into MMORPGs and not any other games much. So I think in terms of “world”. All I can say is that I’ve felt all along that MMORPGs absolutely need the worldly interaction. I don’t know how much this relates to “fun” in the sense of simply opening doors and sitting in chairs. But I think it should be obvious that making things work in our games is fun. I mean, remote controlled toys are more fun than regular toys.

    Of course, not all gamers are alike. Some (what some of us call Themeparkers) seem to really get into the mathematical aspects first hand, through DPS and all that, and knowing what’s the best math. Players like me, on the other hand, can see the math in the play (testing damage with various damage types) but are far less concerned with knowing the guts of the math. And far more concerned with driving our toys.

  6. When you’re roaring along in a Planetside tank, targeting an enemy tank on a different heading, and trying to hit that tank with a projectile that follows a arc, you’re solving multiple math problems in geometry and physics.

    But your experience is not one of sitting down with a calculator and graph paper and working out the precise moment and direction you should fire. Your brain is much better than that. It can calculate the relative angles and velocities and trigger your reflexes without you being aware of doing any math at all.

    In the examples Raph is talking about, you can substitute dialogue tree choices and object collection for pressure plates and k-switches and it’s the same dynamic. There’s an optimum level of complexity that engages us without being beyond our ability.

    Math isn’t reality; it’s a tool for modeling and measuring reality. But it’s a very powerful tool. We as players might never encounter it unclothed in game trappings… unless we peer behind the curtain and find what those wily designers are up to.

    (Strange sidenote — I’ve found a site that has me listed as a game designer, on the strength of a submission I made to Autoduel Quarterly many decades ago. Yay! I’m in the clubhouse!)

  7. […] Raph Koster on the underlying mathematical patterns of Fun […]

  8. I saw the analogousness immediately, but then I wondered if that was intentional. Like… does it have to be location traversal, or could it be conversational paths? I wasn’t sure until your bold-italic stuff afterwards. 😛

  9. Both the amount and the type of difficulty (if any) desired to produce “fun” by different human brains varies immensely. People who aren’t very good at certain types of challenges will avoid entirely games that contain them, or sometimes be very miserable playing them. Some people prefer games that are mostly or entirely luck, some prefer skill and the ones that do prefer different amounts and/or types of skill.

    I’m an odd duck myself, games that present extremely large lookahead trees without hidden information, randomness, or opponent actions truncating them are extremely stressful to me. Because I know I *can* perform immensely better if I sit down for many long minutes before each and every move, traversing the lookahead tree in my mind. But I don’t want to because that’s a huge amount of “work”, not “play”. But if I stop way short of my abilities, I feel like I’m “playing the game badly”. Triple Town, much though I love the design and Dan’s work in general, is very stressful to me for that reason, not enough obscuring randomness to prevent a super-deep tree. There was one solitaire game I loved because the tree wasn’t quite deep enough, but I would play it by getting an opening position, stare, stare, stare, stare, think, think, think, think, then after a long period of time make a few dozen moves. Bam. Other people played it very differently – chess likewise, can be played on a different level than the way strong players do. Which is lucky for chess, or else hardly anyone would play.

    I will note that in the vast majority of cases, ANY significant amount of difficulty isn’t what game players desire, and the ones who do want some are very much in the minority.

Sorry, the comment form is closed at this time.