Adam Norwood

Tag: mathematics

  • Classic Nintendo Games are (NP-)Hard
    Visit the source: arxiv.org

    Science!

    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.

    Translation: video games might provide interesting fodder for complexity theory, and possibly provide a model for novel ways of looking at difficult decision problems. In any case, I just like seeing Metroid mentioned on the arXiv.

    (Via New Scientist)

    , , , , ,

  • Who Killed Videogames Social Games Psychology

    Game design is about crafting a micro-economy. Even in an action game, every action the player or an enemy can perform is a stock or a bond or a unit of currency that can be traded for something else. As the screen scrolls from left to right, Super Mario Bros.’s market fluctuates. One fireball can buy one dead koopa. The points at the top of the screen can’t buy anything. Given enough time and a spreadsheet, I could tell you how many dead Goombas a Bowser fireball is worth.

    From who killed videogames (a ghost story), an insightful essay on the addiction psychology of social games and the strange motivating forces that lure people into plunking down money on intangibles, the nefarious angle of so-called gamification.

    “The players will come for the cute characters, and stay for the cruel mathematics.”

    I think I’ll go read a book now…

    (Via O’Reilly Radar)

    , , , , , , ,

  • Logically boring

    From Lewis Carroll’s Symbolic Logic, which aimed to make logic understandable via quirky syllogisms and illustrated tables:

    1. No interesting poems are unpopular among people of real taste;
    2. No modern poetry is free from affectation;
    3. All your poems are on the subject of soap-bubbles;
    4. No affected poetry is popular among people of real taste;
    5. No ancient poem is on the subject of soap-bubbles.

    Conclusion: all your poems are uninteresting.

    , , , ,

  • Nomographs

    From a post titled The Art of Nomography on Dead Reckonings (a blog dedicated to forgotten-but-beautiful mathematical systems! I’d better subscribe to this one…) :

    Nomography, truly a forgotten art, is the graphical representation of mathematical relationships or laws (the Greek word for law is nomos). These graphs are variously called nomograms (the term used here), nomographs, alignment charts, and abacs. This area of practical and theoretical mathematics was invented in 1880 by Philbert Maurice d’Ocagne (1862-1938) and used extensively for many years to provide engineers with fast graphical calculations of complicated formulas to a practical precision.

    Along with the mathematics involved, a great deal of ingenuity went into the design of these nomograms to increase their utility as well as their precision. Many books were written on nomography and then driven out of print with the spread of computers and calculators, and it can be difficult to find these books today even in libraries. Every once in a while a nomogram appears in a modern setting, and it seems odd and strangely old-fashioned—the multi-faceted Smith Chart for transmission line calculations is still sometimes observed in the wild. The theory of nomograms “draws on every aspect of analytic, descriptive, and projective geometries, the several fields of algebra, and other mathematical fields” [Douglass].

    More about nomograms and abacs on Wikipedia.

    (Via O’Reilly Radar)

    , , , , ,

  • Simulated Heat Mapping for Computer Vision

    A new approach to computer vision object recognition: simulated heat-mapping:

    The heat-mapping method works by first breaking an object into a mesh of triangles, the simplest shape that can characterize surfaces, and then calculating the flow of heat over the meshed object. The method does not involve actually tracking heat; it simulates the flow of heat using well-established mathematical principles, Ramani said. …

    The method accurately simulates how heat flows on the object while revealing its structure and distinguishing unique points needed for segmentation by computing the “heat mean signature.” Knowing the heat mean signature allows a computer to determine the center of each segment, assign a “weight” to specific segments and then define the overall shape of the object. …

    “A histogram is a two-dimensional mapping of a three-dimensional shape,” Ramani said. “So, no matter how a dog bends or twists, it gives you the same signature.”

    In other words, recognizing discrete parts (like fingers or facial features) of an object in front of the camera should be much more accurate with this approach than with older techniques like simple edge detection. Uses for real-time recognition are apparent (more accurate Dance Central!), but it seems like this would also be a boon for character animation rigging?

    (Via ACM TechNews)

    , , ,

  • Phillip Torrone Rides the Square Wheeled Tricycle

    (video no longer available)

    Phillip Torrone rides the square-wheeled tricycle from the Math Midway, a traveling exhibition of mathematics. Figuring out what kind of catenary curves would be needed for differently shaped wheels is a branch of mathematics that I’m happy  exists (as far as I know the problem dates back on some level to the 1960s, but for a good recent illustration of the math involved, check out this PDF from a St. Norbert College mathematical modeling class).

    (Via Make)

    , , , , , ,

  • Heres a Toast to Alan Turing Born in Harsher

    here’s a toast to Alan Turing
    born in harsher, darker times
    who thought outside the container
    and loved outside the lines
    and so the code-breaker was broken
    and we’re sorry
    yes now the s-word has been spoken
    the official conscience woken
    – very carefully scripted but at least it’s not encrypted –
    and the story does suggest
    a part 2 to the Turing Test:
    1. can machines behave like humans?
    2. can we?

    Alan Turing by poet Matt Harvey, on the occasion of British prime minister Gordon Brown’s official posthumous apology to the mathematician and computer theorist. Originally read/published on the BBC Radio 4 broadcast Saturday Live, 12/9/2009.

    (Via Language Log, from a mostly unrelated post on the language of homophobia in Jamaican culture, which is itself worth reading – depressing, but worthwhile)

    , , , , ,

  • A Brief Explanation of a Three Rotor Enigma Machine

    A brief explanation of a three-rotor Enigma machine, the cryptographic device used by Nazi Germany during WWII to encode their communications. While the encryption technology had some flaws, it was largely broken by the Allies due to human mistakes made by the operators (not disposing of their key tables, writing down portions of the codes, captured hardware, etc).

    , , , ,