Computer Chess Club Archives


Search

Terms

Messages

Subject: quiescence search / horizon question

Author: Andrew Shapira

Date: 09:01:26 08/26/05


Summary: People sometimes say that one uses a quiescence search to avoid horizon
problems.  But a quiescence search alone will not do it.  I am looking for some
guidance from the experts.

Suppose we have the following position P1, with white (in capital letters)
to move.

  . . . . . . . k
  . . . . . . . .
  . . . . . . . .
  p p . p p b . .
  . . . . . . R .
  . . . . . . . K
  P P . P P . . .
  . . . . . . . .

In the line kh4 bxr kxr, white has an easy win, and white probably can win
easily if black replies to kh4 with any move other than bxr.

Now suppose that a computer is playing white.  The computer uses some standard
full width alpha-beta search algorithm with a quiescence search.  Suppose that
the position P1 above is reached in the alpha-beta algorithm with 1 ply
remaining in the alpha-beta search, i.e., white makes a move and then goes to
quiescence search.

So, white sees:
  full-width search:
    a4
      quiescence search:
        bxa4
        side to move (white) has no captures; stop the quiescence search
        evalation is +1 (say we're using a material-only static evaluation)
  full-width search, continued:
    kh4
      quiescence search:
        bxr
        kxr
        side to move (white) has no captures; stop the quiescence search
        evaluation is 0

It'll evaluate the position as +1, and think the best move is one of the pawn
moves that defers the loss of the rook, e.g., a4.  This evaluation is not what
we want.  If the computer only has time for the search described above, it will
actually play a4; then black will recapture; white will then hang another pawn,
and so on, eventually losing.  In less extreme cases it will simply misevaluate
the position, which could still be a catastrophe as it may make a move at a
higher level that avoids this position because it does not realize that it wins.

Is there a standard solution for getting the correct evaluation?  (Getting a
deeper search begs the question of what to do in this situation because this
situation can arise after any number of search levels.)

I can imagine that a static exchange evaluator might find this, but this is
unclear to me since it is white's move and the static exchange evaluator would
see no captures that could be made by white.


-A




This page took 0.03 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.