AI achieves highest ever score on Ms Pac-Man

Scientists have developed an artificial Pac-Man player that has achieved the highest ever score for computerised play, using a novel approach for computing real-time game strategy.

In the popular arcade game, Pac-Man must evade ghost enemies while she collects items and navigates an obstacle-populated maze. The game is somewhat of a favourite among engineers and computer scientists who compete to see who can programme the best artificial player.

The record score at the annual Pac-Man Screen Capture Competition stands at 36,280, but researchers led by Silvia Ferrari, professor at Cornell University in the US, have produced a laboratory score of 43,720. The score was achieved using a decision-tree approach in which the optimal moves for the artificial player are derived from a maze of geometry and dynamic equations that predict the movements of the ghosts with 94.6 percent accuracy. As the game progresses, the decision tree is updated in real-time.

"The novelty of our method is in how the decision tree is generated, combining both geometric elements of the maze with information-gathering objectives," said Ferrari, who noted that the information in this case is the fruit Pac-Man collects for bonus points. Her team is the first to mathematically model the game's components, whereas previous artificial players were developed with model-free methods. Engineers take an interest in artificial players because they provide a benchmark challenge for developing new computational methods that can be applied to practical needs such as surveillance, search-and-rescue and mobile robotics.

"Engineering problems are so complicated, they're very difficult to translate across applications. But games are very understandable and can be used to compare different algorithms unambiguously because every algorithm can be applied to the same game," Ferrari said. Ferrari's Pac-Man player faces its own challenges against human players. The study found that the artificial player was not able to average better scores or produce higher scores against humans who routinely played the game."It's very interesting which problems are easier for humans and which are easier for computers," said Ferrari. "In the case of Pac-Man, our mathematical model is very accurate, but the player remains imperfect because of an element of uncertainty in the decisions made by the ghosts," she added.

However, the model did produce better scores than beginners and players with intermediate skills. The artificial player also demonstrated that it was more skilled than advanced players in the upper levels of the game where speed and spatial complexity become more challenging. The study was published in the journal IEEE Transactions on Computational Intelligence and AI in Games.