Search Spaces

• Another important concept in determining how to solve a problem is the concept of search space (or a problem space).
• You can figure out the size of your problem (size of the search space) by figuring out how many states your system can be in.
• Solving the problem is then done by changing the state to get to a good state or even the best state.
• Two particularly important states are the start and final states.
• What is the size of the search space for tic-tac-toe? (< 9!)
• How do you move from one state to another in tic-tac-toe?
• What is the size of chess space (< 64!)?
• Can you do exhaustive search in tic-tac-toe? Chess?