Author: Peter McKenzie
Date: 15:02:00 01/12/01
Go up one level in this thread
On January 12, 2001 at 15:12:13, Miguel A. Ballicora wrote:
>On January 12, 2001 at 05:01:23, Peter McKenzie wrote:
>
>>On January 12, 2001 at 03:20:26, David Rasmussen wrote:
>>
>>>My program Chezzz, and most of the programs I've been learning from and looking
>>>at, has only little or moderate selectivity. Maybe I will keep it that way in
>>>Chezzz, but what are the possibilities?
>>>
>>>As far as I know, there are two general kinds of selectivity as currently used
>>>in "normal" alpha-beta based chess programs.
>>>
>>>1. Extensions
>>>2. Forward pruning
>>
>>Do not forget move ordering, which although is not a form of selectivity in
>>itself is equally important as the two things you mentioned.
>>
>>>
>>>I would like to know what hints and tricks you guys have about extensions,
>>>unusual extensions, how to limit extensions, when not to extend etc.
>>>
>>>But most of all, I would like to know about successful (I know this is somewhat
>>>subjective) forward pruning techniques, that are actually used in programs.
>>>
>>>I compared my programs performance on the position below, with what Christophe
>>>Theron posted from GT. At depth 10 the nodes searched by each programs are appx.
>>>
>>>GT : 1.290.000
>>>Crafty : 13.500.000
>>>Chezzz : 12.500.000
>>
>>LambChop: 5,109,252
>>
>>>
>>>So Crafty and Chezzz is the same, and they are both very conservative in regard
>>>to selectivity IMO. I know that this is a choice and that one way is not better
>>>than the other, but I would still like to know how programs such as GT can get
>>>such a low node count.
>>
>>I think LambChop is a bit more aggresive with selectivity than crafty, for a
>>start it uses various forms of futility pruning as described by Ernst Heinz in
>>his book and on his web pages. On the other hand, I believe my q-search sees
>>more than crafty's.
>>
>>>
>>>Now I know that GT is highly optimized, and that it has probably taken a long
>>>time get as "efficent" as GT. But I would still like to know as much as possible
>>>or at least the basics about how to forward prune succesfully like this.
>>
>>I don't know how GT works and I suspect that Christophe isn't about to tell us
>>:-) Actually I don't mind either, because it is fun to try different things for
>>myself. Imagine if Bob put some cool forward pruning stuff in crafty, then
>>before you know it everyone would be using it - how boring!
>>
>>I guess the basis for some successful pruning methods is figuring out that a
>>position is really great, and that it is a waste of time searching it to the
>>normal depth. This is all that null move pruning does after all.
>>
>>So how can we improve on null move pruning?
>>Well, there are two areas that come to mind:
>>
>>1) find a cheaper way to determine if the position is great. The null move
>>search is quite cheap, but it certainly isn't free.
>>
>>2) find a more accurate way to determine if a position is great. I suspect that
>>the null move search is still quite pessimistic and doesn't prune alot of
>>positions that it should (of course the flip side is that it doesn't make too
>>many mistakes either!).
>>
>>The cheapest way to estimate if a position should fail high is to just look at
>>the static eval. Not very accurate though! Perhaps you can use this to guide
>>your search? Thats what fail high reductions do I think. If you could combine
>>that technique with null move pruning, then you might be on to something.
>>
>>Maybe you can make better use of the eval function by looking at its component
>>parts? For example:
>> if eval > beta + margin && ourKingSafetyPenalty < xxx then
>> prune(); // or reduce search depth or whatever
>
>How about
> if ((eval > beta + margin) && (ourKingSafetyPenalty < xxx)) {
> R=4; /* null move constant */
> } else if (another_condition()) {
> R=3; /* null move constant */
> } else {
> R= DEFAULT_R; /* 2? */
> }
> /* test null move pruning here */
>
>rather than pruning, which could be risky, it allows a cheap second option
>to avoid it = Null move with a very high constant. Maybe different margins
>could use different R's?
>Does it sound reasonable?
Yes, I was wondering about that too.
>
>I think I am going to try it.
Please report your results!
>
>Miguel
>
>
>>
>>Anyway, just a few random ideas :-)
>>
>>Peter
>>
>>
>>>
>>>[D]2r1k2r/5pp1/4p3/ppqpP3/4bQPP/1B6/PPP2R1R/2K5 b k - 0 1
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.