State Space Search

State Space Representation in Artificial Intelligence

Problem Statement: Explain State Splace Reseach in AI with example

To find solution to any problem the foremost condition is that it has to be precisely defined or represented. By defining it precisely means to present an abstract problem in real workable states that are really understood. These states are then operated by some set of operators and finally the solution is obtained. The decision of which operator is to be applied is taken by the control strategy used. There are two ways in which the AI problem can be represented.

State Space Representation
Problem Reduction

State Space Representation

State Space Representation consist of defining an INITIAL State (from where to start), the GOAL State (The destination) and then we follow certain set of sequence of steps (called States). Let’s define each of them separately.

State: AI problem can be represented as a well formed set of possible states. State can be Initial State i.e. starting point, Goal State i.e. destination point and various other possible states between them which are formed by applying certain set of rules.

Space: In an AI problem the exhaustive set of all possible states is called space.

Search: In simple words search is a technique which takes the initial state to goal state by applying certain set of valid rules while moving through space of all possible states.

So we can say that to do a search process we need the following.

Initial State
Set of valid Rules
Goal State

So, a set of all possible states for a given problem is known as state space representation of the problem.

For example: In chess game: The initial position of all the pieces on a chess board defines the initial state. The rules of playing chess defines the set of legal rules and Goal state is defined by any possible board position corresponding to checkmate or a draw state. The point to be noted here is that there can be more than one Goal state possible.

State Space Representation of Tic Tac Toe game is shown is the following figure. Starting from the initial state as we move on applying rules of putting X (cross) or O (Zero) we keep on generating the states, hence the set of states all such generated states is called space, unless we reach one of the goal states that can be a win situation or a draw situation. The new state is generated from the earlier one is by applying the a control strategy.

State Space Representation of Tic Tac Toe Game

State space representation are very advantageous in AI problems as the whole state space is given it becomes easy to find the solution path that leads from initial state to goal state. The basic job is to create such algorithms which can search through the problem space and find out the best solution path. Later chapters will discuss about these search procedures and control strategy to move through the space.