Uplaod the answer as a pdf. The slides might help.
Part 1: State Spaces
1.1) [1pt] You will need to create a small problem to work from (i.e., find an initial state that is only a few moves away from a goal state).
Luckily, for the 8-puzzle this is straightforward. Start from the goal state and move tiles around several times to “mix up” the board
For example (See attached [email protected])
Now you give it a try. Start from the goal state and move the tiles 3 times to create an initial state.
1.2) [4pts] Now draw out the search space starting from the initial state you created in (1.1). Draw 4 levels of the tree (we need a limit since the tree would otherwise be infinite in size), meaning the root node (initial state) and 3 levels of successor states. When considering successor states, evaluate moves (and writing them left-to-right) in the following order:
- Move a tile up into the blank space
- Move a tile down into the blank space
- Move a tile left into the blank space
- Move a tile right into the blank space
Indicate in some way which nodes are goal states and which nodes have further successors (which you won’t explore because they are past 4 levels).
The idea here is to reproduce something like the trees demonstrated on the slides (e.g., slide 11 in Uninformed Search).
I highly recommend putting the first set of successors (2nd level of tree) on separate pages, so you have enough room to finish the tree!
Part 2: Uninformed Search
Now we move on to some actual algorithms.
2.1) [4pts] Using your initial state from Part 1, show how Breadth First Search (BFS) would explore states.
Show your work in detail, including the contents of the Open and Closed sets after each iteration.
Because the open set will grow quite large, you may abbreviate by leaving out parts of the open and closed sets which don’t change. However, make sure it is clear what is leaving the open set and what enters the open/closed sets (and where!).
Hint: As you work through the BFS operation, trace which states it explores on your tree from Part 1. Is it following the pattern you expect? If not, maybe you’ve made a mistake?
If you find yourself needing to do more than 10 iterations to find a goal state, then after the 10th iteration, you may simply report which state is visited, rather than the entire contents of the Open & Closed sets.
2.2) [0.5pts] If you had used Uniform Cost Search (UCS) instead of BFS above, how would your results change?
2.3) [4pts] Now repeat (2.1) but using Depth-Limited Search (DLS) with a depth limit of 4.
Remember that DLS needs to know the depth in the search tree of each state (number of actions to reach), so you will need to include that extra information in your open set. (The formatting is up to you, but you could use the UCS example on the slides for inspiration.)
Hint: When you generate successor (children) states, how do you know what their depth is? Can you calculate their depth if you know the predecessor (parent) depth?
2.4) [4pts] Again, repeat (2.1) using Iterative Deepening Search (IDS).
Keep in mind, IDS runs DLS multiple times with increasing depth limits, so this problem will be somewhat like repeating (2.3) multiple times. Make sure it is clear each time where the depth limit changes (and a new run of DLS starts).
Hint: You may be able to re-use (copy-paste) many pieces of your work from (2.3) to save time.
Part 3: Informed Search
3.1) [6pts] Finally, repeat (2.1) using A* search using the “misplaced tiles” heuristic (see slide 25).
Note, as with DLS, A* requires tracking extra information about a state in order to operate. At a minimum, you will need to track the total estimated path cost for each node ( f ). But I highly recommend tracking the path cost so far ( g ) as well, as it will make you’re job significantly easier.
Hint: The path cost so far ( g ) has a very strong relationship with the depth from DLS…
