AI Taught How To Play Ms. Pac-Man

trogador writes with the news that researchers are working to teach AIs how to play games as an exercise in reinforced learning. Software constructs have been taught to play games like chess and checkers since the 50s, but the Department of Information Systems at Eotvos University in Hungary is working to adapt that thinking to more modern titles. Besides Ms. Pac-Man, game like Tetris and Baldur's Gate assist these programs in mapping different behaviors onto their artificial test subjects. "Szita and Lorincz chose Ms. Pac-Man for their study because the game enabled them to test a variety of teaching methods. In the original Pac-Man, released in 1979, players must eat dots, avoid being eaten by four ghosts, and score big points by eating flashing ghosts. Therefore, a player's movements depend heavily on the movements of ghosts. However, the ghosts' routes are deterministic, enabling players to find patterns and predict future movements. In Ms. Pac-Man, on the other hand, the ghosts' routes are randomized, so that players can't figure out an optimal action sequence in advance."

Re:"AI"s tend to be overhyped

[Hado]

I feel I must comment since I am familiar with the AI used in this case: Reinforcement Learning. RL is a method of finding a mapping of states to actions in a setting where rewards can be obtained. The interesting part is that RL algorithms can learn to behave optimally when only very basic information is given. For instance, it should be enough to simply give small rewards for eating the dots and large punishments for being caught by a ghost. There are many theoretical results in the field that also hold in the case of stochastic environments (such as when the ghosts move randomly). In a sense you don't have control over the learning process, at least not in the sense that you control what exactly happens and which actions get tried. However, in the end theoretically still perfect behavior can be learned. This may take quite some time though, but fortunately good behaviors usually emerge much sooner.

That being said, it is relatively easy to apply these techniques to games such as Ms. Pacman. Much harder problems have already been solved using RL algorithms. What seems missing in the article (though I don't know if this is also the case in the actual research) is comparisons with other RL methods than their own. Though their approach sounds promising and it's nice that they beat some human players, this is not uncommon in games for RL.

Re:"AI"s tend to be overhyped

[Tyir]

Actually, what you describe is exactly what Reinforcement Learning (RL) is. RL can be considered a subbranch of AI. In RL, an agent starts by knowing nothing about the environment. It explores the environment by taking available actions, in this domain, the actions would be exactly the actions available to the human players. It also has a reward signal R, which is used to train the agent to do the correct thing. Completing the level will probably give a high reward, encountering a ghost will give a negative reward. What a RL algorithm will do is give approximations for the future value of being in any state in the environment. What the researches will do is train the agent on the domain for a large number of steps (perhaps millions of games played in simulation) and the agent will learn to play the game well. Note this require *no* domain knowledge, i.e. the programmer doesn't but any heuristics, strategies, or high level tricks to have the agent complete the game, which I believe is what you think is being done here.

So what the technique used in this paper is doing exactly what you would consider "real" AI. Full disclosure, I am a Master's student who has done a good amount of work in RL, and I have not read the paper, so what I describe above is not going to be exactly right, but is probably the general idea.

Re:The difference between Pac-Man and Ms Pac-Man

[blogan]

Ms Pac-Man also has a bow.

Re:"AI"s tend to be overhyped

[bunratty]

But that is indeed how the term has been used for decades. What you describe is taught in AI classes and is described in AI books. It's the only kind of AI we have. As such, the term isn't useless. If you want to refer to original thought by a computer, use the term "strong AI," which hasn't been invented yet.