Notes about mathematics

March 22, 2012 permalink

Classic Nintendo Games are (NP-)Hard →

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)

October 17, 2011 permalink

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)

August 14, 2011 permalink

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.

August 13, 2011 permalink

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)

July 15, 2011 permalink

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)

October 11, 2009 permalink

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)

September 19, 2009 permalink

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?