The classic arcade game Ms. Pac-Man is beloved because of its simple, yet challenging premise of the female animated character evading ghost enemies, while collecting items and navigating an obstacle-populated maze.
Call it cheating to win or just a novel approach to beating a very hard game, but researchers at Cornell University have developed an artificial Ms. Pac-Man player that utilizes geometry and dynamic equations to predict the movements of the ghosts to beat a previously held high score.
Engineers and scientists frequently compete to see who can program the best artificial player. The previous record score at the annual Ms. Pac-Man Screen Capture Competition stood at 36,280, but Cornell was about to produce a laboratory score of 43,720. Using a decision-tree approach, the equations were able to predict, with a 94.6 percent accuracy, the path of the ghosts and, as the game progressed, the decision tree was 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,” says Silvia Ferrari, professor of mechanical and aerospace engineering at Cornell. The information in this case is the “fruit” Ms. Pac-Man collects for bonus points. Ferrari says this is the first time the game’s components have been mathematically modeled. Previous artificial players were developed with model-free methods.
The goal of the project is to provide a benchmark for developing new computational methods that could later be applied to areas outside of video games, such as surveillance, search-and-rescue and mobile robotics.
Unable to Beat Humans
Interestingly, the artificial Ms. Pac-Man was able to match the average scores of human players that routinely played the game, however, against beginners and even some intermediate players the artificial Ms. Pac-Man was beaten. The artificial player was shown to demonstrate more skill than advanced players in the upper levels of the game where speed and complexity become more challenging, researchers say.
While the project is now on hiatus, Ferrari says the team may revisit it in the future to improve the artificial player by adding a component that would allow it to autonomously learn from its mistakes as it plays more games.