Author: Peter McKenzie
Date: 02:01:23 01/12/01
Go up one level in this thread
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
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.