Ms Pac-Man Competition
IEEE WCCI 2008 Results
Simon M. Lucas

Entries

There were 11 functioning entries (plus one that I was unable to run) submitted by the deadline of May 23, 2008.  This compares with 5 entries for the IEEE CEC 2007 contest, showing that the competition is gathering momentum.  There has been significant progress, with many of the entries now achieving much better scores than the default controller.

Of the teams submitting entries, only three registered for and attended the conference.  Those teams were able to run their entries live at the conference using their own machines.  There is a significant advantage in doing this, as different machines may have different screen capture and key event generation delays.  A controller that performs well when running on one machine may fail badly on another machine.

Entry Authors Affiliation
Southern Maine Fitzgerald, Kemeraitis and Bates Congdon University of Southern Maine
Handa Hisashi Handa Okayama University, Japan
Dortmund Piatkowski, Neugebauer and Naujoks University of Dortmund
     
Gan Gan, Liu and Bao n/a
Flensbank Flensbak and Yannakakis IT University of Copenhagen, Denmark
Leandro Liu and Gomez Universidad Nacional de Colombia
Ruck Kashifuji, Oda, Matsumoto, Hirono and Thawonmas Ritsumeikan University, Kyoto, Japan
Pacool Khosravi and Mehrabian Sharif Univ. of Tech., Tehran, Iran
Wirth Wirth and Gallagher University of Queensland, Australia
Shirikawa

Ando, Shirakawa, Otsuka, Takahashi, Totsuka and Nagao

Yokohama National University, Japan
Jabbari Pante Jabbari Sharif Univ. of Tech., Tehran, Iran


Results

The competition was won by Alan Fitzgerald, Peter Kemeraitis and Clare Bates-Congdon from the University of Southern Maine (USM).  Their agent achieved a high-score of 15,970 during the live Ms. Pac-Man competition session at WCCI 2008 - congratulations to them!!!

In second place is the off-site entry submitted by Gan, with a high score of 15,400.  This entry was submitted before the deadline, but I was unable to run it before the live session due to technical problems.

The full set of results is shown below.  Note that the on-site and off-site results are not directly comparable.  As mentioned above, the on-site entries had the advantage of being run by their developers on their own machines.  The off-site entries have been run 10 times because there was more time available.  The on-site entries were ranked on their high score on their first three attempts during the finals session (shown as the first three columns on the 'conf' part of the spreadsheet.  To get the same effect for the off-site entries one could simply consider the first three attempts by each system. 

The results spreadsheet below is split into the on-site and off-site entries.  For the on-site entries (conf) the first three results (columns 1,2,3) are the results during the live finals session, the remaining three (columns 5,6,7) were for the trial session.

The platform column shows the version of Ms. Pac-Man and the operating system used.  Web indicates Web Ms. Pac-Man, while MS indicates the Microsoft Revenge of Arcade version.  The versions both use emulators to run the original ROM code for the game, and appear to be identical in terms of game play.

Note that one team (Ruck) offered two entries - I've only included the best performing one (i.e. the one that performed best under the test conditions on my laptop) in the main table of results - this is Ruck (Escape).

Discussion

It's interesting to observe that the two leading entries have adopted very different strategies.  The USM entry makes little effort to eat the ghosts when edible, whereas the second place entry (Gan) uses ghost-eating to great effect.  While both entries achieve similar scores on average, I personally found the Gan entry more fun to watch.  It frequently takes outrageous risks and often escapes from seemingly impossible situations, whereas the USM entry takes a more business-like approach to efficiently clear each level.

As far as I'm aware the leading entries don't use any machine learning, though a good deal of hand-tuning has been used to make them operate effectively, and many of the entrants plan to use machine learning techniques in the future.  The USM entry has all the hooks in place it use evolutionary algorithms to adapt the parameters of its controller, so hopefully we'll see that put to good effect for the CIG 2008 contest.

While the leading entries (especially Gan) play exceedingly well at times, they often lose lives through making apparently stupid decisions - running straight into ghosts for example, when not even trapped.  However, when judging the behaviour it's important to realise that the software agents operate on a slightly delayed version of the game (having been through the screen capture and image parsing process).  Therefore, a decision that appears to be incomprehensible may have made good sense 20 milliseconds ago!

The leading entries significantly outperform previous attempts at developing software agents for the game based on machine learning (e.g. [1] and [2]).  While it should be noted that both [1] and [2] used different implementations of Ms. Pac-Man, both of these were (in the opinion of the author) easier and less entertaining versions than the original.  Also, both [1] and [2] had direct access to the game state, and did not suffer the timing uncertainties inherent in the screen capture mode of operation.

The leading entries submitted to this competition now represent the state of the art in software agent Ms. Pac-Man.  However, beating the human world record of over 900,000 remains a distant goal!

Videos

Here's a video (6mb .wmv format, or on youtube) that illustrates the operation of the Gan entry.  In the screenshot below the agent is about to commit suicide (give up the ghost ;-) by running straight into "pinky", under no threat whatsoever!  Prior to this the agent demonstrated significant skill in eating all four ghosts, and in surviving some death-defying situations.

Note: this video was made with CamStudio, and the making of the video probably interferes a bit with the game and the agent (the action is jerkier than when not making a video).  That said, this score is fairly typically of what the Gan agent achieves.

Follow-Up

Two versions of the Ms. Pac Man competition will be run for IEEE CIG 2008: the screen-capture version (described here), and also modified version where people can enter either a Pac-Man agent or a team of ghosts.  More details coming soon.

References

[1] Simon M. Lucas, Evolving a Neural Network Location Evaluator to Play Ms. Pac-Man, IEEE Symposium on Computational Intelligence and Games (2005), pages: 203 -- 210 [pdf]

[2] Szita and A. Lorincz, Learning to Play Using Low-Complexity Rule-Based Policies: Illustrations through Ms. Pac-Man, Journal of Artificial Intelligence Research (2007), Volume 30, pages 659-684 [pdf].

end of page