Super Mario AI Competition(julian.togelius.com)
julian.togelius.com
Super Mario AI Competition
http://julian.togelius.com/mariocompetition2009/
6 comments
AI contests like this and the DARPA Grand Challenge Race encourage solutions in a single domain. AFAIK in the DARPA Challenge there was overfitting and I doubt the generalization capability of the systems involved. We need more contests in the spirit of "General Game Playing" contests where the problem domain is unknown to the programmers. http://games.stanford.edu/. You only get a formal description before the game and a small amount of "thinking" time which the system has to use understand the game and formulate a strategy.
There is a vast difference between AI for games (which are purely theoretical exercises) and AI for working in the real world. The fundamental characteristic of the real world is that there is uncertainty and ambiguity in every measurement and even your actions (did my car actually move when I pressed the accelerator?).
The kinds of systems you build to tackle these latter types of problems are very different from the kinds you need for the first type. Both have their place, of course, although IMHO, the latter type is more interesting, as it's a much messier area to work in.
The kinds of systems you build to tackle these latter types of problems are very different from the kinds you need for the first type. Both have their place, of course, although IMHO, the latter type is more interesting, as it's a much messier area to work in.
Well, messiness is just one part of the problem. I usually see AI as a layered system that solves a general problem. The layers are broadly: lower level sensory systems(vision, speech recognition) and higher level symbolic reasoning systems. Recently, there has a been a lot of success in the lower layers due to Machine Learning and probabilistic systems. The messiness comes in the lower layers. When dealing with the higher layers you face much harder problems. Hard in the sense of Turing uncomputable. The only formal solution proposed for general AI is uncomputable http://www.hutter1.net/ai/uaibook.htm.
Also there is nothing which restricts real world problem solvers to a single domain. Most messy problems have a formal solution. The engineering part is what remains (but the engineering part is nevertheless hard!). Some non "messy" problems have no computable solution e.g. deciding whether an arbitrary argument in first order logic is true. They challenge the bounds on human thinking.
Also "General Game Playing" is not only about games. (Like Game Theory is not only about games).
Also there is nothing which restricts real world problem solvers to a single domain. Most messy problems have a formal solution. The engineering part is what remains (but the engineering part is nevertheless hard!). Some non "messy" problems have no computable solution e.g. deciding whether an arbitrary argument in first order logic is true. They challenge the bounds on human thinking.
Also "General Game Playing" is not only about games. (Like Game Theory is not only about games).
I don't agree that the higher level symbolic reasoning is necessarily harder, nor that the lower level is simply engineering. The problems at the low-level are still very tough, and require scientific (and not just hacky- or engineering-) approaches.
As for the "single domain" issue, this was a big red herring in old-style AI (before the so-called AI winter) -- basically, it turns out that the different branches of what used to be called AI (e.g., vision, machine learning, NLP, speech, etc.) have to use quite different techniques.
"General" AI systems such as logic, game players (and yes, I know it's not just about games), etc., can be used in various domains, but in general they're not very applicable to most real-world problems in the different domains.
For example, I work in computer vision, and while we certainly use a lot of probabilistic analysis that can be broadly applicable to other domains, a lot of the progress in recent years has been using techniques that aren't really transferable (e.g., SIFT or SLAM).
As for the "single domain" issue, this was a big red herring in old-style AI (before the so-called AI winter) -- basically, it turns out that the different branches of what used to be called AI (e.g., vision, machine learning, NLP, speech, etc.) have to use quite different techniques.
"General" AI systems such as logic, game players (and yes, I know it's not just about games), etc., can be used in various domains, but in general they're not very applicable to most real-world problems in the different domains.
For example, I work in computer vision, and while we certainly use a lot of probabilistic analysis that can be broadly applicable to other domains, a lot of the progress in recent years has been using techniques that aren't really transferable (e.g., SIFT or SLAM).
General AI is not applicable in real life yet. Probabilistic reasoning can be subsumed into a logic system. For example, a human(David Lowe) has originated SIFT. A reasoning system should in principle be able to derive SIFT. We are not there yet but that should be the goal.
The problem with singe domain systems is none are even capable of robust inductive transfer (http://en.wikipedia.org/wiki/Inductive_transfer). Some reasoning problems are mathematically hard problems (http://en.wikipedia.org/wiki/List_of_undecidable_problems). There is no algorithm which even in principle can solve them. Among other things, you need infinite processing speed to do so. No amount of science can help here as it is in the logical domain.
The problem with singe domain systems is none are even capable of robust inductive transfer (http://en.wikipedia.org/wiki/Inductive_transfer). Some reasoning problems are mathematically hard problems (http://en.wikipedia.org/wiki/List_of_undecidable_problems). There is no algorithm which even in principle can solve them. Among other things, you need infinite processing speed to do so. No amount of science can help here as it is in the logical domain.
Your statement about inductive transfer is false. There are many vision systems, for example, that use transfer learning (as it is known in our community) to use knowledge gained from one task in another. Moreover, many of these approaches are specific to vision -- they can't easily be applied in other domains.
The rest of your comments about reasoning systems are either part of theoretical computer science (e.g., most of that list of undecidable problems), or in the realm of philosophy/metaphysics/80s-style AI. The former is an interesting area, but much closer to math than most other areas of CS. I call the latter philosophy/metaphysics because these are often questions that are interesting from a purely academic viewpoint, but are utterly useless for trying to make progress on real tasks. This was the big problem with 80s style AI: people hoped that they could build general systems which could "reason" about how to derive algorithms to do particular tasks. Knowledge bases were supposed to be steps in this direction.
What the community learned is that this is not a valid approach, in part because it doesn't take into account the enormous amount of data people have access to from birth to adulthood (not to mention the fact that we can interact with our environment and see the results of our actions). There doesn't seem to be a good way to provide a computer system this kind of information.
There are also strong biological arguments against this idea. For example, a large fraction of human brain cells are exclusively devoted to processing visual information. This is in addition to the significant amount of visual processing done by our eyes and the optic nerve. There are similar systems in the brain devoted to speech processing and language, etc.
All of this suggests that a general reasoning system cannot hope to solve the challenging problems in these different domains.
The rest of your comments about reasoning systems are either part of theoretical computer science (e.g., most of that list of undecidable problems), or in the realm of philosophy/metaphysics/80s-style AI. The former is an interesting area, but much closer to math than most other areas of CS. I call the latter philosophy/metaphysics because these are often questions that are interesting from a purely academic viewpoint, but are utterly useless for trying to make progress on real tasks. This was the big problem with 80s style AI: people hoped that they could build general systems which could "reason" about how to derive algorithms to do particular tasks. Knowledge bases were supposed to be steps in this direction.
What the community learned is that this is not a valid approach, in part because it doesn't take into account the enormous amount of data people have access to from birth to adulthood (not to mention the fact that we can interact with our environment and see the results of our actions). There doesn't seem to be a good way to provide a computer system this kind of information.
There are also strong biological arguments against this idea. For example, a large fraction of human brain cells are exclusively devoted to processing visual information. This is in addition to the significant amount of visual processing done by our eyes and the optic nerve. There are similar systems in the brain devoted to speech processing and language, etc.
All of this suggests that a general reasoning system cannot hope to solve the challenging problems in these different domains.
Almost all AI these days (even academic research) is a "solution for a single domain," unfortuantely.
Oy, such a short timeline for a task like this! Submissions are due by August 14th or September 3.
Programming video game AI is fun. I took a class at UPenn where we had to build a pacman playing agent with reenforcement learning. The gameplay was't standard pacman, but with just a few, general features and correct training it was easy to get pretty decent results. And it's not that hard to implement. Not sure how it'd work on Mario though. Anyone have any thoughts?
On a related note, one of the more interesting lightning talks at YAPC this year was about the Tactical Amulet Extraction Bot, a framework for programmatically playing nethack. Here's a blog about it: http://taeb-blog.sartak.org/
And the code: http://search.cpan.org/~sartak/TAEB-0.03/lib/TAEB.pm
I think it's been discussed here at HN once or twice, as well.
And the code: http://search.cpan.org/~sartak/TAEB-0.03/lib/TAEB.pm
I think it's been discussed here at HN once or twice, as well.
I've long wondered why the DARPA challenge for automated cars is necessary when the code could be tested using video games for orders of magnitude less money.
In theory there is no difference between theory and practice. In practice, however...
crude simulations don't invalidate theories. i hate anti-scientific quips like that.
In theory, there is no difference between theory and practice, but in practice there is.
I'm quite sure that if there is one set of people that know this by heart then it is the military. Real world experience will bring out the trouble much faster than any amount of simulation.
Use simulations to help you design, validate your design in the real world. Then update your simulation to reflect the lessons you learned during your real world tests and iterate.
Have a look at armadillo aerospace, John Carmack is as versed as anybody in that field with simulations and STILL they find out almost every trial they do that the real world is not as clean as the simulated one.
I'm quite sure that if there is one set of people that know this by heart then it is the military. Real world experience will bring out the trouble much faster than any amount of simulation.
Use simulations to help you design, validate your design in the real world. Then update your simulation to reflect the lessons you learned during your real world tests and iterate.
Have a look at armadillo aerospace, John Carmack is as versed as anybody in that field with simulations and STILL they find out almost every trial they do that the real world is not as clean as the simulated one.
My preferred phrasing is "The only difference between practice and theory is that, in theory, there is no difference between practice and theory."
Indeed. Just take a look at Murphy's laws of combat: http://www.murphys-laws.com/murphy/murphy-war.html
Those are great, thanks :)
I don't consider that quip anti-scientific at all. I take it as a reminder that you must always test your theories against reality, because the ways that reality and theory differ might be greater than you realized.
To address your original question, the realities of controlling an actual car are probably the hard problems. Dealing with things such as the inertia of the car and tires slipping on the road are probably both required to solve the problem, and difficult to simulate accurately. Simulations only simulate what we know about. It's often the things we didn't anticipate that make the difference between success and failure.
To address your original question, the realities of controlling an actual car are probably the hard problems. Dealing with things such as the inertia of the car and tires slipping on the road are probably both required to solve the problem, and difficult to simulate accurately. Simulations only simulate what we know about. It's often the things we didn't anticipate that make the difference between success and failure.
let me put it another way then.
can the darpa challengers code EVEN handle a simulation? if not then why waste money going ahead with the full project?
can the darpa challengers code EVEN handle a simulation? if not then why waste money going ahead with the full project?
I'm sure it never occurred to anyone on these teams to try out their code in a simulated environment. I'm 100% positive their development model was to crash car after car after car until they got it working. I can only imagine how expensive some of those bug hunts got.
Come on, seriously?
Come on, seriously?
ya, srsly. From what I've seen they are hacking together the hardware and then constantly updating the code to get just barely working solutions, oftentimes in the middle of the testing. If some teams are running a fairly complex car physics simulator with simulated input from each of the types of sensors they are using this would be the first I've heard of it.
30 seconds on Google:
http://www.torctech.com/company/news/jaus-standard-emerges-d...
http://www.torctech.com/company/news/jaus-standard-emerges-d...
thanks calambrac. obviously I didn't look hard enough.
that presumes an unreasonable amount of homogeneity in both the programming languages of the entrants and the sensor platforms of their vehicles. The entrants may very well do that inhouse for testing purposes, but since Darpa is merely responsible running the competition and determining if the prize award is merited, why on earth would they do something that would unduly constrain the entrants?
They've successfully navigated in the real world, so I'd say yes.
Crude simulations may or may not invalidate theories, but they're notoriously bad at weeding out ultimately inviable lines of investigation. The raw, real world is messy and unpredictable in a way a simulation can never be, and until something from the DARPA Challenge or its ilk can handle meatspace, we got no business trusting meat with it.
Not to say simulations are bad things; they're just of limited utility. Beyond that point, it does get expensive. I think that's part of the reason for the Challenge in the first place.
Not to say simulations are bad things; they're just of limited utility. Beyond that point, it does get expensive. I think that's part of the reason for the Challenge in the first place.
It's not anti-scientific, it's an old engineering adage. It's the unknown unknowns that will get you.
The issue is that
- success on a simulator does not mean being able to "scale up" to real life
- success IRL would does not imply success on some simulator
The link is particularly weak for crude simulations of multi-agent, dynamical, stochastic, partially observable, real-time worlds.
- success on a simulator does not mean being able to "scale up" to real life
- success IRL would does not imply success on some simulator
The link is particularly weak for crude simulations of multi-agent, dynamical, stochastic, partially observable, real-time worlds.
Given perfect information, like from a video game (with access to the object model, etc), the DARPA challenges aren't really that difficult. You just have to plan a path and then stay on it.
Its the noise of the real world that is infinitely challenging. You have to incorporate probabilities into your decision making, which is much more difficult. Jumping a mario around is much more AI intensive because the amount of solutions is much higher. A car is fixed to roads and has a map. Mario might know where everything is, but knowing what to do is much more difficult.
Its the noise of the real world that is infinitely challenging. You have to incorporate probabilities into your decision making, which is much more difficult. Jumping a mario around is much more AI intensive because the amount of solutions is much higher. A car is fixed to roads and has a map. Mario might know where everything is, but knowing what to do is much more difficult.
I have friend who works at NASA in sim and test. Let me assure you simulations don't have to cost an order of magnitude less when the gov is involved.
All joking aside you are talking about custom designed systems. How would you design a sim that works with whatever wonky sensor setup a team can come up with? Two isn't pre-challenge VandV up to the individual teams? They should have simed it long before it got to the competition if they were going to. The competition is to prove that it works in real life\bragging rights. It isn't nearly as cool to say my simulated robot is faster than your simulated robot.
All joking aside you are talking about custom designed systems. How would you design a sim that works with whatever wonky sensor setup a team can come up with? Two isn't pre-challenge VandV up to the individual teams? They should have simed it long before it got to the competition if they were going to. The competition is to prove that it works in real life\bragging rights. It isn't nearly as cool to say my simulated robot is faster than your simulated robot.
Building the vehicles with the associated sensor and control systems were just as important as the AIs controlling I suppose.