Author: Christophe Theron
Date: 23:58:14 01/04/98
Go up one level in this thread
On January 04, 1998 at 18:37:30, Don Dailey wrote:
>Once Richard told me or Larry that he could not do a 2 ply search. I
>got the idea that his program always REQUIRES a response to the
>computers move. So a 1 ply search could never have a 1 ply PV if
>my understanding is right. And yet the search always seems odd except
>in the case where you are doing a 1 ply search with no selectivity.
Don, I think you gave me a part of the secret last time.
Remember that you said:
>We could start with some simple experiments. Suppose we (as a test)
>threw out null move altogether and always took a beta cutoff at ood
>nodes, after ply 1, 3, 5, 7 etc. This of course would be when when
>the static eval >= beta. This first experiment would give us an uppper
>bound on how fast this could be.
I tried this today. It doesn't work very well in the way you describe,
but I think you are on the right track.
I changed your suggestion. I removed my quiescence search and turned it
to full width search BUT:
* if it is the opponent's move, I change alpha to max(alpha,eval(pos))
before generating and trying the moves. This can produce a cutoff, as in
a standard QSearch, or give a better value for alpha.
* If it is the computer's move, I don't change anything
In both cases, I apply "futility pruning". That is: if
eval(pos)<alpha-margin, I don't generate every move, but only captures.
Let margin=0.90
* I limit this Q-Selective-Search to 8 plies.
To say it differently: I don't care if the opponent is threatened. And
if the score is very bad, I assume that only a capture can bring it back
into the window.
This modified QSearch comes after a normal full width search.
It doesn't work very well, because I only spent 1 hour or 2 on it. And
it is very slow too, almost unusable to play a real game, because it
develops large trees.
But the interesting fact is that it gives Genius-like main lines. I mean
it solves some problems at ply 1, when a conventional program would
solve them at only deeper levels. In fact it solves only "traps",
positions where there is a danger for the side to move. And the main
line has very often an odd number of moves.
But it solves nothing else quickly, as we expected anyway. The goal is
just to find a reliable line for the program in the long term, maybe not
the best.
A 1 ply search takes several seconds on my computer. In the same time,
Tiger could compute to ply 6 or 7.
The basic idea is correct, but we have to introduce some optimizations
to get a reasonable tree.
Anyway, I think it's a step forward. Hope you will find some time to
experiment with your own idea, or with the modified version I am
suggesting.
>I have a feeling he gathers bounds for 1 side after a move so that a
>1 ply search would be missing some information. Similar to our null
>move selectivity, where we get a score bound for 1 side only.
Maybe these bounds can be used to limit the search generated by our
too-simple-but-Genius-like-indeed selective search.
>So in some way I believe everthing is linked together in move pairs
>and maybe even his evaluation is in 2 stages. It would be great if
>I could do evaluation in a consistant way to avoid the odd/even affect
>and the stand pat bonus crap in my program. Maybe Richard does.
Maybe it's the only reason why he cannot do even plies searches.
Anyway, as I said, the above algorithm has the "side effect" of finding
odd length main lines. Natural, since we prune before the other side's
moves.
>It could very well be that he always ends on the opponents move but
>does not display the final move of the pv, it's basically a check to
>see if the previous computer move is sound. I think he has something
>like a capture search but it's heavily pruned by a swap off evaluator
>and considers more than just captures too.
A SEE could help prune more and maybe to get acceptable tree size... How
to use it? To prune after the opponents move?
We could do before the program's move the same pruning you suggested
before the opponent's move, but with more care:
alpha = max( alpha, eval(pos)-loss(side) );
if (alpha>=beta) return(alpha);
This allows pruning the non-dangerous opponent's moves.
(loss(side) is given by the SEE. It can be, for example, the value of
the most attacked piece, or of the worst exchange the opponent can
start).
>Years ago there was lot's of talk about "tapering" and Richards program
>was considered an example of this. I think Richard himself called it
>tapered selectivity. I'm pretty sure there is some notion of including
>less moves as you get closer to the leaf nodes of his search. In
>conversations with him he was very vague about this but indicated
>that he threw out more and more moves, sort of like 80% 70% 60% 50%
>etc. I know this sounds artificial but it's basically the idea as
>I remember it from him. It's quite possible I didn't interpret what
>he said correctly or his ambiguity left too much to interpretation.
This is still in the dark side of our moon.
>Any, more thoughts and ideas.
Yes, I think we are in the right way. Others readers, send ideas!
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.