Big news
Judea Pearl has won a richly-deserved Turing Award, for his pioneering work on reasoning under uncertainty, Bayesian inference, and causality. Much like last year’s winner Leslie Valiant, Pearl has been a perfectly-plausible candidate since the 1980s; it was really just a question of when they’d get around to him. For those who don’t know his work, Pearl’s landmark book Causality provides a wonderful introduction to at least one major strand of his thought; I read it this summer and it inverted the way I think about lots of things in statistics. (Pearl’s fame precedes this award, partly for a tragic reason: he’s probably best known to the public as the father of the murdered journalist Daniel Pearl.)
In other big news, playing Super Mario Bros. is now known to be NP-complete, as shown in this landmark paper by Greg Aloupis, Erik Demaine, and Alan Guo. The sheer intuitiveness of the gadget constructions, at least to anyone who grew up playing Nintendo, makes this probably my favorite NP-completeness paper of all time (well, I guess tied with some papers by Cook, Karp, and Levin).
Follow
Comment #1 March 15th, 2012 at 1:36 pm
Thanks for the heads-up on that paper.
Next time I have to teach Theory of Computation to undergrads I’ll use that to motivate them 🙂
Comment #2 March 15th, 2012 at 2:03 pm
Huge thanks for the pointer to the very interesting Aloupis-Demaine-Guo paper!
From the paper: “In order to force the player to take the Super Mushroom in the beginning, we block off the Finish gadget with bricks”.
But in the tool-assisted speed running community (which the authors explicitly acknowledge in the introduction) there are well-known tricks for getting past such barriers without a Super Mushroom. In fact, see here: http://tasvideos.org/GameResources/NES/SuperMarioBros.html#ApplicationJumpIntoAWallJustBelowASolidCeilingAndWalkThroughIt (if your browser does not automatically jump to the correct section, scroll down manually to “Application: Jump into a wall just below a solid ceiling and walk through it”) You will see an animated figure of regular Mario skipping *precisely* the obstacle which the authors attempt to block him with.
This raises all kinds of questions about how game theorists ought to model these types of games. Are such glitches part of the game? Why or why not? One of these days I fancy I might even try to write a paper on the subject, though for now other stuff has to take priority.
Comment #3 March 15th, 2012 at 2:12 pm
I love how specific the abstract is.
“Our results apply to Super Mario Bros. 1, 3, Lost Levels, and Super Mario World … all Legend of Zelda games except Zelda II …”
I also quite enjoy the phrase “generalized Super Mario Bros”.
Comment #4 March 15th, 2012 at 2:19 pm
Just out of curiosity in what way did Causality invert the way you think about statistics ?
And yeah that paper is awesome! 😀
Comment #5 March 15th, 2012 at 3:04 pm
That is awesome!!!
Comment #6 March 15th, 2012 at 3:24 pm
I saw the same problem with the Super Mario Bros. proof, and a similar one for A Link to the Past: someone playing the game normally will get the Pegasus Shoes before the hookshot; there’s a glitch that allows one to hover over gaps (at least in a tool-assisted speedun) by pressing the button to activate the Pegasus Shoes on every frame. I haven’t fully read the Pokémon proof, but I noticed at least two things that bother me: one is that it doesn’t seem to take into account the trainer locations resetting if you save and reload (some Pokémon tool-assisted speedruns use glitches that require saving and reloading). The other is that it seems to rely on the player being able to tell the weak players from strong players without battling them. I suppose this could be discovered ahead of time for a tool-assisted speedrun, either through experimentation or perhaps a memory viewer, but I don’t know that having prior information is really in the spirit of trying to solve an NP-complete problem.
Comment #7 March 15th, 2012 at 4:27 pm
Heh, someone actually proving that, rather than the old joke paper/video…
Comment #8 March 15th, 2012 at 7:14 pm
Some of you may also appreciate the fact that the work was initiated in Barbados. I have been there: it is a great place for workshops, with the potential of “swimming breaks” instead of coffee breaks.
Comment #9 March 15th, 2012 at 7:48 pm
Let us congratulate the winners of Waterman’s award too 😉
http://www.cccblog.org/2012/03/08/two-computer-scientists-receive-2012-alan-waterman-award/
Comment #10 March 15th, 2012 at 7:49 pm
As cool as the Mario thing is, it has a hard time competing against the proof that Minesweeper is NP-complete. To do that, they actually constructed “logic gates” and “wires” out of the possibilities that certain sections could be solved one way or another. One of my favorite results ever. Details here: http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm
Congrats to Doctor Pearl as well…
Comment #11 March 16th, 2012 at 2:09 am
Thanks, Jiav!
Comment #12 March 16th, 2012 at 2:31 am
Izo #4:
Just out of curiosity in what way did Causality invert the way you think about statistics ?
The first thing people learn about statistics is “correlation does not imply causation.” That’s true, of course, but over the years it tended to morph into the following:
What’s “really out there in the world” is an observed pattern of correlations. Causality is then a form of storytelling that we use to represent those correlations more compactly—something that evolved over millions of years because it was useful to us, sort of like the separation of the visual field into discrete objects.
Pearl says no, that has it completely backwards. Underlying the world is some real causal structure that we’re trying to figure out. To take his favorite example, it’s not merely true that rain is correlated with grass getting wet, and that rain starts slightly earlier in time: the rain actually causes the grass to get wet, and not vice versa. One way to formalize that intuition is that, if we intervened directly in the state of the world to make it rain (say, by seeding clouds), that would also make the grass wet; whereas if we intervened to make the grass wet, that wouldn’t make it rain. Correlation might be the thing we can directly observe, but there’s an excellent (and “objective”) reason why we care about causation more: because knowing the causal relationships between random variables lets you predict what will happen to those variables even in novel or hypothetical situations, not just situations like the ones you already saw.
At that level, it all sounds pretty obvious! But Pearl and his collaborators developed this perspective into a whole way of organizing statistical reasoning called “causal Bayes nets”, which has actually been used in applications (and which could be used more) and about which many interesting theorems can be proved.
Beyond that, Causality is filled with counterintuitive observations about this or that classical puzzle of statistics, but I don’t want to spoil the surprise of reading it. 🙂
Comment #13 March 16th, 2012 at 4:35 am
[…] Judea Pearl wins Turing Award, here. Pearl’s book Causality seems interesting, particularly from a price discovery (leading […]
Comment #14 March 16th, 2012 at 4:51 am
“which has actually been used in applications (and which could be used more) and about which many interesting theorems can be proved.”
(1) What are those applications that already exist? (more convincing if software is available)
(2) What are those applications you have in mind that haven’t been implemented yet?
(3) How does Pearl’s causality calculus manifest itself in quantum mechanics? If it’s so fundamental, it must have reared its head in qm a long time ago. Or is our current understanding of qm incomplete because it lacks Pearl’s causality calculus?
Comment #15 March 16th, 2012 at 8:30 am
[…] Demaine, and Alan Guo. Classic Nintendo Games are (NP-)Hard (PDF). Preprint. [3] Scott Aaronson. Big News. Shtetl-Optimized, 2012. [4] Ryan Landay. Comment on [3], 2012. [5] Masterjun. SNES Super Mario […]
Comment #16 March 16th, 2012 at 12:33 pm
rrtucci: I’ll let someone else field your first and second questions, if they feel like it. Your third one is actually extremely interesting. Pearl explicitly discusses quantum mechanics in Causality, as the only known example of a phenomenon that violates certain “obvious” axioms of causal inference. For example, there’s apparently what’s known as the “Common Cause Assumption”: if two random variables x and y are observed to be correlated, then either there must be a causal chain leading from x to y, or a causal chain leading from y to x, or another set of variables Z with causal chains leading to both x and y, such that x and y are conditionally independent given Z. Now, this assumption is badly violated if x and y are Alice and Bob’s measurement outcomes in the CHSH game, since the first two possibilities would correspond to superluminal signalling and the third one to hidden variables (which, again, would require superluminal signalling). Indeed, I understand that Rob Spekkens and some others have been working on reformulating arguments about nonlocality, contextuality, etc. in Pearl’s language.
The way I currently think about it, Pearl’s causality calculus only works for events (i.e., random variables), but the whole notion of an event presupposes decoherence, i.e. that something roughly classical has crystallized out of the amplitude soup. You can use his calculus to pinpoint pretty nicely which axioms and intuitions are violated by QM. But I have no idea what a version of Pearl’s calculus that applied directly to quantum states would look like, or whether it would be useful for anything.
Comment #17 March 17th, 2012 at 9:25 am
Minor note: Could you fix the arXiv link to go to the abstract rather than directly to the PDF?
Actually, I’m a little confused by the crossover gadgets in the Mario example; doesn’t Mario need to be able to get back afterward?
Comment #18 March 17th, 2012 at 10:08 pm
Does the NP-completeness of Super Mario Brothers really a proof that its hard to play- since people don’t play it on that big a board. More generally, proofs that games are NPC- or PSPACE-complete, or NEXP-complete—- do they really mean the game is hard?
Comment #19 March 17th, 2012 at 11:29 pm
Unfortunately the margin is too small to tell 🙂
Comment #20 March 18th, 2012 at 3:00 am
GASARCH: I’d say these results have extremely little to do with the hardness of the game as actually played; instead they tell you how much hardness “could, potentially” be lurking there, were the level designers devious enough. But the nice thing with this sort of result is that you can examine the gadgets and decide for yourself! (I.e., “how similar is this to any situation I remember from Super Mario?”) Also, I confess to being intrigued that Zelda is PSPACE-complete, whereas Mario is “merely” NP-complete. I do remember Zelda as being a more complicated game, and partly because it involved more combinatorial-style puzzles (pushing blocks around, etc).
Comment #21 March 18th, 2012 at 5:29 pm
The video game paper is really nice, thank you Scott for pointing to it. Though I find it misleading to say that Mario is NP-hard. Some game inspired from Mario is. But as you say, those results have little to do with the actual games, how they are played. The hardness of actual games is still an interesting and perhaps open problem (which I guess could be modeled by machine learning concepts, expressing how complicated and variable the required sequences of moves can be, more than how hard they are to find).
The paper may apply more to the puzzle genre of game, while Mario is a skill game. Zelda is a mix, so I guess the paper applies better to it than to Mario.
Comment #22 March 19th, 2012 at 2:36 pm
[…] was Judea Pearl ‘s student from 88 to 92 (a couple of related posts can be found here and […]
Comment #23 March 29th, 2012 at 1:57 pm
Anybody who wants to find out more about applications of Pearl’s work could start by investigating the research of people like Daphne Koller (Stanford) and Eric Horvitz and collaborators at Microsoft Research. (As I recall, Horvitz came to Microsoft from Stanford.)
Comment #24 March 30th, 2012 at 5:25 pm
See this July 2010 post on Steve Hsu’s blog, pointing to a 2001 paper by Pearl (at cs.ucla.edu) presenting his arguments and the resulting formal framework. Also see the discussion in the comments.
Comment #25 March 30th, 2012 at 5:36 pm
PS: Google Video has a June 2007 commencement address by Pearl at the University of Toronto, which touches only indirectly on his work.
Comment #26 April 2nd, 2012 at 2:00 am
Looks like we need quantum computers to figure out political campaigns.
http://www.nytimes.com/2012/04/01/opinion/sunday/a-quantum-theory-of-mitt-romney.html
Comment #27 April 2nd, 2012 at 1:34 pm
Today I want to insult Scott’s Chinese readers
China’s Muppet Communique