# Incorrect node expansion in game board with A* search

I have the following game board below, and we're using A* search to find the optimal path from the agent to the key. There are 8 directions. Up, down, left, right have a cost of 1, and diagonal directions have cost 3. We will be using a priority queue with function $$f(v) = g(v) + h(v)$$ where $$g(v)$$ is the backwards cost from the goal through the given edges and up to the vertex v while $$h(v)$$ is the optimal least cost distance from v to the goal node.

So I calculated the f(s) for the different states, assuming no prior edges specified:

And then I started the search and these are the steps I took: expand C: (CD,3), (CE,3), (CF,3), (CA,5), (CB,5)

expand CD: (CDF,3),(CE,3), (CF,3), (CA,5), (CB,5), (CDB,5)

expand CDF: (CDFH,3), (CE,3), (CF,3), (CA,5), (CB,5), (CDB,5), (CDFG,6)

expand CDFH: (CE,3), (CF,3), (CA,5), (CB,5), (CDB,5), (CDFG,6)

So I only expanded, C,D,F,H. I got the correct answer for the optimal path, but not the correct answer for nodes expanded, which is supposed to be C, D, E, F, G, H. What am I doing wrong?

• In the first iteration of $A*$ (and basically many other state-space search algorithms), you will only add to the frontier the nodes reachable from your current node, but $H$ and $G$ are not reachable with a single action from $C$ (if I interpret correctly your state-space), so I'm not sure how you calculated $f(n)$ for those (in the table). So, you should probably try to think about this issue before proceeding. I would also suggest that you draw your state space as a graph, so that to avoid this type of confusion again.
– nbro
Feb 11 '21 at 0:49
• those f(s) values are just there for the question, I dont use those exact values for the queue. are my expansion steps right? Feb 11 '21 at 2:49
• If I understand correctly, diagonal moves cost 3. So the first expand: CF=3+1, CB=3+3 Feb 11 '21 at 6:22
• @Manaal As I said above, it looks like you didn't really understand how A* (or any other state-space search algorithm) expands the nodes or adds them to the frontier, so I would suggest that you do what I said. Draw your state space as a graph, where only reachable nodes are connected by an edge (so no edge between C and H, e.g.). Moreover, someone also pointed out above that you didn't calculate correctly f(n) for several nodes. I would suggest that you delete this post, do what I suggested, try to solve the problem again, then ask another question, if you still have a question.
– nbro
Feb 11 '21 at 12:27