Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: One mate to solve... that now is very easy.

Author: Paul Byrne

Date: 15:04:11 05/07/01

Go up one level in this thread


On May 07, 2001 at 03:44:07, Paul wrote:

>On May 07, 2001 at 03:18:23, Paul Byrne wrote:
>
>[D]Qqrkrq1Q/1QqqqqQ1/qBbnnbBq/1NQ2QN1/8/2Q2Q2/3RR3/3K4 w - -
>
>>G2K's PN search says:
>>
>>1W. i=8094 n=324622 p=0 d=1000000000 t=3.620
>>1W. Qxc7 wins!
>>
>>3.62 seconds, 324633 nodes.  This is the kind of mate PN does well in, although
>>it doesn't get you a mate-in-n number.
>
>Hi Mr. Byrne,
>
>I (still) haven't read anything about PN, but am very interested to learn ... is
>there anything you can recommend for reading? The only thing I have is a
>postscript doc by Victor Allis, that I think is about the subject (haven't got a
>reader installed now), but maybe you know of something shorter/lighter to get
>into it?

I think the Allis thesis (chapter 2 in particular) is the best introduction
I have seen to PN search...

>I understand from a remark by Heiner Marxen that you have to have plenty of
>memory for PN search, presumably coz the search results have to be saved? But
>why don't you have a winning variation (pv) and number then?

Yes, PN search keeps the entire search tree in memory.  One way to save memory
is to delete any solved subtree once you update the parent's values, since it
will no longer be needed -- that way you can recycle the nodes and get a
longer search.  This makes extracting a pv afterwards rather difficult though.

Without that, you could get a pv -- although you would have to do some searching
in the tree to get the shortest line.  However, PN search tends to produce
some very non-optimal lines since it will search forcing lines quite deeply,
so the pv and mate-in-n number won't be very reliable.

Classic situation is in an endgame where the opponent's king is forced into a
corner so the opponent only has one legal move on each turn.  PN search can
produce lines hundreds of moves long in which the pieces not needed to corner
the king wander at random around the board, just enough to avoid repetition
draws.  Adding a small depth factor will limit this.

-paul



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