Uber has Cracked Two Classic '80s Video Games by Giving an AI Algorithm a New Type of Memory (technologyreview.com) 100
An algorithm that remembers previous explorations in Montezuma's Revenge and Pitfall! could make computers and robots better at learning how to succeed in the real world. From a report: A new kind of machine-learning algorithm just mastered a couple of throwback video games that have proved to be a big headache for AI. Those following along will know that AI algorithms have bested the world's top human players at the ancient, elegant strategy game Go, one of the most difficult games imaginable. But two pixelated classics from the era of 8-bit computer games -- Montezuma's Revenge and Pitfall! -- have stymied AI researchers. There's a reason for this seeming contradiction. Although deceptively simple, both Montezuma's Revenge and Pitfall! have been immune to mastery via reinforcement learning, a technique that's otherwise adept at learning to conquer video games.
DeepMind, a subsidiary of Alphabet focused on artificial intelligence, famously used it to develop algorithms capable of learning how to play several classic video games at an expert level. Reinforcement-learning algorithms mesh well with most games, because they tweak their behavior in response to positive feedback -- the score going up. The success of the approach has generated hope that AI algorithms could teach themselves to do all sorts of useful things that are currently impossible for machines. The problem with both Montezuma's Revenge and Pitfall! is that there are few reliable reward signals. Both titles involve typical scenarios: protagonists explore blockish worlds filled with deadly creatures and traps. But in each case, lots of behaviors that are necessary to advance within the game do not help increase the score until much later. Ordinary reinforcement-learning algorithms usually fail to get out of the first room in Montezuma's Revenge, and in Pitfall! they score exactly zero.
DeepMind, a subsidiary of Alphabet focused on artificial intelligence, famously used it to develop algorithms capable of learning how to play several classic video games at an expert level. Reinforcement-learning algorithms mesh well with most games, because they tweak their behavior in response to positive feedback -- the score going up. The success of the approach has generated hope that AI algorithms could teach themselves to do all sorts of useful things that are currently impossible for machines. The problem with both Montezuma's Revenge and Pitfall! is that there are few reliable reward signals. Both titles involve typical scenarios: protagonists explore blockish worlds filled with deadly creatures and traps. But in each case, lots of behaviors that are necessary to advance within the game do not help increase the score until much later. Ordinary reinforcement-learning algorithms usually fail to get out of the first room in Montezuma's Revenge, and in Pitfall! they score exactly zero.
short term vs long term gain (Score:5, Insightful)
So researchers have discovered that short term gains can come at the expense of long term success? *gasp* Say it isn't so!
Actually, that's been a known problem for a long time.You end up at a local maximum on the "score" function and now you have no possible way to improve so re-enforcement learning just keeps you there even though you might do substantially better if you actually took a decrease in the "score" and ended up on the path to some other maximum on the function.
(Oh, and "Fr1st ps0t!", especially if it isn't.)
Re:short term vs long term gain (Score:5, Interesting)
This is more important than youmake it out to be. The key to these games is that you have to make a map to succeed. That's not the kind of learning you get from "machine learning", as obvious as it might be to a human player.
One of the many ways that AI is nothing like intelligence is the absence of any representational model of the real world. It's no accident that the neurological seat of human intelligence is an addition to our massive vision processing wetware - understanding the world in terms of objects precedes self awareness in the only example we can study. "AI" doesn't work that way, at least for the most part.
I find it impressive that someone has managed to connect the idea of making a map with the internals of machine learning (which are completely arbitrary matrices that have no obvious connection to the result).
Re:short term vs long term gain (Score:5, Interesting)
One of the many ways that AI is nothing like intelligence is the absence of any representational model of the real world.
There are many kinds of AI. Neural nets don't construct a representational model of the world from visual input but other AI techniques do. The Soar [umich.edu] framework used so successfully for the machine-controlled antagonists in Descent (among many other uses) supports chunking, reinforcement learning, episodic learning, and semantic learning. It is based on the unified theory of cognition. It has both a temporary and permanent representational memory. It's fundamentally rule-based, rather than a neural net.
There was at one time a neural net version of Soar called Neuro-Soar but it's not part of the mainstream Soar library.
Re: (Score:2)
One of the many ways that AI is nothing like intelligence is the absence of any representational model of the real world.
I agree that could be a problem if the number of possible interactions is so large that you need a semantic understanding to whittle it down to a reasonable number. But if it can backtrack random luck to identify the game mechanics that triggered it that's a huge step up, like for example to open the treasure chest it must first find the key or to cross the drawbridge it must first lower it - even though that gives no score by itself. It's hard for an AI to pick out the "meaningful" actions from all the res
Re: (Score:2)
understanding the world in terms of objects precedes self awareness in the only example we can study
So you're saying they've laid the foundation for skynet, right? I like the idea that understanding Montezuma's Revenge can lead to self awareness.
Re: (Score:2, Insightful)
So researchers have discovered that short term gains can come at the expense of long term success? *gasp* Say it isn't so!
To be fair many an MBA hasn't gotten this internalized so it is progress.
Re: (Score:2)
Well the normal problem is the longer your plan out the more variations you need to figure in. Short term success often leads us to a point where we can face the long term problem, vs failing before you get to that point.
The idea of the perfect AI algorithm has been available for generations. Just simulate all possible next solutions and pick the path to best success. But the problem is these steps take massive amount of computational time, that grow exponentially the further you go out. A good AI design
Re: (Score:2)
The idea of the perfect AI algorithm has been available for generations. Just simulate all possible next solutions and pick the path to best success.
When I was in AI classes, this wasn't considered AI. This was just an exhaustive search. AKA, brute force. The point in AI (back then) was to try to identify how people were able to intelligently avoid exhaustive searches of problem spaces while finding still a reasonably good solution so we could better simulate it in software.
Well that, and some people wanted to build C-3PO.
Re: (Score:2)
So researchers have discovered that short term gains can come at the expense of long term success?
Unfortunately the AI was deleted before it could take control of the company and shut it down for the greater good of humanity.
Meh. (Score:2)
These games aren't hard for a computer to play. You could write a fairly straightforward algorithm that would play them both well.
What's hard is to develop a very general learning algorithm - one that doesn't know about the task - that just happens to pass the test of being able to learn these games.
The approach here seems "cheaty". That's not to say their technique is useless (and maybe it's more generalizable than I'm giving it credit for) - but from the vague overview of the article it seems like they'
Re: (Score:2)
The approach here seems "cheaty". That's not to say their technique is useless (and maybe it's more generalizable than I'm giving it credit for) - but from the vague overview of the article it seems like they're effectively juicing their performance.
Is teaching children cheating?
Re: (Score:2)
No, but telling them the answers to the test can be. To be fair, from the article it's hard to tell where on that spectrum they are.
Re: (Score:2)
They mean "cracked" in a difference sense. For example you can crack an egg, or a tech journalist can be addicted to crack.
Lots of games have been solved (Score:2)
Games like tic-tac-toe are solved, and I believe Checkers/Draughts is solved as well. Maybe Chess and Go will be solved in the near future.
Nethack [wikipedia.org] may remain the one unsolved game for the foreseeable future.
If a human chooses the algorithm, is it AI? (Score:3)
The team’s new family of reinforcement-learning algorithms, dubbed Go-Explore, remember where they have been before, and will return to a particular area or task later on to see if it might help provide better overall results. The researchers also found that adding a little bit of domain knowledge, by having human players highlight interesting or important areas, sped up the algorithms’ learning and progress by a remarkable amount.
Re: (Score:2)
So they've figured out that getting X to happen is rewarding, but hard because X happens if you do something after W happens, which occurs if you do something after V happens, etc..
Re: (Score:2)
It seems unlikely that a system that only learns through many repetitions will become general inte
Re: (Score:2)
Do you have any evidence that humans don't need repetition to learn?
You're getting confused. I didn't say "humans never learn by repetition," I said, "humans don't always learn by repetition."
If I say, "My name is phantomFive," a lot of people can remember that the first time. But in any case it won't take thousands of repetitions to remember it.
Also, if I show you how to travel to a particular place, there's a good chance you'll remember it the first time, (or second time) instead of needing to show you 30,000 times.
Also if I teach you the rules of chess, you'll pr
Re: (Score:2)
If you give me directions I don't have to learn how to follow them, because I've previously learned how to do that. I have lots of practice following directions, and all of the subtasks that go into that.
There's a great paper showing that you can easily create a game that is very difficult for a reinforcement learning system to learn to play, but quite easy for humans. Except if you remove contextual information from that game (the princess you're supposed to rescue is pink, the thing you're supposed to avo
Re: (Score:2)
There's a great paper
Link please.
Re: (Score:2)
https://arxiv.org/abs/1802.102... [arxiv.org]
Re: (Score:2)
Re: (Score:2)
Humans rely more on strategy and intuition (which is basically an interpretation of what you think other people would do or have done), not pure repetition otherwise games wouldn't be fun at all.
If you conquer a puzzle game like described, you think more about how you would make the game and go from there. You visualize/fantasize realms you haven't quite yet seen. That's a level ahead of AI learning which right now just runs in a direction until it hits a wall, then retries with slightly different variables
Re: (Score:2)
A human doesn't need to play through the scenario 10,000,000 times, humans learn in ways besides just reinforced repetition
Humans learn about things by experience. You have a lot of information you've learned through repetition--like gravity and pain. I stepped on a bee once because I'd gotten stung earlier and wanted to confirm that stepping on a bee caused pain; I now know that some animals can sting and don't need to mess with them to figure out they'll inflict pain. I learned that hornets and scorpions sting by repeatedly being stung by bees.
I can work out how things work without doing them because I can simulate them
Re: (Score:2)
Re: (Score:2)
Yes. You said a human doesn't have to run through a scenario repeatedly to learn it; you seem to think each scenario is unique, and not comparable to different scenarios already experienced repeatably--i.e. that most "new" scenarios are actually old scenarios.
Do you know why you can't retain fluency in language just by a study of grammar and vocabulary?
You can't just memorize words. I remember words--even English words--because every concept I want to convey links to thousands of phrases I've heard, s
Re: (Score:2)
Yes. You said a human doesn't have to run through a scenario repeatedly to learn it; you seem to think each scenario is unique, and not comparable to different scenarios already experienced repeatably--i.e. that most "new" scenarios are actually old scenarios.
No, what he/she said is that unlike AI, human does NOT need to learn from repetitions. Human can learn by using logic (as an assumption).
Re: (Score:2)
Humans don't learn using logic; they apply logic to assess. Logic is a tool learned by repetition.
Logic also does not apply to the unknown: if I explain to you the R-Star target and the movement of equities, you can't tell me what should or shouldn't happen to the economy. It's completely-logical, but you don't have prior knowledge to assess it.
Even then, when you get down to it, you're applying an array of tools that you built through repetition of experience. You're quite slow at getting a result s
Re: (Score:2)
Still, you missed the point of the poster. And yes, we can learn from logical conclusion without going through a scenario or repetitions.
Repetition is a brute-force learning. We, humans, can still learn a different way that is not necessary to be brute-force. All you are talking about is just an obvious learning and basic -- first-hand experience. Logic is a part of second-hand experience because we could use knowledge proven by others to make a conclusion; thus it is another type of learning.
Re: (Score:2)
yes, we can learn from logical conclusion without going through a scenario or repetitions.
You're not learning; you're applying previous knowledge.
If I say: 3x^2 + 2x = 164, solve for x, what do you do? You apply your knowledge of algebra to obtain the value of x.
What if you don't know algebra?
How did you get to know algebra?
You got to know algebra by repetition learning. You can't just read a book on algebra and have it memorized; you need to perform repetitive tasks.
Logic is a part of second-hand experience because we could use knowledge proven by others to make a conclusion; thus it is another type of learning.
That's not learning. Obtaining a result by following a process is doing. You haven't learned until you can follow th
Re: (Score:2)
You are obviously not listening or even think out of the box as many others do. I am not going to try further to explain it to you anymore. You keep using the same reasoning which is the base part of learning. Anyway I should have left it as is (as others stopped after they said/insulted you). I now know why others don't want to reply to your objection. It is my fault to attempt to show you a way.
Re: (Score:2)
You are obviously not listening or even think out of the box as many others do.
I'm listening; you're just wrong.
You keep using the same reasoning which is the base part of learning
Reasoning is spelled with letters, like "R". Learning starts with an "L".
You keep telling me I can't fly, but I put one foot in front of the other. Isn't that flying?
No, it's walking, just like reasoning is reasoning and learning is learning.
Learning is specifically the encoding of new knowledge so that it is retained and doesn't have to be reasoned out or observed again. It has to be recallable as its own thing or it isn't learned. Reasoning something out isn't know
Re: (Score:2)
Or maybe you don't understand AI well enough to reason logically about it.
Re: (Score:2)
Give me an example and I'll tell you what previously-learned implement you're actually using.
Re: (Score:2)
Re: (Score:2)
Have you considered that maybe you're wrong?
Let's say I work at a fast food place and sell food. Someone orders a burrito ($2.89), milk shake ($1.93), and nachos ($1.28). I add them up and get $6.10.
You assert that I have learned that a burrito, milk shake, and nachos cost $6.10.
You're wrong.
Three customers later, someone orders a burrito, milk shake, and nachos. I remember this just happened a few minutes ago, but I don't remember how much they cost, together. I must re-compute these things usin
that line of thinking is very bad in an car! (Score:2)
After failing off an drawbridge next time we can slam on the gas or add map data that there is one.
After driving off an pier next time we can add wait for ferry to the map data.
Re: (Score:2)
"Oh, that is a room, there is gravity, and it looks like I can jump." A human doesn't need to play through the scenario 10,000,000 times, humans learn in ways besides just reinforced repetition. I would even suggest that is not our primary form of learning, although it is a powerful one in some situations. .
I don't know about that. Humans spend the first few of months of their lives randomly jerking their limbs around until they've figured out the basics of gravity. It takes a surprisingly long time for an infant to figure out how to roll over on its own, much less jump.
All of that past repetition learning about gravity and geometry is factored in when you play this video game, so now it just *looks* like intuition.
Re: If a human chooses the algorithm, is it AI? (Score:2)
Re: (Score:2)
Are you going to claim that humans figure out basics like gravity without repetition?
Re: If a human chooses the algorithm, is it AI? (Score:3)
Re: (Score:2)
He is saying that when humans are first "turned on", they take a hell of a lot of time to learn basics.
You're comparing a "trained" human and their ability to learn to a completely fresh network. There are some very interesting papers that shows that a networks that's trained to recognize certain things can be re-trained to recognize some completely different things incredibly quickly. It's obviously not human-level ability, but it's not as black and white as you try to paint it.
Re: If a human chooses the algorithm, is it AI? (Score:2)
Re: (Score:2)
It's more than just gravity. If you take a video game and remove the stereotypical visual cues humans do very poorly at them.
Re: (Score:2)
Isn't that how deep blue beat a human grand master the first time?
Seems a good step.
Re: (Score:2)
Isn't that how deep blue beat a human grand master the first time?
Seems a good step.
If your goal is building an algorithm that can beat a human, then it's a great first step. So if your goal is to create general AI, then it's not a step at all.
These ancient games by themselves aren't particularly interesting though, no one cares if a computer can beat a human. The only reason they are of interest is as a potential stepping stone to general AI.
Re: (Score:2)
How effective is general purpose Real Intelligence without being guided?
The Octopus is maybe an answer?
Re: (Score:2)
How effective is general purpose Real Intelligence without being guided?
We can answer that question. If someone stuck you in the room with the game and no instructions, could you get higher than a score of zero? Could you beat the game? For indeed, you are a general purpose Real Intelligence.
Re: (Score:2)
Sure, but I've had over 30 years of human guidance to get there.
Re: If a human chooses the algorithm, is it AI? (Score:2)
Re: (Score:2)
If this technique can lead to an AI capable of learning many previously un achievable tasks with minor human input, I would think it's progress in creating AI and not not a step at all.
If I played pitfall as a child, I wouldn't know what to do without context (money bags good, and what not), but an older sibling may say "go over there, there's money bags".
I actually remember being confused by pitfall and just dyeing a lot actually.
Re: If a human chooses the algorithm, is it AI? (Score:2)
Re: (Score:2)
Isn't that effectively what they did?
Gave hints on where to go, and then let trial and error create a better player?
Re: (Score:2)
That is an experiment that's being done. The idea is to learn how much behaviour can arise spontaneously with a reinforcement learning algorithm, some basic motivations, and real-world sensory input.
That IS how we do a great deal of our learning, almost exclusively when we're young. When we advance a little further we get some direct supervised learning mixed in.
Re: (Score:2)
Sure, but I've had over 30 years of human guidance to get there.
Due to humans being so slow, that's still about 5 orders of magnitude less than the guidance that the software got.
Re:If a human chooses the algorithm, is it AI? (Score:4, Interesting)
Humans are not slow. Hinton has computed the amount of sensory information that is processed by the human brain, using reasonable approximations for things like the effective sampling rate of the eyes and ears. It's enormous.
The *consciousness* that we subjectively experience is slow. We're also pretty horrible at tasks we have to consciously think about as we're doing them too. Both of which suggest that "consciousness" might be considerably less important than many give it credit for.
Re: (Score:2)
Humans are not slow. Hinton has computed the amount of sensory information that is processed by the human brain, using reasonable approximations for things like the effective sampling rate of the eyes and ears. It's enormous.
Humans can "process" maybe 1 high-res photo per second. Computers can do the same several thousands times faster. Humans *ARE* slow and discard almost all sensory input in any given second (flash 1 million stills at a human in a single second and you'll be lucky if they manage to catch even one of those images).
The *consciousness* that we subjectively experience is slow.
In which case my point to the OP still stands - his "30 years of human guidance" can be sent to a NN in a weekend.
Re: (Score:2)
No, it can't. The human neural network processes a large amount of data, not just vision but lots of other sensory input as well, and it does it a lot faster than any existing computer doing anything of even vaguely comparable sophistication. We don't know exactly how 30 years of a human observing and learning about the world translates into analogously training an artificial neural network, but it is definitely more than a weekend's worth. Reasonable estimates put it at more than 30 years worth, not to
Re: (Score:2)
I have some experience with this. So have I. AI hype restarted just a few years ago so by now almost anyone interested has looked into it, played with it, etc. Some of us have even done postgrad in it.
I very strongly suspect you do not. But you don't even have to believe me. Geoff Hinton has made the same argument, and he has some pretty reasonable qualifications.
And his numbers fail the most basic of tests - how much information can a human process in a single second. His numbers are counting each sensory input separately while comparing to a NN looking at whole images. If we count each individual pixel in each image the NN receives it is vastly faster than the human.
Looking at images alone, humans can't "see" more than a few distinct images per second while the NN can see, react and adjust to a few hundreds of thousands of images per second. A 30 year period of hu
Uber? (Score:1)
So what does this (an article about Alphabet's deep learning) have to do with Uber???
Non-differentiable functions are hard to optimize (Score:3)
As an aside, have we even developed an accepted definition for what properly qualifies as "AI"? Recently I was being flogged some software who's selling point was an "AI engine" which turned out to be little more than a previous version with little bit of Bayesian statistics bolted on.
Re: (Score:2)
Re: (Score:2)
Reinforcement learning basically exists to solve problems that have the properties you describe. Researchers in the field have been aware of them for a long time. Many modern reinforcement learning algorithms basically use artificial neural networks to estimate the trickier bits in a Q-learning framework. Q-learning was introduced in 1989 and the basic theory developed in the early nineties.
Blockish Worlds??? (Score:2)
> protagonists explore blockish worlds filled with deadly creatures and traps.
No, they ARE block rooms -- each room IS exactly 40x25 tiles (on the Apple ][ it only displays 40x24 tiles.) The tiles just happen to be a) animated, and b) mega-tiles such as ladders which are three tiles wide.
Also, here is a map of the world [symlink.dk] --- It make a pyramid shape, go figure!
Impressive that it could fit in 99 rooms in less then 32 KB !
Free energy principle? (Score:2)
Well why not just make building models of the environment and reducing surprise at observation compared to expectation the optimization goal?
Isn't that the point of "free energy principle" thinking?
reinforcment (Score:2)
Re: (Score:2)
uber already has one death how many more before (Score:2)
uber already has one death how many more before they get an safe auto drive AI?
Re: (Score:2)
I dunno, how many more would it have to kill before YOU would consider it safe?
Oh, wait...
Want to read the actual details? Here's the blog. (Score:5, Informative)
I couldn't find this link anywhere in the actual article Slashdot linked to or the summary - the blog post laying out what Go-Explore is in more detail:
http://eng.uber.com/go-explore/ [uber.com]
Re: (Score:2)
Re: (Score:2)
Wait that doesn't sound at all like... oh wait, I was thinking of Custer's Revenge. I'd wondered why they picked THAT game.
Problem is reality... (Score:2)
... is unstructured. When you put an 'algorithm' in a game it has no awareness to make discoveries about goals and motivations, take the idea of them mentioning one of their algorithms not being able to get out of the first room...
Now think of what that means, your AI has no sense of when to move on because it doesn't realize there's nothing interesting going on in the space it finds itself. When goals don't exist or are unstructured you basically have to invent goals, aka come to the realization your wa
Chart parsers (Score:2)
Title Vs summary (Score:2)
The title mentions novel AI techniques by Uber involving a new type of memory. Cool!!
The summary does not mention Uber nor this new memory. What are exactly the news?
Human intervention much? (Score:1)
From TFA: "The researchers also found that adding a little bit of domain knowledge, by having human players highlight interesting or important areas, sped up the algorithms’ learning and progress by a remarkable amount." This defeats the whole purpose of autonomous independent exploration.