State Space

• I think State Space is a crucial concept for AI.
• The problem you're trying to solve is broken up into a series of discrete states.
• Not all problems can be described this way, but many can, and all can be approximated this way.
• You also describe the transitions between states. How do you go from one to another.
• You frequently have start and goal states.
• The problem then becomes a question of search.
• How can you move from the start to the goal.
• For example, how can you describe a maze as a state space?
• How can you search to find a path from the start to the goal.
• From the graph lecture, you can use Depth First Search or Breadth First Search.
• Also note that the size and shape of the state space tells you a lot about what to do.
• If it is huge, you can't use exhaustive techniques, unless it's reqular.
• How would you describe a tic-tac-toe game in state space?