Author: Heiner Marxen
Date: 15:12:48 03/11/99
Some time ago, when I listened to a discussion of evaluating
positions vs. evaluating moves (or pathes), I started to
realize that there may be real problems with the usual way
to evaluate positions at the tips of the search tree and
backing them up to the root moves.
Clearly, evaluation of the path (leading to a position)
_must_not_ go into the value of the position, at least with
respect to the transposition table (TT). [For simplicity I
will omit complications with draw by repetition or the
50-move rule.]
In principal, I feel it is the right thing to evaluate
positions, because this is the way game theory defines
mini-max and justifies alpha-beta.
As an example let's assume white is to move, material is
balanced, and white can immediately take a (hung) pawn (with
a rook, say) and really win the pawn. Say, we do a 9-ply
search, and two moves come up with an eval of +1. One is
the pawn eater, and the other is a Q-move checking the black
king. That second move is the problem (my opinion): the
search sees a lot of king hunting with check moves where
at the different depths the Q can continue to issue yet
another check, or the rook could now eat the pawn. So, both
moves come up with the same eval for the same reason: they
both win a pawn (the same pawn).
Let's further assume, for some reason, the Q-move is chosen
(e.g. because searched first). Its value indicates that
white will reach a position with value +1. The black king
moves out of check, and now white is facing a position
essentially the same as 2 plies before. Again, white
selects the Q-move etc.
I.e. the search finds white can force to win a pawn, but
does not really make progress towards that win.
The danger is that eventually black may make some progress
such that the pawn eating is not possible, any more, since
the search now can see that black would win by a forced
mate (say).
Such a problem with making progress has already come up with
forced mates (IIRC Bob Hyatt reported some program to
continue with threatening mate in 2). That is easily solved
by forcing the search to seek for a shorter mate the next
time, thus making progress.
Shouldn't we try to make some progress in the general case,
not just for forced mates?
What is the state of the art with this?
Does it happen, at all, in real games?
Or am I way off, and this is not a problem, at all?
Or is it solved, already?
Another view: We have two equally good best moves, along
with their PVs (when searched first), one of which wins a
pawn in ply 1, and confirms this win with a 8-ply search,
while the other PV does 8 plies of something, followed by
winning a pawn, and confirmes this win with a quiescence
search, only. As a human I would clearly take the pawn,
first. Intuitively I'd say the program should do so, also,
because it is more "sure" about it.
eval
^
+1 + * * * * * * * * * taking the pawn, first
|
0 *------------------
1 2 3 4 5 6 7 8 9 depth
eval
^
+1 + * hunting the king, first
|
0 *-*-*-*-*-*-*-*-*--
1 2 3 4 5 6 7 8 9 depth
Thinking more about it, I occurs to me that iterative
deepening, together with a TT (both are pretty standard),
may solve the problem, as shown above, since a 1-ply search
would prefer the pawn eater and store it as "best move" into
the TT, and in the further searches start with this move.
May be, that is enough, already. Dunno.
Opinions?
Heiner
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.