Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Mixing alpha-beta with PN search

Author: Tord Romstad

Date: 04:04:16 01/20/04

Go up one level in this thread


Hi Dennis,

Thank you very much for your answer!  I am very happy to recieve
advice from one of the leading authorities on PN-like algorithms.

:-)

On January 20, 2004 at 05:54:11, Dennis Breuker wrote:
>
>I haven't worked on something similar, but have worked with PN search
>and PN^2 search (see my thesis). I have thought about using PN search
>for finding material wins.

Yes, I've read and enjoyed your thesis, of course.  Your idea of using
PN search for finding material wins is already on the list of thing
I would like to try out some time.  One of my most recent changes in
my engine is the following:

When the side to move is ahead by a piece or more in material, and
the opponent has no positional compensation, I use a null move search
with my normal evaluation function replaced by a much simpler function.
The idea is that the position is almost certainly won unless the
opponent has a forced tactical win.  Inside the null move search
positional scores are not very important (I hope), and a primitive
evaluation function should be enough.  If the nullmove fails high
by a big margin (which is usually the case), I return the value of
the static eval (*not* the value of the null move search).  If
the null move fails high by only a small margin, it is too risky
to trust the reduced-knowledge search, and I do another null move
search with the full evaluation function.

It is perhaps worth a try to replace the reduced-knowledge
null move searches with a PN search for finding material wins.

>In general, I think it is very difficult to use plain PN search
>for finding an arbitrary goal. PN search is guided by mobility:
>it prefers positions where the opponent has few moves, and you
>have many moves. That is why it is good in finding forced mates.
>If the opponent has few moves, there is a higher probability
>that there is a mate somewhere. And that is why PN search is
>not so good in finding mates where you have to make a
>"silent move" (don't know the Engelish term for it) somewhere in
>the sequence.
>A forced mate like 1.Nf7+ Kg8 2.Nh6++ Kh8 3.Qg8+ Rxg8 4.Nf7 mate
>is very easy to find for PN search, whereas a mate like
>1.Bf6 any 2.Qh6 any 3.Qg7 mate is much more difficult to find
>for PN search.
>
>This means that when you have other goals than mate, you must
>guide the search for a most proving node by something else than
>mobility... And that's not easy.

It's not easy, but in certain cases I am not sure it is entirely
impossible.  Finding a clever domain-dependent way of assigning
the initial proof and disproof numbers could help, don't you
think so?

Tord



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.