Author: Christophe Theron
Date: 23:35:49 12/27/97
Go up one level in this thread
On December 26, 1997 at 18:05:04, Chris Whittington wrote:
>I figured the search was always fixed to odd ply, because of doing
>static exchange evaluations. Safer for the assymetry if you stop with
>the decision that a piece is en prise when its your pieec, than to stop
>when its the opponent's piece (the opponenst piece may never get won,
>perhaps), so deducting it from his score and giving it to yourself is a
>dangerous thing to do .....
>
>If evrybody uses capture search, this is no longer relevant.
>
>The words "used to" and "was" above imply that the recent Genius's no
>longer act this way, true ?
I think you are right. The very old Psion 1.01 for PC does this, and I
believe Genius 3 and 5 still does. You'll even see Psion or Genius
evaluate positions where one side is in check!
Using a SEE, if you find a safe way to do it, is interesting because you
evaluate less positions, so you can afford spending a little more time
on positional evaluation. And the safe way to use a SEE is to evaluate
after YOUR move, as Chris said. Furthermore, you are able to detect
what's happening to you in the end of the line, I mean you are more
aware of the threats your opponent does to you than the threats you do
to him.
So here's a summary of the informations collected about the Lang
algorithms. Maybe they are out of date, but it is still interesting to
know why those programs were so good for such a long time:
* Use a SEE to evaluate leaves
* Evaluate only after your move (so build only odd-length lines)
* When it is your side to move, select only interesting moves (the best
move, from a positionnal point of view, and all threatening moves, for
example)
* When it is the opponent's turn, select every move
I think the idea of looking at every possible move when it is the
opponent's turn is a little bit too much. Another related idea would be:
* Your turn: select the best move (from a SEE+positional 1 ply
evaluation) and the very threatening moves (including checks of course)
* Opponent's turn: select several best moves and any threatening move.
About the "shifted search": usually, the program is careful about what
could happen to him (looks at a lot of the opponent's moves). But if you
detect an agressive move (attacking the opponent), it could make sense
to "shift" and be careful for the opponent (looking at a lot of your
moves to see if a combination is possible).
This could be done in a very natural way by recapture or check
extensions. A recapture on the same square, if it wins something, often
is the second move of a combination: your opponent has given you
something that you just re-captured, and he's looking for some tactical
compensation. That's why some programs (CM4000, Rebel?) do an extension
here. The recapture is "free" and does not count as a ply. The
recaptured piece doesn't have to be the same as the piece it just
captured the move before. In fact, it is better if it has a bigger value
(the exchange seems to be a loosing one).
That's the ideal place to put your "shift" in the search. From that move
on, the recapturing side is, maybe, "defending" against a combination.
So in order to find the combination you start being less selective for
the other side. The same applies for a check evasion.
That's just an idea I had to justify the "shifted search". Personnaly I
don't believe it's a good idea, but maybe somebody's going to find out
that it works...
Another thing: the above principle don't prevent you from using null
move, although using an SEE to detect threats is just another way to use
the null move idea. The real null move is more efficient, I know it
because I tried both. A good thing is to use the SEE in the last 2 moves
of the lines, and use null move when you are closer to the root. Try
using the SEE in the last 3 moves if you want to take some risks! The
SEE has to include a "mate in 1" detection.
And still another thing: none of the above ideas tells us how to extend
the search beyond the nominal depth. Everybody here has seen Genius very
long lines (we are back to the idea of this thread and Junior's long
lines), going 12 plies beyond the normal exhaustive search. How would
you do it?
My contribution: compute a pessimistic score in the leaves and decide
the node is a terminal one only if pessimistic_score >= beta. In the
classical quiescence search the pessimistic score is simply the static
evaluation score. In this new kind of QSearch, I define it to be
(static_eval - threats). QSearch can generate every move (not only
captures) if a threat is detected.
I'm sure you'll need some extra filtering mechanism to prevent to much
tree growth. Somebody has an idea?
Christophe
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.