In this topic, we will formalize informed search techniques by defining and applying heuristics to guide our search.
In the Tic-Tac-Toe example, we implemented a greedy algorithm that first focused on winning, and then focused on not losing. When it comes to winning the game immediately, the greedy algorithm is optimal, because there is never a better step than winning the game. When it comes to not losing, it matters how we avoid the loss. Our algorithm simply chose a random safe move without considering how many winning opportunities we have created.
Breadth First Search and Depth First Search are uninform, because they consider all possible states in the game. An informed search explores the space of available states intelligently.