Even though Pac-Man is deterministic (not really random), a GA solution was never really sufficient for solving it. For example, say we have two GA "Children", or sequences of moves that are 30 steps long. Each one moves Pac around the maze differently. The standard GA crossover/breeding method is to take two children, split them both at the same point (ie: 15 steps in), swap their parts, and bammo... you have two new children. The problem with doing this (which is what I did for this implementation) is that by 15 steps in (or even 3 steps in) the next move will have a completely different result. Think about if Pac were at the top of the screen for one of those and the bottom of the screen for the other. I should have done crossovers based on Pac's position in the maze... but even then, the Ghosts might be in different placements. In one child, it might be safe to go north from a specific location, but in another child, there might be a ghost there. The whole point of doing a GA, and breeding these movement paths was entirely futile. The only reason it ever got decent at playing at all was that it would randomly go through moves until it got further. It basically did a brute-force method on solving the problem, which is what GA is meant to prevent.
The optimum solution for Pac-Man (or his wife, Ms.Pac-Man, which is non-determinisitc) would be to implement a Genetic Programming solution instead of the GA solution.
As far as implementation, the code that determined when to send down control changes to the game was always pretty shaky. I should have spent more time to figure out exactly when to look for a new control change. I think what I ultimately ended up with was a "send the next control message when Pac is at a coordinate that is a multiple of 8 pixels" or something like that. (This was part of the code that was borrowed from the "Pac Tape" project, but for some reason, I felt it necessary to modify it. *shrug*)
The software was blind. This is just fine for a GA. If this were to
be upgraded to use a GP with something like my small LISP
interpreter, then some kind of 'vision' for Pac would be needed,
so that programs like "Move forward if there is a ghost to the north"
can be implemented. Regardless, this is outside of the scope of the
project, and is only mentioned here to get this thought out of my head.
source |
|||
binary |