6 ms·

Super Mario AI Competition

101 points by fogus 17y ago

nazgulnarsil 17y ago
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.
- stonemetal 17y ago
  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.
- CGamesPlay 17y ago
  In theory there is no difference between theory and practice. In practice, however...
  - nazgulnarsil 17y ago
    crude simulations don't invalidate theories. i hate anti-scientific quips like that.
    - agravier 17y ago
      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.
    - scott_s 17y ago
      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.
      - nazgulnarsil 17y ago
        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?
        carterschonwald 17y ago
        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?
        calambrac 17y ago
        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?
        nazgulnarsil 17y ago
        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.
    - rosser 17y ago
      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.
    - jacquesm 17y ago
      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.
      - scott_s 17y ago
        My preferred phrasing is "The only difference between practice and theory is that, in theory, there is no difference between practice and theory."
      - jwhitlark 17y ago
        Indeed. Just take a look at Murphy's laws of combat: http://www.murphys-laws.com/murphy/murphy-war.html http://www.murphys-laws.com/murphy/murphy-war.html
        marvin 17y ago
        Those are great, thanks :)
    - JabavuAdams 17y ago
      It's not anti-scientific, it's an old engineering adage. It's the unknown unknowns that will get you.
- dmm 17y ago
  Building the vehicles with the associated sensor and control systems were just as important as the AIs controlling I suppose.
- maximilian 17y ago
  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.
rawr 17y ago
I like how a hefty fraction of the algorithms use neural networks so that they get better as they watch humans play. The reason for this, of course, is that the developers just want a reason to play Mario :-)
- rw 17y ago
  Fine, yes; but you don't have to use neural networks to get that behavior.
naveensundar 17y ago
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/ 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.
- apu 17y ago
  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.
  - naveensundar 17y ago
    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 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).
dkarl 17y ago
Oy, such a short timeline for a task like this! Submissions are due by August 14th or September 3.
SwellJoe 17y ago
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/ http://taeb-blog.sartak.org/ And the code: http://search.cpan.org/~sartak/TAEB-0.03/lib/TAEB.pm 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.
apgwoz 17y ago
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?

101 points by fogus 17y ago

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.

stonemetal 17y ago
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.
CGamesPlay 17y ago
In theory there is no difference between theory and practice. In practice, however...
- nazgulnarsil 17y ago
  crude simulations don't invalidate theories. i hate anti-scientific quips like that.
  - agravier 17y ago
    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.
  - scott_s 17y ago
    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.
    - nazgulnarsil 17y ago
      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?
      - carterschonwald 17y ago
        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?
      - calambrac 17y ago
        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?
        nazgulnarsil 17y ago
        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.
  - rosser 17y ago
    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.
  - jacquesm 17y ago
    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.
    - scott_s 17y ago
      My preferred phrasing is "The only difference between practice and theory is that, in theory, there is no difference between practice and theory."
    - jwhitlark 17y ago
      Indeed. Just take a look at Murphy's laws of combat: http://www.murphys-laws.com/murphy/murphy-war.html http://www.murphys-laws.com/murphy/murphy-war.html
      - marvin 17y ago
        Those are great, thanks :)
  - JabavuAdams 17y ago
    It's not anti-scientific, it's an old engineering adage. It's the unknown unknowns that will get you.
dmm 17y ago
Building the vehicles with the associated sensor and control systems were just as important as the AIs controlling I suppose.
maximilian 17y ago
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.

rawr 17y ago

I like how a hefty fraction of the algorithms use neural networks so that they get better as they watch humans play. The reason for this, of course, is that the developers just want a reason to play Mario :-)

rw 17y ago
Fine, yes; but you don't have to use neural networks to get that behavior.

naveensundar 17y ago

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

apu 17y ago
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.
- naveensundar 17y ago
  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 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).

dkarl 17y ago

Oy, such a short timeline for a task like this! Submissions are due by August 14th or September 3.

SwellJoe 17y ago

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/ http://taeb-blog.sartak.org/ And the code: http://search.cpan.org/~sartak/TAEB-0.03/lib/TAEB.pm 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.

apgwoz 17y ago

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?