- Categories of problems: Certain-world (rule-governed and we know the actions and the effects) vs Uncertain-world (stochastic, we do not know its nature and actions can have multiple causes)
- All problems in AI needs: We need to represent the problem (agent thinking)→ searching the solution (agent explore the space of possibilities)
- If we look at networks it is all about the representation as well, cats and dogs : we want good prediction, training allows to minimize your errors
- Search landscapes shows, if your error is much it will be higher and vice versa → can we reach the lowest point?
- The 15 and 8 puzzle: the mission is to set the numbers for goal state by changing the location of the square one by one → there are 16! and 9! states that we can try
- How might an agent solve 8-puzzle? : 4 different possibilities, moving up-down-left-right
- Can we solve with in naïve brute force? start initial state → goal state (apply the move operators), might work but wastefully because we will revisit the same game states
- Option 1: Bread-first reach → we look states in the each of the tree
- Open list: we need to explore vs Close list: we already explore
- Why? It always find the shortest → we consider one level in one time (in horizontal level)
- Problematic: when branching factor (b) is high like in chess (which the possibilities will be very high in chess)
- Option 2: Depth-first search → we are looking down (in vertical level)
- Preferable, when solution path is long
- Miss: the short path
SUMMARY
- How can we solve 8 puzzle?
- Specify some way to represent the problem: representing different states of the problem that we need to consider
- Determine operators: moving like the actions and this allows to understand the strategies
- Determine search strategy: by using operators for initial → goal state (depends on the problem)