As well as a cost associated with each path, there may be a minimum possible distance to the goal. For example consider the following:
T---4----G--4--C /\ | W / \ 5 / 3 5 | 3 / \ | / A---4----H-2--B--4--P
Problem: find the optimum path from A to W
The minimum possible distance from any node to W is the straight line distance to W. We can use this to help the branch and bound algorithm.
Instead of using the cost, use the cost + minimum distance left. This will discourage steps away from the solution.
Some paths may be redundant e.g. A->T->H is a valid path but A-> H has a lower cost and so the former is redundant.
The A* procedure is a branch and bound search with the inclusion of a lower-bound estimate of remaining cost and removal of redundant paths.
In the 8-puzzle problem 8 differently numbered tiles are fitted into 9 spaces on a 3x3 grid. One space has no tile so that any tile adjacent to the empty space can be moved to occupy it by sliding from its original position. For instance, here is an initial and a goal state:
initial state goal state 2 8 1 1 2 3 4 6 4 5 6 7 5 3 7 8
Here are some different heuristic functions:
A solution to the problem may be found by using a best-first search where the heuristic is used to choose which position to search next. (don't forget to exclude loops from the search).
In order to find the optimal solution, branch and bound or A* could be used. In this case the path length is the number of moves so far and the underestimate of distance left could be the heuristic.
Games require different search methods since we are often dealing with an adversary.
A tree in which the nodes denote board configurations, and the branches indicate how one board configuration can be transformed into another by a single move.
An exhaustive search of the game tree for a solution is usually not possible. Need a way to rank board positions. If there is an infallible way to rank board positions then no search is necessary, just choose the move that gives the best position. Unfortunately, this is not possible for the vast majority of games. The answer is to use a board ranking after play has been extended through several levels of move and counter move.
Suppose that board positions can be ranked by a situation analyser to give a single number.
The machine will want to maximise this number for its turn and the opponent will want to minimise it.
The procedure by which the scoring information passes up the game tree is called the MINIMAX procedure,because the score at each node is either the minimum or the maximum of the scores at the nodes immediately below:
O Max(2,1)=2 / \ / \ / \ / \ O2 O1 Min(2,7)=2 Min(8,1)=1 / \ / \ O O O O 2 7 1 8
The numbers in this diagram represent the board ranking. One player tries to get higher numbers while the other tries to get lower numbers.
For each node in the games tree:
If you have an idea that is surely bad, do not take time to see how terrible it is.
Consider the example: It is not necessary to evaluate the branch at the right (with the 8) since the 1 is already lower than the 2 and will not be chosen.
Procedure To perform minimax search with the ALPHA-BETA procedure,