Comments on: Big news

By: rrtucci

rrtucci — Mon, 02 Apr 2012 18:34:31 +0000

Today I want to insult Scott's Chinese readers China's Muppet Communique

By: asdf

asdf — Mon, 02 Apr 2012 07:00:11 +0000

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

By: Chris W.

Chris W. — Fri, 30 Mar 2012 22:36:26 +0000

PS: Google Video has a June 2007 commencement address by Pearl at the University of Toronto, which touches only indirectly on his work.

By: Chris W.

Chris W. — Fri, 30 Mar 2012 22:25:17 +0000

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.

By: Chris W.

Chris W. — Thu, 29 Mar 2012 18:57:20 +0000

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.)

By: Embracing uncertainty, causality, and curiosity: Judea Pearl wins the 2011 A. M. Turing Award « Windows On Theory

Mon, 19 Mar 2012 19:36:41 +0000

[...] was Judea Pearl ‘s student from 88 to 92 (a couple of related posts can be found here and [...]

By: plm

plm — Sun, 18 Mar 2012 22:29:42 +0000

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.

By: Scott

Scott — Sun, 18 Mar 2012 08:00:48 +0000

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).

By: Jiav

Jiav — Sun, 18 Mar 2012 04:29:07 +0000

Unfortunately the margin is too small to tell

By: GASARCH

GASARCH — Sun, 18 Mar 2012 03:08:41 +0000

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?