AI takes ‘Ms. Pac-Man’ to the limit


We no longer need players to beat Ms Pac-Man

Ms. Pac-Man was supposed to be the more difficult arcade game. But now it’s been laid low — like chess, Go, and poker before it — by artificial intelligence.

Researchers with deep learning company Maluuba, which Microsoft acquired earlier this year, decided to tackle the deceptively simple arcade game after developing an unusual AI algorithm that uses a team of intelligent agents overseen by a manager agent to play Ms. Pac-Man. Those agents broke the game down into tasks and sub-tasks and were rewarded (or reinforced) for pursuing those tasks.

For example, some agents were charged with finding specific Ms. Pac-Man game pellets, while others were told to avoid ghosts at all costs. The manager agent would then analyze how the agents approached each task and the intensity they applied to them to decide which paths were, in fact, the best. Individual agents had their own reward functions and the manager would prioritize tasks that were more important. In other words, tasks like avoiding ghosts (which kill on touch in the game) were prioritized over other tasks.

Using this method, the AI algorithm soon mastered Ms. Pac-Man and reached a maximum score of 999,999, which, according to Microsoft, no AI or human has ever achieved before. Doing so, automatically resets the game.

Maluuba researcher Harm van Seijen, who also authored a paper on the AI research (which is being submitted to Cornell University on Wednesday), told me that they designed their AI based on how the iPhone is made. "It’s not a single person that makes it," he told me, adding, "It’s really inspired by how humans cooperate to do these really great things, like build really great products."

The team spent months working on the algorithms, but only applied them to Ms. Pac-Man in the last two months.

In all, there were approximately 150 intelligent agents all working in parallel on Ms. Pac-Man. To continuously play the game inside a computer, the team needed three pieces of code: the game, a routine to send actions to the game, and the learning method.

The goal of this research, van Seijen said, was never to beat the game — it was "to solve learning and behavior.” So, completing Ms. Pac-Man came as a surprise.

"It was pretty exciting, but also kind of a letdown at same point," Maluuba product manager Rahul Mehrotra.

‘It was pretty exciting, but also kind of a let-down at same point.’

After running the algorithms overnight on the game the researchers noticed some anomalies in the data, Mehrotra recalled. To understand why the scores didn’t simply keep rising, the team sat and watched the AI play the game.

"As we approached this million mark point, we started to get excited. So as soon as we got to 999,990 the game resets to zero. We were like, ‘Oh, you can’t score more than that.’ We wanted to keep going forward," said Mehrotra.

According to Microsoft’s blog post on the breakthrough, Steve Golson, one of the co-creators of the arcade version of the game, said that that the deceptively simple Ms. Pac-Man, 1980s sequel to the wildly popular Pac-Man arcade game, was intentionally designed to have less predictability than Pac-Man.

“You want [players to think], ‘Oh, oh, I almost got it! I’m going to try again,’” Golson said. “Ka-ching! Another quarter,” he said in the blog post.

Later, I caught up with Golson via Twitter DM and asked him about the score limit and his creation being beaten by an AI:

I assumed there was a 999,990 limit, just like in arcade Pac-Man and Ms. Pac-Man. A human might theoretically make it to that level, but how many hours would it be? We humans have to take bathroom breaks! Their AI just needs to stay plugged in…

Games, van Seijen said, have been traditionally very popular among AI researchers for testing algorithms and Ms. Pac-Man has already received a lot of attention in AI community. "It’s actually a very hard game to solve," he explained.

Seemingly random systems are catnip for researchers trying to test and develop ever-more powerful versions of AI. When there are countless options and no obvious pattern to the choices a system makes, basic computer systems can struggle to conquer them.

The divide and conquer approach the Maluuba researchers took, however, proved too much for Ms. Pac-Man, and allowed researchers to complete the game. And though they believe it may have applications that go far beyond the arcade, no one was willing to predict exactly when task-based AIs would appear in more complex scenarios.

"This is still a very controlled setting. Pac-Man is very compact and still doesn’t represent complexity of real-world situations," said Mehrotra.

That said, van Seijen sees a bigger goal with more far-reaching implications for AI.

"At a higher level, we want to solve AI and build really intelligent agents that can not only observe, but act. If you reach that, it could have enormous consequences."

Seriously, Game Over.