Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: An MTD(f) question about NULL MOVE searching

Author: Vasik Rajlich

Date: 11:46:36 07/16/04

Go up one level in this thread


On July 16, 2004 at 13:55:46, Fabien Letouzey wrote:

>On July 16, 2004 at 13:40:52, Vasik Rajlich wrote:
>
>>On July 16, 2004 at 12:13:25, Fabien Letouzey wrote:
>
>>>Actually in PVS I think of every PV node as a root.  If PV nodes really are
>>>different (as they seem to be regarding move ordering), that would justify doing
>>>other things differently as well.
>
>>Do you mean that you order moves differently at PV nodes? I guess I should take
>>a look at your code. It doesn't sound like a bad idea.
>
>No I don't except for IID now.  But since scout-like algorithms make the
>assumption that the first move is the best one (as opposed to "good enough to
>produce a cutoff" in null-window nodes), it would make sense in my current
>understanding.

It's true, this does make sense.

Much of the search tree is filled with all sorts of bogus positions, with
material hanging, etc. This is why move ordering generally favors primitive
moves like captures and killers. Along the PV, it may be different. It may also
not make much difference on the size of the overall tree.

>
>>PVS with MTD (f)-like driver. My first engine was MTD (f), and I hope that tests
>>will justify using small/zero width windows in at least some situations. Note
>>that MTD (f) is a degenerate case of PVS.
>
>I completely disagree here.  I consider PVS to be "move based" (e.g. the scout
>assumption) while MTD(f) is value-based (at the root).
>
>Actually I look at PVS as alpha-beta + the scout "trick".  MTD(f) seems very
>different from alpha-beta to me (in its way of scanning the tree that is).
>

Well, it depends on the point of view. MTD (f) is a degenerate case of PVS from
the point of view of the search code. Here is a perfectly reasonable MTD (f)
implementation:

int MTD_f_Search (int beta)
{
 return PVS_Search (beta-1, beta); // fail soft, double-sided HT, etc ..
}

The difference between MTD (f) and PVS is nothing more than the size of the
initial root window, and the stepping function used by the root driver in the
case of a fail high/low.

So, why not abstract those properties into a more general root driver, and be
prepared to adjust them based on some characteristics of the position or the
current search.

In the worst case, the general driver degenerates into either PVS or MTD (f), or
something in the middle (ie bigger windows than MTD (f), smaller than PVS).

Anyway - I'm about to head to Biel for two weeks, possibly without much
internet. I'll post anything interesting in this direction when I get back ...

Vas

>Fabien.



This page took 0.04 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.