Motto: Further search and Games
Assignment 3.1
Solve the hero/sidekick problem using a breadth-first search.

Does it find a solution path which is
shorter than the one by depth-first search (with tokens)?
It should be, or at least no longer, or something is wrong.
Assignment 3.2
Find out how many positions are being evaluated/tested using depth-first and breadth-first search.
The BFS should evaluate many more solutions than the DFS. You can count them by
using the visitation list.
Assignment 3.3∗
Devise a heuristic for the hero/sidekick problem and use a best-first search or an A∗ algorithm to
solve it. Evaluate how many positions you test using this heuristic. Is it better than depth-first
search or breadth-first search?
It is not obvious how to devise a heuristic for the hero/sidekick problem, as this has many
cul-de-sacs. However, the number of correctly transferred travellers can be used, or else,
you could experiment with a higher weight for heroes or sidekicks to see whether it can
help to consider one more critical for the evaluation of “distance” to the goal state.
For the 6 coins problem, instead, this is easy to do, namely closeness to target solution.
Assignment 3.4∗
Solve the Nim game, this time write a minimax algorithm for this purpose (once you covered the
principles in the lecture