A team of engineers at Cornell University created a computer program that blew through previous records for computerized play of Ms. Pac-Man. The AI system learned and updated itself with each new level of play.
The old record for a computerized player was 36,820. The new record, held by a trio of researchers from the mechanical and aerospace engineering departments, produced a score of 43,720 in a laboratory setting.
[Image Source: Wikipedia]
Granted, this pales when compared to human counterparts. The most recent world record for human players goes to Abdner Ashman with a score of 921,360.
The team, led by Professor Silvia Ferrari, predicted the movements of the ghosts with 94.6 percent accuracy. They developed a decision-tree approach. This system constantly updates and runs equations to determine where the ghosts will be.
“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 in an interview with Cornell’s newspaper.
For those unfamiliar with Ms. Pac-Man and Pac-Man, the titular characters have to stay alive as long as possible. Each round ends when all items on screen have been collected. Players must guide Ms. Pac-Man through the maze and avoid the ghost enemies. The rhythmic movements of the game intrigue classic gamers and engineers wanting to program artificial players.
[Image Source: Wikipedia]
Artificial intelligence systems and learning have thrived in classic console gameplay. They provide constant challenges and benchmarks with each new level.
“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.
And according to the Ms. Pac-Man Competition website, Ms. Pac-Man offers considerably harder challenges than her ‘male’ counterpart. This makes it a favorite among engineers looking for a uniquely difficult challenge.
“Unlike Pac-Man, Ms. Pac-Man is a non-deterministic game, and rather difficult for most human players,” the site reads. “As far as we know, nobody really knows how hard it is to develop an AI player for the game.”
Other than creating a really smart system to impress friends, what’s the point of this research? Ferrari said it lies in a link between which problems are easier for humans compared to simple fixes for robots:
“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…
“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.”
For a better understanding of exactly how the AI ghosts work, take a look at the video below. If you happen to learn the AI habits, maybe you can even take on the world record score (or at least beat Cornell’s computer system):