Heuristic Search

Uninformed search / Brute force search

"Uninformed search" uses no problem-specific information to guide its search.
An example would be a "brute force" or exhaustive search through all states.
We saw this with depth-first search and breadth-first search.

Uninformed search doesn't scale well to large problems.

Informed search / Heuristic search

"Informed search" means we use some problem-specific information to guide the search.
Instead of systematically searching states in the order in which they present themselves:
We restrict the search by first choosing a branch that is "more likely" to lead to goal.

But how do we know which branch is "more likely"? We don't know where the goal is!
Answer: We don't know which branch. But maybe we can make a decent guess, a lot of the time. We use a "heuristic" to guess what to search next.

Heuristic search gives up the idea of ever doing an exhaustive search.
It gives up the idea of guaranteeing to find the best solution.
Instead we try to do a smart search of a huge space in the limited time available.
Any heuristic can fail.

Xs and Os

Let us consider heuristic search with Xs and Os (Tic-Tac-Toe).

Reduce statespace

First, we will try to use symmetry to reduce the search problem.

We previously established there are at most 9! = 362,880 paths through the game.

Symmetry reduction - Recognise that many states are mirror images of each other and so we don't have to search them separately.
Can rotate or mirror-image a board state to show it is basically the same problem as another state.
There are basically only 3 unique first moves.

See Luger Fig 4.1

Symmetry reduction on 1st level reduces no. of paths to 3 . 8!
Symmetry reduction on 2nd level reduces no. of paths to 12 . 7! = 60,480

Symmetry reduction may require a lot of thought and work by the human. But worth it if it reduces state space.
For Xs and Os, or any 2D board, could write an algorithm to do the symmetry reduction (rotate and mirror).
Might not be board game: e.g. 2D traffic lights junction simulation. Could be rotated.

Heuristic search for Xs and Os

Now, what heuristic can we think of to guide or restrict our search of future moves and counter-moves?

Consider a heuristic of: "Number of winning opportunities (that contain at least one of my pieces)" in each situation.
Always take highest (or if draw, any joint winner).

First move:
The heuristic says to always go for the centre move.
Luger Fig 4.2
This dumps 2/3 of entire statespace after symmetry-reduction (or 8/9 if we consider our original naive search).

2nd move:
There are only actually 2 unique replies the opponent can make:
Luger Fig 4.3
Depending which reply he makes, our heuristic tells us what to do next in each case. Oddly, in both cases, it mightn't be the move you think.
The numbers circled show "Number of winning opportunities (that contain at least one of my pieces)"

Two ways of using the heuristic:

Use it to make the actual move.
Don't search down multiple levels.
Respond to current state by comparing "Number of winning opportunities" among possible immediate moves, and taking that move.
Not AI search at all. Just a solution.
or:

Use it to decide which child to search first.
Use it to order the children and do depth-first etc. searches as before.

Hill-climbing

"Take the state with the highest number of winning opportunities" heuristic is a "Hill-climbing" strategy.
Take the most promising immediate next step, without looking n steps ahead.

Imagine searching for highest point on a curve:

Imagine a landscape like the above, but the machine cannot see it. The machine sees no equation, and no picture.
The machine produces an x value and is told the y value.
It changes x value to try to improve the y value.
Hill-climbing is where we change x to always go uphill, never downhill, until reach a peak.
Imagine a single point (not n points as here).
Pick a random x value, see the y value. Then move it uphill from where it is.
Unless the start point is already (by chance) on the slope of the global optimum, our point will move to a local optimum not the global optimum.
Hill-climbing will not temporarily get into a worse state in order to get into a better one after that.

N-puzzle game

15-puzzle (the most common version of the N-puzzle game)

Solving the 15-puzzle game.

The N-puzzle game.
An example of where we might need to go "downhill".
To get to goal, might need to move some pieces temporarily out of position.
Public domain image from here.

The local optimum problem

Luger Fig 4.4
Large number is best.
We have parent (4) who is better than any of its children (3).
So will stay at parent (4) and miss global optimum (5).

4.2 - Best-first search

Best-first search is a heuristic search.
We need a function to order the states by a heuristic estimate of how good they are or how close to the goal they are. Of course this will just be a guess.
This is called an "evaluation function".
Given such a heuristic evaluation function, best-first search works as follows.

Best-first search.
Image courtesy of Ralph Morelli.

The numbers show the heuristic estimate of the fitness of each state (lowest number best - view it as "distance from goal").
OPEN - current fringe of the search.
CLOSED - states already visited.

Notes:
When B is evaluated, its children E and F seem worse / further from goal (our heuristic got it wrong, on either parent or child, or both).
E and F go into sorted queue. C now has lowest number, so we jump to there.
We jump around the graph. Next state to be evaluated may be at any level.
States actually expanded are in bold.
State O is dead-end. Note heuristic was wrong about O.
When state O is not goal, we turn to next in queue - P.

Morelli is showing the space that exists, not the space the program knows about (which is smaller).
e.g. He shows us K and L and their children, but the program does not know they exist yet.

Q. Why does Morelli have heuristic 3 on goal P? I genuinely do not know. The heuristic can be wrong, but surely it will be 0 on the goal itself.

Q. Show all the paths where the heuristic must be wrong.

We have backtracking when we go down an apparently promising but fruitless path.
Less likely to get stuck in local optimum than if always took best-looking next step (hill-climbing). Eventually some other state probably evaluates as best and we jump to that.

Inaccurate heuristic

The heuristic evaluation function is only a guess. It is bound to be inaccurate on some states.

Note we could get stuck down a path if heuristic very inaccurate.
e.g. Go down a line where heuristic says we are 2 steps from goal forever, no matter how deep we go.

Q. How might you solve this? (How might you compensate for an inaccurate heuristic?)

Designing an evaluation function

Evaluation function f is a heuristic estimate of how good the state is (high f good) / distance to goal (low f good).
The design of heuristic evaluation functions is an empirical problem. Can spend a lot of time designing and re-designing them.
Often no obvious answer. e.g. Write a function that estimates, for any state x in chess, how far that state is from checkmate.