If your youth was misspent dodging “ghosts” in the video game – in which the player controls a munching blob around a grid – you may be bemused to learn that a computer program has learned to play just as well, but using different tactics.
In the popular 80s arcade game, the unofficial sequel to Pac-Man, the blob avoids killer ghosts while earning points for eating dots and fruit. If the blob has eaten a special “power” dot, it can eat the ghosts for more points.
András Lõrincz and István Szita at Eötvös University in Budapest, Hungary, started by giving their Ms Pac-Man program a selection of possible scenarios, such as “if ghost nearby”, and possible actions, such as “move away”. The program randomly combined scenarios with actions to produce rules, and then played games using random combinations of those rules to deduce which ones work (.
Advertisement
The program also set priorities, important for situations in which two rules conflict. The most important rule, it decided, was to avoid being eaten by ghosts, followed by pursuing any edible ghost. The next rule says that if all moves seem equally good, don’t turn back as you have already eaten the dots in that direction.
The resulting program narrowly outperformed average human players, but failed to evolve certain tactics that humans find useful, such as waiting for ghosts to approach before eating a power dot to minimise the time taken to eat it.
