PacMan: what kinds of heuristics are mainly used?

Question

Beside A*, BFS, DFS and the like, what are other good path-finding algorithms/heuristics popularly used in Pacman? I don't think the ones I mentioned will work if there're more than one fruits for pacman to find.

I need some good path-finding algorithms that PacMan can use to finish the maze with the least possible step-count. I've tried to search around for a guideline, but so far no luck. A* with Manhattan distance is mentioned everywhere but it will only work with mazes with only one (or two? or maybe up to a few?) fruit to get.

BTW, to keep things simple, assuming that there're no ghosts around.

Some examples from the original PacMan problems: First, Second and Third

Answer 1

Heuristic which worked for me if you know the look of labyrinth:

1. Find real distance between two currently furthest fruits in labyrinth - let's call that x.
2. Find real distance from current Pacman position to the closer of previous two fruits - let's call that y.

Then, answer is just: x + y.

Note that real distances are not Manhattan distances, but real distances in maze - you can calculate that (even precalculate if you want) because you know the look of labyrinth (you know all the walls, ...). This information (real distance between some two points in maze) is static because walls don't change.

The interpretation of this x + y formula could be something like this:

• x - either way, you will have to travel this distance, at least at the end
• y - while you are at the some of the two furthest fruits, it's better to collect the food that is near to it so you don't have to go back

If you are solving this as a part of Berkeley AI class project, for calculation of real distance between two points you could use function mazeDistance(pos1, pos2, gameState) which is already implemented and is using your implementation of bfs. Also, this heuristic is admissible and consistent, at least for their test cases. By the way, with this heuristic I managed to expand just 376 nodes in trickySearch maze.

Answer 2

You comment says you are looking for shortest path. This problem is a variation of TSP on a planar graph, and thus is NP-Hard.

Possible heuristics function for A* that can solve the problem but is not admissible [thus the path found is not guaranteed to be optimal]:

Sum of manhattan distances from all fruits to the agent.

You can also use an edmissible heuristic, of #fruits - but it will take a long time.

If you are looking for optimal, well - it is hard. You can try all permutations of fruits, and check the total distance you need to travel. This solution is factorial in the number of fruits, and if it is greater then 20 - with naive bruteforce - it will take too long. You can somehow make it better by reducing the problem to TSP, and use dynamic-programming solution, which is also exponential, or some heuristical solutions to TSP.

---

One can also improve the non-admissible heuristic solution to provide an any-time algorithm:

iteratively run A* with a decreasing heuristic function: h(v) = h'(v) / m, where h' is the heuristic function on last iteration of A*, and m > 1. This guarantees that at some point, your heuristic function h will be admissible - and the solution found will be optimal. However, each iteration is expected to take much longer then the previous one [exponentially longer..]

Answer 3

I found the closest approx food(using manhattan distances) but for my heuristic I used the actual distance from my position to the closest food. To this I added 1 for all those food points that dont share row or column with my position or closest food point.

Because the food points that do share row or col with my position or closest food position would be eaten while going from my position to the closest food and Ive already counted the cost of this in the actual distance I mentioned in the second line.

So, in short: heuristic = mazeDistance(my position, estimated closest food) + points left out

This was admissible and consistent. With this I was expanding 5500 nodes and got a 5/4 on the FoodHeuristic. https://github.com/sukritiverma1996/Intro-to-AI-course

Answer 4

I know this is old, but there are probably a lot of other people out there looking to solve this problem (it's part of Berkeley's free AI class). There's a lot of brute force suggestions, so I'll contribute a fairly simple one that gets pretty close and IS ADMISSIBLE:

1. Find the nearest fruit
2. Remove that fruit from the list of remaining fruits and add the distance to the total
3. Find the nearest fruit to this fruit
4. return to step 2 and repeat until there are no more fruits
5. return the total

edit: Previous claim that this is an admissible heuristic is false. Sorry!

Answer 5

You could brute force it for small numbers of fruits in a reasonable sized maze.

• Create a graph with a node for each piece of fruit in the maze.
• Use A* or similar to find the distance between each pair of fruits. (You will need O(n^2) runs of A* to get all the pairwise distances between n fruits.)
• Link the nodes (fruits) in the graph with edges weighted by distance.
• Find the cheapest cycle in the graph (visiting all nodes at least once) by brute force. See cheapest cost traveral on complete graph.

Answer 6

I found two solutions.

The first is Antonio Juric's solution above, which calculates an excellent heuristic. However, this uses mazeDistance(), which calls BFS(), multiple times. This makes it very slow to calculate, and is akin to solving the problem using UCS, then using your solution to solve it again using A*.

My other solution, which checks 8475 nodes for me in trickySearch (but is twice as fast as the first solution), is as follows:

Let pos = the pacman's current position Let near = the coordinates of the closest piece of food by manhattan distance. Let MHD(a,b) = the Manhattan distance between a and b. Let far = the piece of food with maximum MHD(far,near).

The heuristic is calculated to be MHD(pos,near) + MHD(near,far). This is admissible and consistent. It is not as good of a heuristic, but it's much faster to calculate.

Answer 7

For eating all dots problem, I used the heuristic value as the maximum value of all the manhattan distances from all the food points to the current Pacman position. This is admissible as Pacman needs to travel at least this much distance to reach to the goal point. It is also consistent since the manhattan distance heuristic from a single point is always consistent. It expanded 9551 search nodes in the tricky search problem.

For corners food problems, use the heuristic as the sum of the first closest food from the Pacman. Relocate the Pacman to this food position, then repeat the previous step until all food pellets are get eaten. This is a greedy approach, which need not be admissible and consistent but this is a special scenario and it can be shown that this heuristic is admissible and consistent by considering all the cases. It expanded 485 nodes in the medium search problem.

Answer 8

if you want to reduce the number of nodes expanded and don't care about running time, I would recommend using Minimum Spanning Tree, the cost of edge should be mazeDistance and using a priorityQueue, every time adding a node into visited node, look for the nearest node to just added node and then adding it to visited node, until all the food node has been added into visited node. If you are doing with AI course problem, the node expanded should be very low.

Answer 9

Assuming this is for the Berkeley AI project:

In the general case, finding the shortest path that visits every dot is NP-hard. However, that does not mean it is hard in practice. The reason is because there are fixed parameter tractable algorithms and the Pacman mazes provided fall under the case of graphs that are easy to solve.

In particular, for any given branch-width, the shortest path can be found in time polynomial in the size of the graph (but exponential in the branch width of the graph) by a simple application of dynamic programming. This does not violate the NP-hardness since arbitrary graphs can have a large branch width, but it means that the problem can be solved efficiently if you only care about graphs that have a low branch width. The Pacman mazes provided have poor connectivity, and hence a low branch width.

For more details, see this post.

Answer 10

Heuristic that I used that took about 9 seconds to find the path by expanding 1844 nodes for trickySearch:

1. Find the food that is nearest to pacman's current position using the mazeDistance function. Let's say that the maze distance to this nearest food is min_dist and the position of this food is nearest_food.

2. Find the food that is farthest to pacman's current position using the same method as above. Let's call the position of this food farthest_food.

3. Now the heuristic that is returned is min_dist + mazeDistance(nearest_food, farthest_food)

This heuristic is consistent because if there are only 2 food points in the maze, the shortest path would be to collect the nearest food and then the farthest food. And as the number of food grows, it naturally takes more steps to collect the additional food.

Answer 11

in a given game state, say md(x) is the manhattan distance from pacman to node x, consider minmd(X) as a function that return xmin s.t md(xmin)<=md(x) for all x in X. let X be the set of foods pacman has got left to eat.

Than think about it - if you consider a relaxation of your pacman world in which there are no walls, pacman cant walk less than md(xmin) where xmin=minmd(X) to eat some fruit, and then (after pacman has moved to xmin in order to eat it) if it wants to eat another fruit he must go no less than md(xmin1) where xmin1=minmd(X-{xmin}) and so on. return the sum of the mds pacman walked from xmin to xmin1 to xmin2 and so on and since this is an optimal solution to the relaxation you got yourself a great admissible and cosistent heuristic function!

Another point to consider, is that you can even get a better heuristic if you consider the walls, this is much tougher problem so i didnt get into it much, but I noticed that if you bound pacman in a rectangle with the next optimal fruit, he will have to pay at least 2 more actions if theres some FULL vertical or horizontal wall line between them because he would have to exit the bounding rectangle and re-enter it again paying at least 2 actions while doing so for each such wall. This can be further examined and you can also find more special features in this rectangle.

EDIT:

This heuristics is not admissible, thanks @Alon Gouldman for seeing that.