ms. pac-man evolves

There was an interesting news item today on the New Scientist website:

Computer learns to out-munch humans at Pac-Man

If your youth was misspent dodging “ghosts” in the 1980s video game Pac-Man … you may be bemused to learn that a computer program has learned to play just as well, using tactics that it developed by itself.

read the full article »

Two Hungarian researchers have developed a version of Ms. Pac-Man where the place of the human player has been taken by (what sounds like) a “genetic programming” or “reinforcement learning” artificial intelligence system. If it’s doing what I think it’s doing, the system will be built with basic rules and goals for the game world and then left to combine these rules and random variations thereof to see which combinations lead to the best results. These winning rules are then recombined in a further evolutionary cycle to produce next generation rules that, with any luck, lead to even better results. Rinse and repeat.

The researchers report that their system has learned to play the game at least as well as an “average” human player, but interestingly has not evolved certain tactics that humans have found useful, such as waiting for ghosts to approach before eating a power dot to maximise the potential effect of the dot.

It’s interesting stuff and part of their broader research into how current game AI implementations lag behind human intelligence. What I’d like to see is this implementation turned around so that the ghosts can evolve better strategies to capture the player!

The full report on their work is available in an academic paper entitled “Learning to Play Using Low-Complexity Rule-Based Policies: Illustrations through Ms. Pac-Man (Szita and A. Lorincz 2007)” and is available to download as a PDF or PostScript file from the Journal Of Artificial Intelligence Research website:

http://www.jair.org/papers/paper2368.html

What the paper doesn’t tell me is just how in hell I can get a job like that?!