AI Problem Solving.! Define the problem as State Space Search.

The steps that are required to build a system to solve a particular problem are:

1. Problem Definition that must include precise specifications of what the initial situation will be as well as what final situations constitute acceptable solutions to the problem.

2. Problem Analysis , this can have immense impact on the appropriateness of varies possible techniques for solving the problem.

3. Selection of the best technique(s) for solving the particular problem.

Define the Problem as State Space Search

Consider the problem of “Playing Chess” . to build a program that could play chess, we have to specify the starting position of the chess board, the rules that define legal moves. And the board position that represent a win. The goal of the winning the game, if possible, must be made explicit.

The starting position can be described by an 8 X 8 array square in which each element square (x,y),(x varying from 1to 8 & y varying from 1 to 8) describes the board position of an appropriate chess coin, the goal is any board position in which the opponent does not have a legal move and his or her “king” is under attack. The legal moves provide the way of getting from initial state of final state.

The legal moves can be described as a set of rules consisting of two parts: A left side that gives the current position and the right side that describes the change to be made to the board position. An example is shown in the following figure.

Current Position

          While pawn at square ( 5 , 2), AND Square ( 5 , 3 ) is empty,  AND Square ( 5 , 4 ). is empty.

Changing Board Position

                                 Move pawn from Square ( 5 , 2 ) to Square ( 5 , 4 ) .

The current position of a coin on the board is its STATE and the set of all possible STATES is STATE SPACE. One or more states where the problem terminates is FINAL STATE or GOAL STATE . The state space representation forms the basis of most of the AI methods. It allows for a formal definition of the problem as the need to convert some given situation into some desired situation using a set of permissible operations. It permits the problem to be solved with the help of known techniques and control strategies to move through the problem space until goal state is found.

Some of the problems that fall within the scope of AI and the kinds of techniques will be useful to solve these problems.

S.No Problems Techniques

1. Chess Hill climbing

2. Water Jug Best – First Search, Branch and Bound

3. 8 – Puzzle A* Search . Depth First Search

4. Traveling Salesman Heuristic Search

5. Missionaries & Cannibals Best – First Search with backtracking

6. Tower of Hanoi Best First Search

7. Monkey and Bananas Breadth First Search , Best First Search

8. Cryprarithemetic Depth First Search

9. Bridge Depth First Search