Pacman result for Q7 too good to be true?

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

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.

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.

@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?

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.

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.

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?

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.