Problems and Search

Problem solving involves:

• problem definition -- detailed specifications of inputs and what constitutes an acceptable solution;
• problem analysis;
• knowledge representation;
• problem solving -- selection of best techniques.

Problem Definition

In order to solve the problem play a game, which is restricted to two person table or board games, a topic which was fully discussed in the last year's course, we require the rules of the game and the targets for winning as well as a means of representing positions in the game. The opening position can be defined as the initial state and a winning position as a goal state, there can be more than one. legal moves allow for transfer from initial state to other states leading to the goal state. However the rules are far to copious in most games especially chess where they exceed the number of particles in the universe. Thus the rules cannot in general be supplied accurately and computer programs cannot easily handle them. The storage also presents another problem but searching can be achieved by hashing.

The number of rules that are used must be minimised and the set can be produced by expressing each rule in as general a form as possible. The representation of games in this way leads to a state space representation and it is natural for well organised games with some structure. This representation allows for the formal definition of a problem which necessitates the movement from a set of initial positions to one of a set of target positions. It means that the solution involves using known techniques and a systematic search. This is quite a common method in AI.

• Well organised problems (e.g. games) can be described as a set of rules.
• Rules can be generalised and represented as a state space representation:
• formal definition.
• move from initial states to one of a set of target positions.
• move is achieved via a systematic search.

Searching

There are 2 basic ways to perform a search:

• Blind search -- can only move according to position in search.
• Heuristic search -- use domain-specific information to decide where to search next.

Blind Search Depth-First Search

1. Set L to be a list of the initial nodes in the problem.
2. If L is empty, fail otherwise pick the first node n from L
3. If n is a goal state, quit and return path from initial node.
4. Otherwise remove n from L and add to the front of L all of n's children. Label each child with its path from initial node. Return to 2.

Note: All numbers in Fig 1 refer to order visited in search.

Breadth-First Search

1. Set L to be a list of the initial nodes in the problem.
2. If L is empty, fail otherwise pick the first node n from L
3. If n is a goal state, quit and return path from initial node.
4. Otherwise remove n from L and add to the end of L all of n's children. Label each child with its path from initial node. Return to 2.

Note: All numbers in Fig 1 refer to order visited in search.