backward thinking & checking your work
john quill taylor
I have a basic question about chess program algorithms.
Let's say you are finishing at some ply on a deep
search. At the end of each ply, do chess programs
"work backwards" to check if the intended line is
really any good? Or do they only work "brute force"
from the original position?
For example, let's say a program settles on a move after
completion of 10-ply, and let's say that the last move
at the END of the 10-ply shown is Rook captures Bishop.
Now, at the *resulting* position at the END of this line,
does the program then analyze this *possible* resultant
position, at least to a certain depth, perhaps 6-ply?
And if it does, and if it finds that the value calculated
during this deeper "extension" of the original search is
actually much lower than the value was at the 10-ply,
does it "back up the intended line" until the value goes
back up (improving the line using the move already found)?
This seems like a simple thing to do before making a move
(if the value never goes up to what was "seen" at 10-ply,
the line could be of course rejected). Does this "backward"
thinking exist in the current chess programs, and if so,
what is this procedure called?
I ask this because often I see a line prepared out to
some deep level, and when I move to the end (or even
near the end) of that line, the value goes way down
(or up) at a simple 30-second search (say 5- or 6-ply).
Why would any MOVE in such a LINE even be considered as
part of the continuation if its "badness" can be detected
in just a few seconds? I know what the horizon effect is,
but this seems much more basic to me, as simple as
"checking your work" in a math problem. It can't "cost"
too much time to run 5- or 6-ply at each possible POSITION
(only 20 positions for a 20-ply LINE) to ensure that the
proposed LINE ITSELF is worthy, can it? Are there really
*that* many possible things going on that the computer has
no time to CHECK THE SOUNDNESS OF THE LINE BEING PROPOSED!?
- jqt -
bruce moreland
>I have a basic question about chess program algorithms.
>
>Let's say you are finishing at some ply on a deep
>search. At the end of each ply, do chess programs
>"work backwards" to check if the intended line is
>really any good? Or do they only work "brute force"
>from the original position?
>
>For example, let's say a program settles on a move after
>completion of 10-ply, and let's say that the last move
>at the END of the 10-ply shown is Rook captures Bishop.
>
>Now, at the *resulting* position at the END of this line,
>does the program then analyze this *possible* resultant
>position, at least to a certain depth, perhaps 6-ply?
>And if it does, and if it finds that the value calculated
>during this deeper "extension" of the original search is
>actually much lower than the value was at the 10-ply,
>does it "back up the intended line" until the value goes
>back up (improving the line using the move already found)?
This has been done, but I don't think people are doing it in general.
The PV is just your best guess about what is going to happen in the
game. There can be mistakes in the PV. If there are mistakes in the
PV, what you hope is that there is a point above the end of the PV,
and below the root move, at which you can change your mind if you need
to, while maintaining all or most of the value of the PV.
If you find that the ending position is evaluated optimistically (you
thought it was good, but actually it is bad), you don't know that the
root move is bad, you just know that a pretty important node got the
wrong evaluation assigned to it. It is possible that you can diverge
prior to getting to this node in the real game, but it's not certain,
maybe you did just shoot yourself.
But if you find that the ending position is evaluated pessimistically,
or accurately, it does not follow that you should have complete
confidence in your whole PV. Because it is possible that the opponent
can deviate at some point as well.
If you want to start second-guessing yourself all up and down the PV,
then what you are doing is the next iteration of the search.
You could use detection of an optimistically evaluated PV terminal
node as a trigger to extend time, which will result in better
performance on that particular position, but it's not known if the
time spent searching that position would typically be spent better
somewhere further on down the line.
>This seems like a simple thing to do before making a move
>(if the value never goes up to what was "seen" at 10-ply,
>the line could be of course rejected). Does this "backward"
>thinking exist in the current chess programs, and if so,
>what is this procedure called?
I think I have heard it called a verification search. Bob Hyatt can
tell you who did it first. Probably Ken Thompson, if I had to guess.
>I ask this because often I see a line prepared out to
>some deep level, and when I move to the end (or even
>near the end) of that line, the value goes way down
>(or up) at a simple 30-second search (say 5- or 6-ply).
Yes, this is because if you go to the end of a 10-ply variation, then
back up two plies, what you have is a two-ply search, which isn't very
accurate or we'd all just search two plies and be done. There are
moves ahead of these last two on the PV, and these moves are the
product of a lot of searching -- a lot of trees were examined in order
to validate *those* moves, and since they are closer to the root, they
are more likely to be accurate.
>Why would any MOVE in such a LINE even be considered as
>part of the continuation if its "badness" can be detected
>in just a few seconds? I know what the horizon effect is,
>but this seems much more basic to me, as simple as
>"checking your work" in a math problem. It can't "cost"
>too much time to run 5- or 6-ply at each possible POSITION
>(only 20 positions for a 20-ply LINE) to ensure that the
>proposed LINE ITSELF is worthy, can it? Are there really
>*that* many possible things going on that the computer has
>no time to CHECK THE SOUNDNESS OF THE LINE BEING PROPOSED!?
It isn't the line you are choosing, it is the whole tree under the
root move. The line is nothing, you are not necessarily commited to
the whole line, just because you picked the move at the root. The PV
is important, since there can be forced sequences in there that you
aren't extending on (so effectively you're searching very shallowly),
but not absolutely important.
bruce
Andrew Fan
>I have a basic question about chess program algorithms.
>
>Let's say you are finishing at some ply on a deep
>search. At the end of each ply, do chess programs
>"work backwards" to check if the intended line is
>really any good? Or do they only work "brute force"
>from the original position?
>
With an iterative alpha-beta search, the search depth is
extended at each iteration until allocated time runs out.
>For example, let's say a program settles on a move after
>completion of 10-ply, and let's say that the last move
>at the END of the 10-ply shown is Rook captures Bishop.
>
Forceful variations (captures and checks) will usually cause
the search depth to extend beyond the given number until a
quiescent position is found - in this most cases a static
evaluation function will rate the position.
>Now, at the *resulting* position at the END of this line,
>does the program then analyze this *possible* resultant
>position, at least to a certain depth, perhaps 6-ply?
>And if it does, and if it finds that the value calculated
>during this deeper "extension" of the original search is
>actually much lower than the value was at the 10-ply,
>does it "back up the intended line" until the value goes
>back up (improving the line using the move already found)?
>
How many "seem" good lines are there in a 10-ply search ?
How reliable are the extended 6-ply searches ? Why not search
another 6-ply beyond the extended 6-ply to make sure that
search is "good" ?
>This seems like a simple thing to do before making a move
>(if the value never goes up to what was "seen" at 10-ply,
>the line could be of course rejected). Does this "backward"
>thinking exist in the current chess programs, and if so,
>what is this procedure called?
>
>I ask this because often I see a line prepared out to
>some deep level, and when I move to the end (or even
>near the end) of that line, the value goes way down
>(or up) at a simple 30-second search (say 5- or 6-ply).
>
>Why would any MOVE in such a LINE even be considered as
>part of the continuation if its "badness" can be detected
>in just a few seconds? I know what the horizon effect is,
>but this seems much more basic to me, as simple as
>"checking your work" in a math problem. It can't "cost"
>too much time to run 5- or 6-ply at each possible POSITION
>(only 20 positions for a 20-ply LINE) to ensure that the
>proposed LINE ITSELF is worthy, can it? Are there really
>*that* many possible things going on that the computer has
>no time to CHECK THE SOUNDNESS OF THE LINE BEING PROPOSED!?
If I know the best move, then I don't need to search for it.
But I only know if a move is best after I've searched. That's
why forced moves are (usually) best moves!
Andrew.
Robert Hyatt
john quill taylor <john-qui...@hp.com> wrote:
: I have a basic question about chess program algorithms.
: Let's say you are finishing at some ply on a deep
: search. At the end of each ply, do chess programs
: "work backwards" to check if the intended line is
: really any good? Or do they only work "brute force"
: from the original position?
It is a "minimax" search... so the program searches "forward" from
the root, but scores get backed up "in reverse" from the tips. So
that you can recognize when it is profitable to not make another
capture for example... and so you can compare two (or more moves)
and decide which one looks "better" because you already have done
all the analysis, and just have to compare the numeric results..
: For example, let's say a program settles on a move after
: completion of 10-ply, and let's say that the last move
: at the END of the 10-ply shown is Rook captures Bishop.
: Now, at the *resulting* position at the END of this line,
: does the program then analyze this *possible* resultant
: position, at least to a certain depth, perhaps 6-ply?
: And if it does, and if it finds that the value calculated
: during this deeper "extension" of the original search is
: actually much lower than the value was at the 10-ply,
: does it "back up the intended line" until the value goes
: back up (improving the line using the move already found)?
Basically, yes... The only thing that stops a search down a
particular "line" is a decision, only allowable after searching
to at least "D" plies, based on whether you would choose to move
again or "stand pat" at the current position and accept it "as it
is."
: This seems like a simple thing to do before making a move
: (if the value never goes up to what was "seen" at 10-ply,
: the line could be of course rejected). Does this "backward"
: thinking exist in the current chess programs, and if so,
: what is this procedure called?
: I ask this because often I see a line prepared out to
: some deep level, and when I move to the end (or even
: near the end) of that line, the value goes way down
: (or up) at a simple 30-second search (say 5- or 6-ply).
This is the result of simply "stopping too soon" going down the
analysis of that line. That's why an eleven ply search is better
than a ten ply search... and why twelve would be better than eleven.
Deeper searches can reveal deeper tactics that produce far different
scores than the shallower searches...
: Why would any MOVE in such a LINE even be considered as
: part of the continuation if its "badness" can be detected
: in just a few seconds? I know what the horizon effect is,
: but this seems much more basic to me, as simple as
: "checking your work" in a math problem. It can't "cost"
: too much time to run 5- or 6-ply at each possible POSITION
: (only 20 positions for a 20-ply LINE) to ensure that the
: proposed LINE ITSELF is worthy, can it? Are there really
: *that* many possible things going on that the computer has
: no time to CHECK THE SOUNDNESS OF THE LINE BEING PROPOSED!?
the problem is that there are *millions* of such positions near
the end of the tree. If "analyzing" one takes only a few
seconds... watch what the "math" says... (1,000,000 x *anything*
is a *long time*.. :) )
: - jqt -
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Robert Hyatt
bruce moreland <bru...@seanet.com> wrote:
: On Wed, 13 May 1998 05:54:23 GMT, john-qui...@hp.com (john quill
: taylor) wrote:
:>This seems like a simple thing to do before making a move
:>(if the value never goes up to what was "seen" at 10-ply,
:>the line could be of course rejected). Does this "backward"
:>thinking exist in the current chess programs, and if so,
:>what is this procedure called?
: I think I have heard it called a verification search. Bob Hyatt can
: tell you who did it first. Probably Ken Thompson, if I had to guess.
Actually Richard Greenblatt... He tried this:
when a PV gets backed up to the root, first run back down to the end
of the PV, and do a two ply search from that position. If the score
gets better, toss it out. If it gets worse use this to decide whether
this move should be played or not.
I tried it in 1978 but took it out just before the ACM event. I didn't
like the way it behaved, although it would sometimes prevent me from
switching to something that had a problem out near the end. But in
general, it didn't catch that often enough..
john quill taylor
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
>...
>the problem is that there are *millions* of such positions near
>the end of the tree. If "analyzing" one takes only a few
>seconds... watch what the "math" says... (1,000,000 x *anything*
>is a *long time*.. :) )
So is it simply a matter of TIME, and not the horizon effect?
It seems to me that *some* of that time is not being well spent.
For instance, imagine going to 15-ply at say 10 hours, and three
moves down the tree, the evaluation goes way up or way down. If,
in that 10 hours, the program had merely looked at the POSITION
that was just a few plies away (in the supposed "best" line), it
would have discovered the goodness (or badness) at that juncture.
Maybe it's a matter of, "Is it worth spending time doing *this*
as opposed to searching from the known (yet static) position?"
Even on recapture of a major piece, or dodging a check (cases
when only one or two moves "make sense," it seems like the
programs "look" forward from the CURRENT position, when they
might be better off looking from the "probable future" position.
Shouldn't SOME time (more time?) be allotted to the soundness
of the LINE, and not just the MOVE? I realize that there are
millions (billions!) of possibilities, but I have also seen how
much more "powerful" moves can be seen by "testing" the branches
of the proposed line with a SECOND computer. It often takes just
just a few minutes for a second program to "see" better moves
"down the line," and thus improve the line in less time than
it takes just one program. Maybe with TWO processors, ONE could
just be a go-ahead-look-for?!
I guess what I am saying is that a given LINE yields known
possible POSITIONS, and these POSITIONS, much like "won"
endgames in a tablebase, could be checked very quickly, and
if the evaluation goes up, the program could at least STRIVE
for that position (raise the evaluation even if it cannot be
"seen" from the current position). It sounds like this has
already been done (and is being done), and I do understand
the "danger" of heading down a line without COMPLETE justification
for that line. It does, however, seem to be the way HUMANS play,
at least some of them.
Thanks for all of the interesting re-plies! :-)
- jqt -
Robert Hyatt
:>...
:>the problem is that there are *millions* of such positions near
:>the end of the tree. If "analyzing" one takes only a few
:>seconds... watch what the "math" says... (1,000,000 x *anything*
:>is a *long time*.. :) )
: So is it simply a matter of TIME, and not the horizon effect?
: It seems to me that *some* of that time is not being well spent.
: For instance, imagine going to 15-ply at say 10 hours, and three
: moves down the tree, the evaluation goes way up or way down. If,
: in that 10 hours, the program had merely looked at the POSITION
: that was just a few plies away (in the supposed "best" line), it
: would have discovered the goodness (or badness) at that juncture.
: Maybe it's a matter of, "Is it worth spending time doing *this*
: as opposed to searching from the known (yet static) position?"
: Even on recapture of a major piece, or dodging a check (cases
: when only one or two moves "make sense," it seems like the
: programs "look" forward from the CURRENT position, when they
: might be better off looking from the "probable future" position.
This is known as "forward pruning" where you don't follow *all*
lines into the future, but only follow some. However, if the ones
you *don't* follow turn out to be good for you, you miss them. If
they turn out to be bad for you, you *still* miss them and walk
into things...
: Shouldn't SOME time (more time?) be allotted to the soundness
: of the LINE, and not just the MOVE? I realize that there are
: millions (billions!) of possibilities, but I have also seen how
: much more "powerful" moves can be seen by "testing" the branches
: of the proposed line with a SECOND computer. It often takes just
: just a few minutes for a second program to "see" better moves
: "down the line," and thus improve the line in less time than
: it takes just one program. Maybe with TWO processors, ONE could
: just be a go-ahead-look-for?!
Yes, *if* you know which moves to check. That's the problem...
: I guess what I am saying is that a given LINE yields known
: possible POSITIONS, and these POSITIONS, much like "won"
: endgames in a tablebase, could be checked very quickly, and
: if the evaluation goes up, the program could at least STRIVE
: for that position (raise the evaluation even if it cannot be
: "seen" from the current position). It sounds like this has
: already been done (and is being done), and I do understand
: the "danger" of heading down a line without COMPLETE justification
: for that line. It does, however, seem to be the way HUMANS play,
: at least some of them.
: Thanks for all of the interesting re-plies! :-)
: - jqt -
Komputer Korner
Most programs do this now. Most have some form of forward pruning even
if it is only singular extension. Check the 2nd number of the search
depth line of a program like Fritz 5 where it singularly extends a
promising PV very deep into the tree. Notice that the 2nd number of
search depth plies is much larger than the 1st number which is the
full width ply number that has been searched.
--
--
Komputer Korner
The inkompetent komputer
To send email take the 1 out of my address. My email address is
kor...@netcom.ca but take the 1 out before sending the email.
john quill taylor wrote in message
x6jfi75$5q...@hpbs1500.boi.hp.com>...
xSo is it simply a matter of TIME, and not the horizon effect?
xIt seems to me that *some* of that time is not being well spent.
xFor instance, imagine going to 15-ply at say 10 hours, and three
xmoves down the tree, the evaluation goes way up or way down. If,
xin that 10 hours, the program had merely looked at the POSITION
xthat was just a few plies away (in the supposed "best" line), it
xwould have discovered the goodness (or badness) at that juncture.
xMaybe it's a matter of, "Is it worth spending time doing *this*
xas opposed to searching from the known (yet static) position?"
snipped
xShouldn't SOME time (more time?) be allotted to the soundness
xof the LINE, and not just the MOVE? I realize that there are
xmillions (billions!) of possibilities, but I have also seen how
xmuch more "powerful" moves can be seen by "testing" the branches
xof the proposed line with a SECOND computer. It often takes just
xjust a few minutes for a second program to "see" better moves
x"down the line," and thus improve the line in less time than
xit takes just one program. Maybe with TWO processors, ONE could
xjust be a go-ahead-look-for?!
xI guess what I am saying is that a given LINE yields known
xpossible POSITIONS, and these POSITIONS, much like "won"
xendgames in a tablebase, could be checked very quickly, and
xif the evaluation goes up, the program could at least STRIVE
xfor that position (raise the evaluation even if it cannot be
x"seen" from the current position). It sounds like this has
xalready been done (and is being done), and I do understand
xthe "danger" of heading down a line without COMPLETE justification
xfor that line. It does, however, seem to be the way HUMANS play,
xat least some of them.