Author: David Rasmussen
Date: 02:33:16 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. > Of course it is important, but I don't think that there is a tenfold tree size improvement in enhancing move ordering. Crafty's move ordering is already quite good, and even if GT's is even better, I don't believe that it accounts for this dramatic difference. >> >>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. > OK >> >>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! > Agreed. Still, people would develop the ideas and programs would end up being different after all. All the "new" ideas from the last 10-15 years, that are being used in nearly all chess program today, doesn't mean that all programs are the same. >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 :-) > Nice ideas. But I was looking not so much for new ideas, as for the already known forward pruning techniques that a program such as GT might be using or at least build on, to achieve such "good" performance, node-wise.
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.