When performing search, an important theoretical question is which states must be expanded by which algorithms. Early
work by Dechter and Pearl showed that all optimal unidirectional algorithms must expand all states with f(s) < C*, where
C* is the optimal solution cost. Note that the theory says nothing about states with f(s) = C*. The app on this
page contains three "games" related to understanding necessary expansions in unidirectional and bidirectional search.
Start by drawing or erasing any obstacles in the map. Then, select a start and goal state for the game.
Next, play the first game -- try to identify a state that, if it were not expanded, A* would not be guaranteed to
find the optimal solution. (That is, a state with f(s) < C*.)
In the second game you will try to identify a similar state for bidirectional search. If you are having trouble
with the second game, you can try the third game -- an alternate version of the second game.