Ms. Pac-Man gobbles up new high score using AI algorithm
A new artificial intelligence algorithm has powered Ms. Pac-Man to set a new high score.
The algorithm uses the so-called decision tree approach, allowing the computer to predict the movements of ghosts, which Ms. Pac-Man must avoid, with almost 95 per cent accuracy. Based on these predictions and the geometry of the maze in which the player operates, the algorithm deduces the optimal moves.
The algorithm has achieved a score of 43,720 in trials, which is almost 7,000 points more than the current record at the annual Ms. Pac-Man Screen Capture Competition.
“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 Silvia Ferrari, professor of mechanical and aerospace engineering at Cornell University, who led the team behind the project.
The game, popular among engineers working on artificial intelligence, asks players to collect items in a maze while avoiding obstacles and enemy ghosts.
According to Ferrari, the new artificial player is the first that models the game’s individual components and changes its strategy in real time in response to what’s going on.
While computers are able to beat even the best human chess players, their performance in Ms. Pac-Man is not that superior. The Cornell algorithm was not able to consistently achieve better scores than the top human players.
“It's not completely understood right now what elements of a problem allow humans to outperform computers and it is a question we are investigating with neuroscientists through collaborative projects supported by the Office of Naval Research and the National Science Foundation,” said Ferrari.
“In the case of Ms. 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.”
However, Ferrari's 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.
Developing artificially intelligent game players helps researchers break down complex problems, which need to be tackled for the advancement of robotics or surveillance.