Author: Miguel A. Ballicora
Date: 12:12:13 01/12/01
Go up one level in this thread
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?
I think I am going to try it.
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.