5 ms·

What indeterminate games can AI can beat humans at? Backgammon - AI usually beats the best humans Ms. Pac Man - AI loses to almost any human

john_reel 10y ago
What makes Ms. Pac Man so hard for AI?
- tim333 10y ago
  I'm not sure it's hard in general but deepmind's program didn't do well because it couldn't plan ahead https://www.technologyreview.com/s/535446/googles-ai-masters-space-invaders-but-it-still-stinks-at-pac-man/ https://www.technologyreview.com/s/535446/googles-ai-masters...
  - varelse 10y ago
    It's also inferring the game state from looking at the screen rather than being spoonfed the data. One could conceivably perform a depth-limited search on the actual game state if it were available and then use an AlphaGo-like DNN to predict what a deeper search would find, no?
    - tim333 10y ago
      Dunno really. A human would watch the ghosts behaviour and guess their likely future behaviours based on that. I'm not sure if the software gets that, as it were, or how you'd tweak it to do so.
- WhitneyLand 10y ago
  Its indeterminate because the ghosts turn in random directions with no preserve patterns. Notice Go, Chess, etc all are determinant. This paper gives an overview of the background: http://www.cse.unsw.edu.au/~mit/Papers/AAAI10a.pdf http://www.cse.unsw.edu.au/~mit/Papers/AAAI10a.pdf
antognini 10y ago
AI tends to perform poorly for many real-time games because they constitute many, many more "moves" than a game like backgammon. A backgammon game will typically take < 100 moves. For a game like Ms. Pac Man the AI will have to make that many decisions in a timespan of about four seconds. When you train a reinforcement learning algorithm, the AI has to update the parameters that were used to make several thousand decisions, and the only information it has to go on is its score at the end of the game. (This is known as the credit assignment problem --- of all the decisions you made in the game, only a few probably had a substantial impact on the outcome. How do you decide which ones were the important ones?) A game like go is hard because there are many possible moves every turn. But the games themselves are not very many turns, so it is easier to find the important moves, because in some sense all the moves were more important. A game like Ms. Pac Man is hard because, while you only have 5 moves each turn, the games themselves are many, many turns, and it is very difficult for the NNs to learn these long-term dependencies.
- WhitneyLand 10y ago
  Since a child could easily outperform the best AI here, doesn't it imply we need a different approach? Otherwise we need 4 orders of magnitude more compute, and it's just hard to believe their is no better way.
  - haimez 10y ago
    No, just means that someone needs to bother to make an AI for Ms. Pacman. Handling random ghost movements is only trivially confounding for AI learning. Low value, low yield.
    - antognini 10y ago
      It's true that someone could pretty easily hand-craft an AI that plays Ms. Pac-Man pretty well. But that's not really the point. Because after all that work, you still only end up with a computer program that can play Ms. Pac-Man. It won't play Pong, it won't play Doom, it won't even be able to play regular Pac-Man! The goal is to build a general system that can learn how to play specific games on its own. So, there is potentially high value to developing a Ms. Pac-Man AI, but only if it's not really a Ms. Pac-Man AI, but actually a more general AI, for which playing Ms. Pac-Man is a specific instance. I agree with the parent comment that some sort of new approach is probably needed. The main issue with reinforcement learning is just that the algorithm gets too little feedback. This ends up discarding an enormous amount of data on each run (or, more accurately, learning from that data extremely inefficiently). There's a huge amount of data present, but the learning from that data has to be unsupervised. A child can do it easily --- they only have to play Ms. Pac-Man once or twice to get the hang of it. Computers currently cannot. Getting them to do that will definitely require something different, but no one is quite sure what.
sherjilozair 10y ago
Note that most of recent work in reinforcement learning focus on creating a model which works on all or most of Atari games without using any game-specific knowledge. If researchers were to focus on only Ms. Pac Man, and ignore the "no game-specific tuning" rule, then Ms. Pac Man, and most Atari games would be solved to near perfection. The challenge that the Atari suite provides is not their individual difficulty, but the difficulty imposed by their diversity, i.e. finding a general algorithm which works well on all Atari games is hard.
- WhitneyLand 10y ago
  I don't know why so many people are suggesting this is easy. Many other attempts has been made targeted specifically against Ms. Pac Man and none have come anywhere near beating an average human player.
varelse 10y ago
Conventional AI can clean up at Pacman if it can do tree search on the game state, source: CS188 out of Berkeley. http://ai.berkeley.edu/lecture_videos.html http://ai.berkeley.edu/lecture_videos.html
- WhitneyLand 10y ago
  Pac Man is easy. Ms. Pacman has been tried and failed by many people who know CS188 material.
  - varelse 10y ago
    Do these attempts make use of the documented idioscynracies of Ms Pacman? http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior http://gameinternals.com/post/2072558330/understanding-pac-m...

john_reel 10y ago

What makes Ms. Pac Man so hard for AI?

tim333 10y ago
I'm not sure it's hard in general but deepmind's program didn't do well because it couldn't plan ahead https://www.technologyreview.com/s/535446/googles-ai-masters-space-invaders-but-it-still-stinks-at-pac-man/ https://www.technologyreview.com/s/535446/googles-ai-masters...
- varelse 10y ago
  It's also inferring the game state from looking at the screen rather than being spoonfed the data. One could conceivably perform a depth-limited search on the actual game state if it were available and then use an AlphaGo-like DNN to predict what a deeper search would find, no?
  - tim333 10y ago
    Dunno really. A human would watch the ghosts behaviour and guess their likely future behaviours based on that. I'm not sure if the software gets that, as it were, or how you'd tweak it to do so.
WhitneyLand 10y ago
Its indeterminate because the ghosts turn in random directions with no preserve patterns. Notice Go, Chess, etc all are determinant. This paper gives an overview of the background: http://www.cse.unsw.edu.au/~mit/Papers/AAAI10a.pdf http://www.cse.unsw.edu.au/~mit/Papers/AAAI10a.pdf

antognini 10y ago

AI tends to perform poorly for many real-time games because they constitute many, many more "moves" than a game like backgammon. A backgammon game will typically take < 100 moves. For a game like Ms. Pac Man the AI will have to make that many decisions in a timespan of about four seconds. When you train a reinforcement learning algorithm, the AI has to update the parameters that were used to make several thousand decisions, and the only information it has to go on is its score at the end of the game. (This is known as the credit assignment problem --- of all the decisions you made in the game, only a few probably had a substantial impact on the outcome. How do you decide which ones were the important ones?) A game like go is hard because there are many possible moves every turn. But the games themselves are not very many turns, so it is easier to find the important moves, because in some sense all the moves were more important. A game like Ms. Pac Man is hard because, while you only have 5 moves each turn, the games themselves are many, many turns, and it is very difficult for the NNs to learn these long-term dependencies.

WhitneyLand 10y ago
Since a child could easily outperform the best AI here, doesn't it imply we need a different approach? Otherwise we need 4 orders of magnitude more compute, and it's just hard to believe their is no better way.
- haimez 10y ago
  No, just means that someone needs to bother to make an AI for Ms. Pacman. Handling random ghost movements is only trivially confounding for AI learning. Low value, low yield.
  - antognini 10y ago
    It's true that someone could pretty easily hand-craft an AI that plays Ms. Pac-Man pretty well. But that's not really the point. Because after all that work, you still only end up with a computer program that can play Ms. Pac-Man. It won't play Pong, it won't play Doom, it won't even be able to play regular Pac-Man! The goal is to build a general system that can learn how to play specific games on its own. So, there is potentially high value to developing a Ms. Pac-Man AI, but only if it's not really a Ms. Pac-Man AI, but actually a more general AI, for which playing Ms. Pac-Man is a specific instance. I agree with the parent comment that some sort of new approach is probably needed. The main issue with reinforcement learning is just that the algorithm gets too little feedback. This ends up discarding an enormous amount of data on each run (or, more accurately, learning from that data extremely inefficiently). There's a huge amount of data present, but the learning from that data has to be unsupervised. A child can do it easily --- they only have to play Ms. Pac-Man once or twice to get the hang of it. Computers currently cannot. Getting them to do that will definitely require something different, but no one is quite sure what.

sherjilozair 10y ago

Note that most of recent work in reinforcement learning focus on creating a model which works on all or most of Atari games without using any game-specific knowledge. If researchers were to focus on only Ms. Pac Man, and ignore the "no game-specific tuning" rule, then Ms. Pac Man, and most Atari games would be solved to near perfection. The challenge that the Atari suite provides is not their individual difficulty, but the difficulty imposed by their diversity, i.e. finding a general algorithm which works well on all Atari games is hard.

WhitneyLand 10y ago
I don't know why so many people are suggesting this is easy. Many other attempts has been made targeted specifically against Ms. Pac Man and none have come anywhere near beating an average human player.

varelse 10y ago

Conventional AI can clean up at Pacman if it can do tree search on the game state, source: CS188 out of Berkeley. http://ai.berkeley.edu/lecture_videos.html http://ai.berkeley.edu/lecture_videos.html

WhitneyLand 10y ago
Pac Man is easy. Ms. Pacman has been tried and failed by many people who know CS188 material.
- varelse 10y ago
  Do these attempts make use of the documented idioscynracies of Ms Pacman? http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior http://gameinternals.com/post/2072558330/understanding-pac-m...