I played with the Pacman programming assignment given to the Standford class (NOT to our online class) and found a result for the trickySearch Q7 problem with only 379 search nodes expanded. In the statement of the question, it is said that it is hard to get fewer than 7000 nodes expanded. Thus, the result I get seems almost too good to be true. As far as I can tell, by putting an explicit check to verify that the heuristic cost never decreases by more than 1 at each step in the expansion, my heuristic is consistent. I am also pretty sure that it is admissible. Is there anything else I can do to verify that I use a valid heuristic?

I should note that the heuristic I use is particularly suited to maze layouts like the trickySearch one. When I use it for the seemingly simpler tinySearch, I get 568 nodes expanded.

asked 16 Oct '11, 02:12

aroberge's gravatar image


Have you tried running it on mediumSearch?
(16 Oct '11, 06:03) Maxim Maxim's gravatar image
Yes, and I had to stop it since, after 20 minutes of run time, it had not come up with a solution and was requiring over 2GB of memory.
(16 Oct '11, 08:31) aroberge aroberge's gravatar image
can you link to the assignment pages and any other references pls ;)
(16 Oct '11, 08:34) Merlin Merlin's gravatar image
Those assignments were a blast. I got 6,110 nodes expanded for trickySearch and 414 nodes expanded on tinySearch (using the AStarFoodSearchAgent).
(27 Nov '11, 03:25) Tom Chappell Tom%20Chappell's gravatar image

I'd say your heuristic function is overfit to that one particular maze ;)


answered 31 Oct '11, 10:26

rhasarub's gravatar image


:D Actually, that might be partly true... It would work really well for similar mazes, those for whom the manhattan distance is a huge under-measurement due to the presence of long and narrow dead-end corridors...
(31 Oct '11, 10:54) aroberge aroberge's gravatar image

Here is a graph of the costs along the optimal path in trickySearch, with the estimated remaining cost (heuristic) stacked above the computed cost (which is of course linear). The heuristic is the aforementioned minimum spanning tree (MST) length + cost to the closest food.

Things to note are:

  • the sum is monotonically non-decreasing (consistency)
  • it never goes above the optimal path cost of 60 (admissibility); this is implied by consistency and the fact that the heuristic is 0 in the goal state
  • increments of more than one unit (at steps 3 and 9) correspond to the heuristic value increasing despite the fact we are one step closer to the goal. This is actually a good thing, it means that the heuristic comes closer to the actual remaining cost.

stacked costs

Of course the graph doesn't prove anything. To prove consistency (or at least, to convince myself), this is my reasoning:

  • if in the last move pacman doesn't eat a food, the heuristic can decrease by at most one (the MST stays the same and the distance to the closest food decrease by at most one).
  • if pacman eats a food that is a leaf of the MST, the heuristic decrease by one (since the length of the removed edge of the MST is equal to the new distance to the closest food, which was 1 in the previous step)
  • if the eaten food (F) is not a leaf, let n be the number of neighbors of the eaten food in the MST. So you remove n edges from the MST and have to add n-1 new edges back (since the MST is a tree, there is no loop, so you now have to reconnect n components, needing n-1 new edges). For any edge you add, say between components A and B, with length d(A,B), you have the following property: d(A,B) >= d(A,F) and d(A,B) >= d(B,F). That follows from the property of the Minimum Spanning Tree: if you had d(A,B) < d(A,F), then the AF edge wouldn't have been part of the MST in the first place, since a smaller spanning tree would have been possible by replacing the AF edge by that other edge between A and B. By putting all the inequalities together, we can deduce that the length of the new minimum spanning tree cannot decrease by more than the length of the smallest edge leading to F, which is compensated by the new distance to the closest food like in the previous case. Again, the heuristic cannot decrease by more than 1, which was the distance to the closest food in the previous step.

answered 17 Jan '12, 19:13

ibatugow's gravatar image


edited 17 Jan '12, 19:17

@gbayliss Stanford course downloads are on the course schedule here but already the lecture 1 link is busted. @aroberge Can you offer any tips for installing cs221 code and Python - was it easy to get working?


answered 16 Oct '11, 09:25

martinhumby's gravatar image


edited 16 Oct '11, 09:26

Python is extremely easy to install. If you have a Mac or a Linux box, it should be there already. If not, head to python.org and follow the links. As for "installing" the code, you simply have to download it, unzip it somewhere. Simply typing "python a_program.py" will run it - no installation step needed.
(16 Oct '11, 09:37) aroberge aroberge's gravatar image
I should have clarified what I meant about installing the code: I was referring to the code samples for the assignment - not Python itself.
(18 Oct '11, 11:10) aroberge aroberge's gravatar image
Thanks for your help, sorry not replying earlier. Loaded pacman under Ubuntu on VirtualBox. Great stuff but going to find getting to grips with the Python code hard - untyped variables makes understanding harder I think.
(18 Oct '11, 19:12) martinhumby martinhumby's gravatar image

I have a similar issue with Q4, my implementation of a-star seems to find the correct solution much faster than stated in the problem. With the null heuristic, my a-star finds the best solution in 435 nodes when they say 549.


answered 16 Oct '11, 20:11

Benoit%20Ambry's gravatar image

Benoit Ambry

edited 16 Oct '11, 20:13

For me, it's 538 nodes expanded - much closer to theirs. I can see a difference in a few nodes, given a choice of "left" vs "right" branch for choosing successors, but I am puzzled as to how yours is so much lower. In the case I wrote about, it's all due to a "clever" choice of heuristics - where I get at least an order of magnitude difference better than what could be expected...
(16 Oct '11, 20:25) aroberge aroberge's gravatar image
No, I have a bug, that is clear. I think it is missing some of the branches and it finds the proper solution by luck. The null heuristic always returns 0. I found actually, I wrote f(n) = h(n) instead of f(n) = g(n) + h(n). now I have 538!
(16 Oct '11, 20:35) Benoit Ambry Benoit%20Ambry's gravatar image
If you are like me, you may find it useful to include a check like: . if h_cost - new_h_cost > successor[2]: . print "consistency problem", h_cost, new_h_cost, successor[0] in your A-star code. This helped me identify some errors in my heuristic functions.
(16 Oct '11, 20:41) aroberge aroberge's gravatar image
Yeah I have that already, I'm on Q6 and a bad heuristic can really take the a-star algo down.
(16 Oct '11, 20:44) Benoit Ambry Benoit%20Ambry's gravatar image
Huh, that's funny that you guys are both getting 538 nodes expanded on this one. I got 549 nodes expanded with the manhattanHeuristic, the same as they predicted.
(27 Nov '11, 03:36) Tom Chappell Tom%20Chappell's gravatar image

I have had a few seemingly ok heuristics for Q7 - one that finds the optimal solution with 10849 expanded nodes, one that finds an almost optimal solution in 7389 expanded nodes. (The heuristics are taking topology of the maze into account)

However, on mediumSearch, the only solutions I could find before my computer melted (rather, ran out of memory) were clearly suboptimal solutions (pacmans oscillating left and right in the maze, eating a few dots on the rigth, turning around, nibbling on the left and back again) that were found in less than 20'000 expanded notes. The heuristics were not admissable for those.

Question: Has anyone found a heuristic that solves mediumSearch optimally and finishes in finite time / memory? I have an idea for a solution, but that would require a totally different solution state. I have already spent way too much time on this heuristic and would like to know if there's hope to actually solve it.


answered 31 Oct '11, 05:19

jcfischer's gravatar image


So I have a heuristic that works in all mazes but mediumSearch and bigSearch. (trickySearch with optimal solution in 9615 expanded nodes). Would be interesting to hear from others how they are faring. I suspect that my heuristic would solve mediumSearch, but I haven't been able to run it to completion.
(31 Oct '11, 06:00) jcfischer jcfischer's gravatar image
I have run mediumSearch with my heuristic and it didn't complete before it ate up 6 GB of memory...
(31 Oct '11, 11:27) jcfischer jcfischer's gravatar image
found a really good article about heuristics for A* search and how it influences the speed and accuracy of the search: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
(01 Nov '11, 12:47) jcfischer jcfischer's gravatar image

Mine does Q7 with 5893 nodes expanded... What are other peoples' results? (Mine completes in 1.2 seconds) I have Q4 as 547 nodes expanded with a "total cost of 210".

@aroberge I'm interested in your check for consistency... What is h_cost and what is new_h_cost?


answered 27 Nov '11, 01:34

bnsh's gravatar image


Actually... I think I see. So, h_cost is the heuristic of the current position, and new_h_cost must be the heuristic for the successor... I am curious if my heuristic for Q7 is inconsistent or not, given how easy it was to get 5893 as an answer. More later.
(27 Nov '11, 01:41) bnsh bnsh's gravatar image
Yep! Sure enough! Consistency problems! Damnit! hehe...
(27 Nov '11, 01:43) bnsh bnsh's gravatar image
For Q7, I got: 6,110 nodes expanded, total cost 60 (trickySearch) 414 nodes expanded, total cost 27 (tinySearch) For Q4, I got: 549 nodes expanded, total cost 210 (I've got the heuristic consistency check in my aStarSearch)
(27 Nov '11, 04:14) Tom Chappell Tom%20Chappell's gravatar image
Q7: (tricky search) 60 cost, 215 expanded in 0.1 seconds. Consistency is guarantied by heuristic construction. However, I've inserted code to check for consistency on each step. No warnings so far. tinySearch - 27 cost, 52 expanded. smallSearch - 34 cost, 57 expanded. Heuristic is O(n^3), where n is a number of food dots.
(27 Nov '11, 04:33) red75prim red75prim's gravatar image
In Q7 my best score in trickySearch is: Path found with total cost of 60 in 1.6 seconds Search nodes expanded: 1130 @red75prim I'm interested in what heuristic you used. Could we contact by email? (It should appear in my profile)
(04 Jan '12, 17:47) maacruz maacruz's gravatar image
@maacruz, I can't see your email. However, I can give a hint: consider the length of minimum spanning tree for remaining food dots. BTW, I implemented slightly different priority queue to get 215 expanded nodes. If program uses util.PriorityQueue, then it expands 255 nodes.
(05 Jan '12, 03:52) red75prim red75prim's gravatar image
@red75prim: Hey, I did the same thing ! Length of minimumum spanning tree (using maze distances) + distance to closest food. 247 nodes expanded with the stock util.PriorityQueue in 0.1 s. I used Dijkstra and a cache to speed up the calculations.
(05 Jan '12, 06:19) ibatugow ibatugow's gravatar image
@ibatugow. Cache, yes, but I was too lazy to implement Dijkstra's algo... [Staring at source code] Well, yes, it's Dijkstra (BFS + tuned getSuccessors).
(05 Jan '12, 07:29) red75prim red75prim's gravatar image
Thanks! But I think it is an inconsistent heuristic (I can think of one such a tree where you remove a node and the resulting total length then is greater), or I'm not making the right approach (my implementation is inconsistent). My email is maacruz in gmail.
(16 Jan '12, 18:38) maacruz maacruz's gravatar image
Looking back... With my first approach for Q7, TrickySearch I got: 5380 nodes expanded, total path cost 60, in 1.8 seconds A solution with 215 nodes expanded is pretty impressive. I am also curious about the approach taken here.
(16 Jan '12, 21:36) egoots egoots's gravatar image
Finally got it. Needed a small trick (which I had used in my previous heuristic) with packman to solve the inconsistency. 255 nodes expanded in trickySearch in 1.4 seconds (completely unoptimized although I cache things)
(17 Jan '12, 18:38) maacruz maacruz's gravatar image
maacruz: could you email me? myusername at gmail dot com
(17 Jan '12, 18:42) aroberge aroberge's gravatar image
Anyone have pointers on how to actually implement the MST based on a maze?
(07 Feb '13, 19:45) AstarC AstarC's gravatar image

Thanks! But I think it is an inconsistent heuristic (I can think of one such a tree where you remove a node and the resulting total length then is greater), or I'm not making the right approach (my implementation is inconsistent). My email is maacruz in gmail.


answered 16 Jan '12, 18:38

maacruz's gravatar image


Yes, the heuristic value can increase, but what the consistency condition says is that the (cost up to now + heuristic value) cannot decrease. In other words, the estimated remaining cost cannot decrease faster than the computed cost increase. It doesn't preclude the heuristic function to increase, as long as it stays admissible (i.e., not larger than the remaining optimal cost).
(17 Jan '12, 05:08) ibatugow ibatugow's gravatar image
Your answer
toggle preview

Follow this Question via Email

Once you sign in you will be able to subscribe for any updates here

Q&A Editor Basics

  • to upload an image into your question or answer hit
  • to create bulleted or numbered lists hit or
  • to add a title or header hit
  • to section your text hit
  • to make a link clickable, surround it with <a> and </a> (for example, <a>www.google.com</a>)
  • basic HTML tags are also supported (for those who know a bit of HTML)
  • To insert an EQUATION you can use LaTeX. (backslash \ has to be escaped, so in your LaTeX code you have to replace \ with \\). You can see more examples and info here