AI with Pacman1527 words. Time to Read: About 15 minutes.
I did it! I know this post is late, but that’s because I wanted to conquer this project so I could post about it. So that’s what I’m doing. One of the courses I’m taking (of the many – I’ve got a short attention span. I’m working on it) is an AI course on edX. So far, it’s one of the most interesting courses I’ve taken. It’s also one of the hardest classes (including my M.E. undergrad) I’ve ever taken.
Let me talk about the project. The course provided a lot of the infrastructure for the Pacman game: displaying it, running it, testing it, grading it, etc. Part of what made the project so hard was all of the files that were included – over 20! I kind of imagine this is what getting a job at a tech company feels like, in micro-version. I had to hunt through all of the files and figure out what did what and which classes got used where. Luckily, the documentation and variable/function/class naming were on point, which made it fairly intuitive.
The main assignment was for me to build the brain for PacMan in various stages. I’ll go through my solutions, which could definitely be improved, but they worked and I got the grade, so nyeh. I was able to accidentally abstract quite a bit out, which ended up making much of the repetitive work super easy. The first few questions asked me to implement various search algorithms, but as it turns out, they are basically all the same with a different sorting function. You’ll see what I mean.
Generic Search Algorithm
Once that was complete, I could roll through the search algorithms fairly easily:
The next (and harder) thing is to implement heuristics for the A* search shown above. A heuristic is an estimate of the cost from a state to the goal state. When using a graph search, in order to guarantee optimal solutions, the heuristic needs to be “admissible” and “consistent.” Admissible means that the heuristic never over-estimates the cost to the goal. This is a delicate balance, though, because the larger the heuristic values, the faster the algorithm goes. Consistency means that the cost from node to node is never less than the heuristic. Luckily, consistency implies admissibility, and if you can get an admissible heuristic, it usually ends up being consistent. The hard part is proving admissibility.
I used two main heuristics: a greedy Nearest Neighbor approach that worked really well but would not be admissible in certain geometries, and a really simple manhattan distance (x distance + y distance) heuristic that didn’t work as good but was definitely admissible.
The other things were just expanding these concepts, working with problems of more than one dot, or four dots separated into the four corners, etc. I could have gotten deeper into optimizing the shortest distance heuristic to work in all cases, but as I started to research this, I found out that that is a pretty standard CS problem without an easy solution. I didn’t want to work that hard if the Manhattan heuristic would work just fine. My only regret is that I couldn’t come up with one that automatically detected the worst-case behaviour of greedy Nearest Neighbor and regressed to the simple Manhattan heuristic.
Fun Link Time!