Last week I attended the IEEE Conference on Computational Intelligence and Games (CIG 2010). This conference (it was actually a symposium in the early days) was started by Simon Lucas and myself in 2005. I also co-chaired the conference with Susil Louis in 2006. The conference has been run every year since 2005, with the lastest one being held in Copenhagen, chaired by Georgios N. Yannakakis and Julian Togelius.
This year I had a paper that was developed as part of a 2nd Year Group Project (the teams members are shown in the picture).
As part of the Computer Science undergraduate degree at the University of Nottingham, second year students are assigned to groups and given a software engineering task to work on. Last year, I set the following:
Your task is to write a computer program that can play the game of Pacman, without human intervention. This is a challenging task and, without some support would, perhaps, be impossible for a second year group project. However, this task has been an ongoing competition for a number of years and there is lots of information/support available, as well as examples as to what can be achieved.
Your starting point should be the web pages of Professor Simon Lucas at the University of Essex, who organises the competition. Therefore, take a look at this web page. This is ESSENTIAL reading and you should study this page (and associated links) before our first meeting. You should also make regular visits to the page as I know that Professor Lucas is planning to update it on a regular basis. Using the information on this web site you should be able to get a system up and running quite quickly and then you have to develop your own algorithms to produce the best automated player that you can.
I would expect you to carry out (at least) the following tasks, with the first two feeding directly into your literature review:
By referencing the competition entries, find out what algorithms appear to have worked well in the past.
Investigate and draw up a set of algorithms that you think could be used as a Pacman Controller. These algorithms might be based on various criteria such as those identified in 1 (above), “Manhattan Distance”, “Straight Line Distance”, “Trying to eat the ghosts”, “Trying to avoid the ghosts”, “Trying to eat the fruit”, “Maximising the score, whilst minimising your chances of being eaten”, etc. There is probably not one good overall strategy and you might consider changing strategies as the game state changes. You might also want to consider how much you plan ahead and how much you just make quick decisions, given that this is a real time game.
As part of the supplied toolkit you are provided with screen capture software (and a window showing you a representation of the captured game state), the game screen itself and a small screen showing the current direction of the Pacman character. As part of this project, I would also like you to develop another GUI element which enables you to select from amongst the algorithms that you have implemented, keeps track of their high score, enables you to choose how “adventurous” the player will be, enables you to mix/match the algorithms etc. Part of the project will be to design this GUI element, deciding what role it should play in the overall software architecture. You can then use this captured information as a basis for the analysis in your final dissertation.
Implement the int move(GameState gs) that is provided in the sample toolkit in order to test out the various game playing algorithms that you have investigated in points 1 and 2 above.
You might want to look at look at the YouTube Video for the competition entry from WCCI 2008 (google “YouTube WCCI pacman”). To give you some indication of the current state of the art, the most recent competition (run in Milan in August 2009), the winning entry achieved a score over 30,000 and reached (from memory) level 5 (it might have been level 4). If you can get anywhere near that you will be doing very well.
The project group did so well that the team not only won the prize for the best project but the School also agreed to fund one of the team members to attend the conference to enter the competition. As a result we also wrote a paper which was a accepted at the conference and the student presented it (a big undertaking for an undergraduate student, but he did very well).
In the competition, we came a VERY respectable third. In second place were last years winners. In first place was a new team who used an Ant Colony based method.
The difference between the top three entries was not that large, with the winning entry getting about 21,000 points.
In fact, during pre-competition testing our team achieved scores of over 22,000 on many occasions, with our best ever score being just over 30,000 (I am sure that the other entrants also have similar sob stories to tell :-)).
If you are interested the reference for our paper is.
Bell N., Fang X., Hughes R., Kendall G., OReilly E. and Qiu S. (2010) Ghost Direction Detection and other Innovations for Ms. Pac-Man. In proceedings of the the 2010 IEEE Conference on Computational Intelligence and Games (CIG’10), 18-21 Aug 2010, Copenhagen, Denmark, pp 465-472
It can be downloaded from here.
The references for the first and second placed entries are.
- Emilio M., Moises M., Gustavo R. and Yago S. (2010) Pac-mAnt: Optimization Based on Ant Colonies Applied to Developing an Agent for Ms. Pac-Man. In proceedings of the the 2010 IEEE Conference on Computational Intelligence and Games (CIG’10), 18-21 Aug 2010, Copenhagen, Denmark, pp 458-464
- Thawonmas R. and Ashida T. (2010 Evolution Strategy for Optimizing Parameters in Ms Pac-Man Controller ICE Pambush 3. In proceedings of the the 2010 IEEE Conference on Computational Intelligence and Games (CIG’10), 18-21 Aug 2010, Copenhagen, Denmark, pp 235-240
More details about the Pac-Man competition can be found at Simon Lucas’ Pac-Man page.