Horizon Effects in modern chess programs?
Steve McCracken
The literature from the 70's seems to make a big deal
about the horizon effect. Apparently game positions
occurred frequently where a search to only 5 ply or so
could be fooled by the horizon effect.
However, I have noticed that it is hard to construct a
meaningful chess position from which a search to 8-10+
ply would be fooled by the horizon effect. Eventually
the value of the material "thrown away" to delay the
inevitable attack would exceed the loss sustained in the
attack, and the search will find the correct move.
However, there are other positions that are susceptible
to variations of the classical horizon effect. Further,
these positions, though rare, do not have the nice
property that eventually material "thrown away" will
exceed material lost.
I classify these positions into two groups:
1) the winner has an inevitable attack
2) the winner has an attack that is not inevitable.
In each group, the loser distracts his opponent with moves
that do not necessarily throw away material, but the
opponent's attack is still pushed over the horizon. While
both are good examples of Jansen "problematic positions"
where the move that looks best with a shallow search suddenly
becomes bad when we look deeper, I refer to them as a kind of
horizon effect because in principle we have enough information
with the limited search depth to suspect that the attack will
succeed.
Although I have had difficulty constructing specific examples,
this is what they might look like:
(1) Black has an inevitable attack that might take a few
quiet moves to develop. However, the search finds that if
white moves a piece to "chase" a valuable black piece around
the board for a few moves, the attack is pushed over the
horizon. So white makes the "chase" move thinking that it
refutes the attack, even if it leaves white with a worse position.
(2) Black has an attack that might take a few quiet moves
to develop. White can refute the attack as long as he moves a
critical defender piece into place right now. However, the
search finds that if white moves the defender to "chase" a black
piece around the board for a few moves, white's defensive
piece ends up in a good position according to the evaluation
function (or maybe white can even win some material along
this line). But now white's piece isn't there to stop black's
attack, and the search will reach its horizon before it
discovers this. So white makes the "chase" move.
Moreover, the "attacks" mentioned above do not necessarily
have to be sequences that end in a capture. They could be,
for instance, be moving a knight to an outpost over several
moves.
My questions to all of you experienced chess programmers are:
a) Do you think any of these horizon effects are responsible
for many errors in modern programs that search to 8 ply
and more? It seems like positions that will fool a program
in this way become more and more rare as search depth increases.
b) Would horizon effect positions that occur far enough down
on a branch to return the wrong value be likely to affect
the move chosen at the top of the tree?
c) Do you think the errors caused by these effects are small
in comparison with errors introduced with null move, quiescence
search, inappropriate position evaluation, etc.? If not, it
might be worthwhile to expand the standard definition of
quiescence (whatever that is) to check whether an attack that
was refuted in a different part of the tree might now succeed.
I'm sure these thoughts are not new, but I'm not sure how they
fit into the context of today's programs.
Thanks,
Steve McCracken
sam...@psu.edu
SheppardCo
> a) Do you think any of these horizon effects are responsible
> for many errors in modern programs that search to 8 ply
> and more? It seems like positions that will fool a program
> in this way become more and more rare as search depth increases.
Yes, such errors are possible, and they do occur, especially
versus human players that have sufficient strength to steer
the game into that direction.
> b) Would horizon effect positions that occur far enough down
> on a branch to return the wrong value be likely to affect
> the move chosen at the top of the tree?
The rule in computer chess is that if something bad is possible,
then it certainly occurs. The reason this rule is true: an
exhaustive search _seeks_out_ positions where the backed up
minimax score is as high as possible, and this involves maximizing
the *sum* of two factors: actual_value + random_error. Exhaustive
search is just as capable of maximizing random_error as it is of
maximizing actual_value.
In brief: yes, this type of problem occurs all the time.
> c) Do you think the errors caused by these effects are small
> in comparison with errors introduced with null move, quiescence
> search, inappropriate position evaluation, etc.? If not, it
> might be worthwhile to expand the standard definition of
> quiescence (whatever that is) to check whether an attack that
> was refuted in a different part of the tree might now succeed.
Exhasutive searches allow only one type of error: evaluation errors.
When you add in null-move searches, you have another type of
error: relying on the null move when there is a zugzwang.
The only known reliable remedy for evaluation errors is to search
more deeply. It is possible to construct more elaborate evaluation
functions, but complexity increases the size of the random_error term.
It is probably not worthwhile to expand the definitions of quiescence
that are currently in use. Quiescence searching is called "searching,"
but is is perhaps better thought of as the evaluation function, since
the values it returns to the full-width searcher are passed into a pure
minimax (alpha-beta) algorithm. Basically: all errors that a chess program
ever commits are attributable to quiescence searching, and hence:
let's think about the quiescence search as "the evaluation function."
So what is the quiescence search supposed to do? It must decide
whether a position has value >alpha. So the quiescence search makes
an error when it says that the value is > alpha when the value is <=
alpha, or vice-versa.
In chess, there are two types of errors: material errors and positional
errors, for lack of better terms. Think of these as "losing moves" and
"dubious moves." What I am trying to say is that it is OK to make
positional
errors, but not OK to lose material. So quiescence searching should
avoid material errors, and if it misassesses a position by a few
centipawns,
then so what?
And thus did quiescence searching evolve into the captures, checks, and
promotions-only search that it is today. We find very few reasons to add
moves other than these to the search, because we want as many positions
as possible to be handled by the full-width, non-error-prone search.
A long response, but I hope it covers the key design choices in an
understandable way. If you want to extend the definition of quiescence
by including other measures, you have to watch out for a few pitfalls:
1) The speed-penalty of collecting information needed to control the
size of the quiescence tree. (See the SEE vs MVV/LVA debate.)
2) Errors introduced in selectively searching defender moves.
3) Probable search explosions.
Of course, if you manage to solve these problems, you are on to
something big!
Warm Regards
Brian Sheppard
Sheppards Company markets Maven, the premier program for
lovers of Scrabble-brand crossword game. For more info,
please e-mail Shepp...@aol.com. Thank-you.
David Flude
>"And thus did quiescence searching evolve into the captures, checks, and
>promotions-only search that it is today. We find very few reasons to add
>moves other than these to the search, because we want as many positions
>as possible to be handled by the full-width, non-error-prone search."
>My question is 'Do programmers exclude pins and Xrays in quiescence searching'
The point is that there would be very relatively few of these to
include in the quiescence search but whenever one occurs there could
be a major error in the evaluation of the position.
SheppardCo
searching'
Sometimes I hear rumors that certain programs include
tactical measures other than captures, selected checks and
pawn promotions.
A typical method for including such moves is to use "horizon
extension", which means that when the opponent has a big threat
and the search is at the terminal ply, then the side to move is not
allowed to stand pat, but must make a move to see if he can
evade the problem.
Technically, this is not part of the quiescence search, since
it takes place within the full-width portion of the tree.
Approaches that try to generate selective tactical moves within
the quiescence search run into problems because the opponent's
best defensive replies are not usually quiescence search moves.
Thus, proper technique requires a full-width reply for the opponent,
with accompanying big problems in search control.
> The point is that there would be very relatively few of these to
> include in the quiescence search but whenever one occurs there could
> be a major error in the evaluation of the position.
My gut feel is that it is a whole lot better to exclude such
measures, the point being to get as many positions as
possible into the full-width search.
Warm regards
Brian Sheppard