Advanced Search

Learning Objectives:

Further reading:

Graph search

Like tree search, but with a *visited* list that checks if some state has not been reached before.

Visited list can take a lot of memory

A* search: standard game playing technique:

Two-player Systems

So if the above methods are all standard, the enemy knows them too.

Q1: How can you reason about the enemy reasoning about your reasoning?

Q2: How you do the above faster?

See http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html

There is a common illusion that we first generate a n-ply minmax tree and then apply alpha-beta prune. No, we generate the tree and apply alpha-beta prune at the same time (otherwise, no point).

How effective is alpha-beta pruning? It depends on the order in which children are visited. If children of a node are visited in the worst possible order, it may be that no pruning occurs. For max nodes, we want to visit the best child first so that time is not wasted in the rest of the children exploring worse scenarios. For min nodes, we want to visit the worst child first (from our perspective, not the opponent's.) There are two obvious sources of this information:

When the optimal child is selected at every opportunity, alpha-beta pruning causes all the rest of the children to be pruned away at every other level of the tree; only that one child is explored. This means that on average the tree can searched twice as deeply as before: a huge increase in searching performance.

Stochastic Tree Search

ISAMP (iterative sampling)

This stochastic tree search can be readily adapted to other problem types.

Eg#1: scheduling problems

Eg#2: N-queens with the lurch algorithm. From state "x", pick an out-arc at random. Follow it to some max depth. Restart.

Note: subsequent research found numerous better variants of the at IJCAI'95, AAAI'96, and in 2002.

Q: Why does Isamp work so well. work so well?

Unordered searchers

Strangely, order may not matter. Rather than struggle with lots of tricky decisions,

For example: Stochastic search: randomly fiddle with current solution Local search: . replace random stabs with a little tinkering Some algorithms just do stochastic search (e.g. simulated annealing) while others do both (MAXWALKSAT)

Simulated Annealing

S. Kirkpatrick and C. D. Gelatt and M. P. Vecchi Optimization by Simulated Annealing, Science, Number 4598, 13 May 1983, volume 220, 4598, pages 671680,1983. 

s := s0; e := E(s)                     // Initial state, energy.
sb := s; eb := e                       // Initial "best" solution
k := 0                                 // Energy evaluation count.
WHILE k < kmax and e > emax            // While time remains & not good enough:
  sn := neighbor(s)                   //   Pick some neighbor.
  en := E(sn)                          //   Compute its energy.
  IF    en < eb                        //   Is this a new best?
  THEN  sb := sn; eb := en             //     Yes, save it.
  FI
  IF random() > P(e, en, k/kmax)       //   Should we move to it?
  THEN  s := sn; e := en               //     Yes, change state.
  FI
  k := k + 1                           //   One more evaluation done                        
RETURN sb                              // Return the best solution found.

Note the space requirements for SA: only enough RAM to hold 3 solutions. Very good for old fashioned machines.

But what to us for the probability function "P"? This is standard function: 

FUNCTION P(old,new,t) = e^((old-new)/t)
Which, incidentally, looks like this:

That is, we jump to a worse solution when "random() > P" in two cases:

Note that such crazy jumps let us escape local minima.

MAXWALKSAT

Kautz, H., Selman, B., & Jiang, Y. A general stochastic approach to solving problems with hard and soft constraints. In D. Gu, J. Du and P. Pardalos (Eds.), The satisfiability problem: Theory and applications, 573586. New York, NY, 1997.

State of the art search algorithm. 

FOR i = 1 to max-tries DO
  solution = random assignment  
  FOR j =1 to max-changes DO
    IF    score(solution) > threshold
    THEN  RETURN solution
    FI
    c = random part of solution 
    IF    p < random()
    THEN  change a random setting in c
    ELSE  change setting in c that maximizes score(solution) 
    FI
RETURN failure, best solution found

This is a very successful algorithm. Here's some performance of WALKSAT (a simpler version of MAXWALKSAT) against a complete search

You saw another example in the introduction to this subject. The movie at right shows two AI algorithms t$ solve the "latin's square" problem: i.e. pick an initial pattern, then try to fill in the rest of the square with no two colors on the same row or column.

This stochastic local search kills the latin squares problem (and, incidently, many other problems).

Genetic Algoirthms

GAs = mutate bit-strings

GPs = mutate parse trees of programs

The dream:

Take a herd of variants on a program

GP= mutation of program structure - Special form of GA (genetic algorithms)

GP selection

Cross-over

Single point crossover (One random crossover point)

Two point crossover (Two random crossover points)

Uniform crossover (Probabilistic bit selection)

Mutation: Randomly flip bits

Q: Why Mutate?

Approaches

And why stop at bit strings?

Recommended Settings

All generalities are false. But, just to get you started:

GP as automated invention machines

Koza, John R., Keane, Martin A., and Streeter, Matthew J. 2003c. i What's AI done for me lately? Genetic programming's human-competitive results IEEE Intelligent Systems. Volume 18. Number 3. May/June 2003. Pages 25-31.

Automatic synthesis of computer programs for 21 "human-competitive", previously patented inventions:

Koza lists 36 "human-competitive" results (including the above patents):

  1. The result was patented as an invention in the past,is an improvement over a patented invention,or would qualify today as a patentable new invention.
  2. The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal.
  3. The result is equal to or better than a result that was placed into a database or archive of results maintained by an internationally recognized panel of scientific experts.
  4. The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created.
  5. The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions.
  6. The result is equal to or better than a result that was considered an achievement in its field when it was first discovered.
  7. The result solves a problem of indisputable difficulty in its field.
  8. The result holds its own or wins a regulated competition involving human contestants (in the form of either live human players or human-written computer programs).