Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: SEE for forward pruning in Q. Search

Author: Vincent Diepeveen

Date: 17:00:45 08/08/99

Go up one level in this thread


On August 07, 1999 at 17:58:55, Robert Hyatt wrote:

>On August 07, 1999 at 08:17:49, Vincent Diepeveen wrote:
>
>>On August 05, 1999 at 22:43:29, Robert Hyatt wrote:
>>
>>>On August 05, 1999 at 17:13:28, Tom King wrote:
>>>
>>>>On August 04, 1999 at 20:00:49, Robert Hyatt wrote:
>>>>
>>>>[snip]
>>>>>
>>>>>
>>>>>I find the following:
>>>>>
>>>>>using SEE to order captures in the q-search, without eliminating any, will
>>>>>shrink the tree about 10% over using something simple like MVV/LVA.  But the
>>>>>SEE code will likely cost you more than 10% (unless you are a bitmap program
>>>>>where this can be done fairly efficiently).
>>>>>
>>>>>using SEE to eliminate losing captures can speed you up another 50%, or a factor
>>>>>of two, which is very significant.  And no matter how slow your SEE code is,
>>>>>that become a 'winner' of an idea.
>>>>
>>>>I'm seeing a big speedup - it's just the (possible) loss of accuracy which
>>>>concerns me. Having said that, my Q search is pretty "quick and nasty" anyway,
>>>>although I do still do things like probe the hash tables.
>>>
>>>
>>>This is only my opinion, but I spend my time working on the full-width part of
>>>the search (extensions, etc.).  The q-search already has _so many_ errors in it
>>>(it is highly selective since throwing out everything but captures is a drastic
>>>step, of course) that I don't trust it at all.  I just want it to handle simple
>>>hung pieces and not much else...  I'll trust my extensions to find the deep
>>>tactical tricks since then I won't be overlooking pins, forks, skewers, etc.
>>>
>>>When you think about it like that, shrink the q-search and use those nodes in
>>>places where they are more useful.
>>>
>>>Just an opinion, of course...
>>
>>Right, my opinion is different. A good qsearch will give more accurate
>>scores for leafs, so in a set of leafs X, for all leafs x in X we will have
>>a more reliable score.
>>
>>So whatever plydepth we get, we will get a positional more trustworthy score,
>>which with backtracking will result in a better and more reliable score.
>>
>>Greetings,
>>Vincent
>
>
>Most searches have three parts:  (1)full width to depth=N; (2) highly selective
>until a terminal position is reached;  (3) static evaluation.
>
>I tend to put my faith in (1)... you want to put yours in (2).  I think it is
>nothing more than a tradeoff...  If your (2) is a lot bigger than mine (and it
>is if you do checks/out-of-check moves there) then your (1) is smaller than
>mine.  In some positions, you will do better.  In others, I will do better.
>
>The real question is, in real games, which works better?  The jury is still
>out, but not doing checks is not getting me killed...  I did checks in the
>q-search many versions ago.  I'm going to test them again pretty soon.  But
>the real question is which plays better?
>
>I don't think that is anywhere near a "resolved issue"...

We agree here that this is not a resolved issue, as so many things
depend upon it.

The only thing that is sure is that pruning on alpha in the qsearch is
dubious (assuming you have a static evaluation which can produce some
real scores).

The only thing we can do to reduce overhead is pruning on beta.

so basically:
  if( !check )  {
    if( score >= beta )
      return score;
    else for all interesting moves:
      try move.
  }
  else {
    for all moves:
      try move.
  }

Now what i personally think is that
the influence of TRYING a move in qsearch is huge
on the hashtable.

It has of course great relation with evaluation.
Suppose evaluation evaluates pieces that can be captured, so
evaluation more or less evaluates using SEE.

That definitely removes the need for the number of
tried captures.

Just exchanging is simply not needed.

In diep i'm not having recapture extensions, but i do
capture usual equal pieces, even when there is big suspicion
that it can be captured back by the other side.

I prefer to do as much as possible within mainsearch, as
i can use there my hashtables better. Therefore i limit
the number of moves tried in qsearch drastically.

First thing to do is introduce 2 new node counts;
node counts that measures number of nodes done in

  a) qsearch
  b) brute force part

Some 5 years ago when the first versions of DIEP
were made i already figured out the more moves i
tried in a, the less nodes i needed in b.

So first word i thought of: "trade-off".

However total node count could drastically increase
at smaller depths when doing more moves in a. At
bigger depths influence was harder to define, as
branching factor got slightly better.

Later analysis were that some real silly moves in
qsearch, like some silly checks and queen captures
covered pawns, wasted bunches of nodes.

So some knowledge in move selection
improved this, still keeping the good branching factor.

Yet this 'trade-off' we will keep of course.

It's very important to realize *what* nodes in b
get influenced by a.

I'm using nullmove R=3. So this means that i nullmove
last 4 ply using the qsearch.

In fact this way of nullmoving is only detecting whether
there are threats against the position. The better i see
the threats in qsearch, the more reliable nullmove will be
the last 4 ply. It's not difficult to imagine a position
where just using qsearch to nullmove misses positional things.

Of course you search so much deeper because of nullmove that you
identify those positions anyway, but then the unreliable score here
causes the hashtables to get bad scores. Now those scores won't
be backtracked to the root. They will however influence the
search tree considerable in move choices next iteration.

Now every iteration there are exponentially more nodes that
have this phenomena.

So in short a better qsearch gives my program in big amounts
of positions a more reliable score which
takes care for a smaller branching factor.

However there are clearly tradeoffs, you cannot do *all checks*.
You cannot do *all captures*. You cannot do *all* interesting moves.

Vincent









This page took 0.02 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.