The Pacman Project
Results and discussion
The results for this project are quite promising. The engine is running stable and did not crash a single time up to now. All the game condition checks are done right for all the situations encountered by now. Pacman is eaten by the ghost when he is within a certain range, he eats the pills when in a certain range to the pills, the power pills are also eaten. The only thing that is not implemented yet due to time constraints is the eating of the ghosts whenever pacman is blue even though everything was prepared for it, the last day to implement it is missing in the end.
For the simulation however, everything showed to work out fine. The modelling of the real life situation was improved by introducing the randomness for players at decision points. Some of the random choices that would kill pacman are ruled out of course. Without the randomness, the games would be static and there would be no need to compute more than one game to determine the fitness. With randomness, it can be seen how well the heuristic is able to react to changes. Simulating a game takes about 350ms on average depending on the heuristics that are used. With one of the heuristics with trained parameters, this can take up to 600ms. This happens because the fitness of the chromosomes is determined by the average length of games and the number of pills eaten.
The real time simulation shows to be quite useful when trying to understand why pacman or ghost make unlogical decisions at certain points. Also it is nice to see how the training changes the behaviour of the artificial players.
The evolutionary algorithm is one of the biggest improvements to the project. The training process for Pacman is obvious from the second generation on. While the first generation has an average fitness of about 2.4 pills eaten per game and a playing time of about 25 minutes, the second generation already reaches a fitness of about 5.2 pills eaten and a game time of about 55 minutes on average. Afterwards, the improvements are going rather slow. This is why after 20 generations only a fitness of 6.08 pills per game and an average game time of 65 minutes is reached. Due to time restrictions the training could not go on for more than 20 generations, since simulating those 20 generations for a population of 50 with 50 games per chromosone to evaluate takes about 9 hours already and noone could afford to not work on the project for that longer than a night. Even after 20 generations, the pacman never managed to win a game, which is probably related to the small map size, the simplified location representations and the basic movement possibilities.
For the ghosts, the training is not done yet, since on the map we are currently playing on is so small and the initial configuration of the ghost players is quite strong already due to the fact that they try to spread over the map and try to enclose the last eaten pill such that the pacman can not leave from there.
In conclusion it can be said, that the project was very broad in its use of programming languages and problem solving concepts. Therefore, the main challenge was not only to implement the Artificial Intelligence advisor but even more to communicate between all the different modules over all the platforms. The engine showed to work reasonably well in the end although more training together with a better implementation of the AI would be desirable. To avoid that pacman gets into those situations where he does not have a chance to escape any more, the implementation of a minimax tree search with alpha-beta pruning could add the significant improvements. In total, our group has put a lot of effort into the project, earned a lot of experience from it in AI development as well as in Web development, PDA development and Remote Procedure Calls (RPC). Furthermore, it can be said that our group is quite happy with the results considering that we had several projects to do besides and taking the complexity of the application into account.