Author: Don Dailey
Date: 15:18:14 06/11/98
Go up one level in this thread
On June 11, 1998 at 08:04:04, Ernst A. Heinz wrote: >On June 10, 1998 at 16:33:26, Don Dailey wrote: > >>Is my understanding correct that you are always trying a null move, >>regardless of the static score? > >Yes, I suspect many/most people do it this way -- "DarkThought" incl. > >>For me it seems to work best to >>have a static score very close (or above) beta. The algorithm as >>I once saw it in the ICCA journal used a half pawn margin. > >Up to which depth to you use the static scores for deciding about >null-move trials? All depths where I do null move. Is there an improvement here? I will experiment more with this since others seem to find it more workable. >>I found it slightly faster to simply do a test search with a zero >>width alpha/beta window around beta. The idea being I only care >>if we get a beta cutoff on the null move search. I'm not using >>the result of one of these searches to tighten the Alpha side of >>the bound either. With MTD this is a non issue but I found >>it works find even with conventional alpha/beta. > >Again I think many/most people only do the zero-window test ... No surprise, since it seems faster. >>Depth-3 selectivity does not work for me, although others report >>great results. I always get nice speedups but find the program >>weakens just enough to measure. Even when I'm very careful about >>endgames and special case things. > >Yep, same for "DarkThought". Independant verification! Bob and Bruce do not notice it, but each program is different. >>My biggest improvement is to not use null move near leaf nodes of >>the main search. A "global" static attack test seems to be a very >>nice improvement. It must be tuned but not too strict. It makes >>the search much faster and it benefits from the speed. I can >>easily measure the improvement in testing. It turns out that I >>actually pick up a few things null move misses although visa-versa >>is also true. I can only do a couple levels of these, then null >>move is superior for its ability to see longer range threats. >> >>The basic idea of our static routine (much of it designed by Larry >>Kaufman) is that we notice the highest valued piece attacked, and >>then assume part of its value will be returned, so if a queen is >>attacked, we assume only 2/3 of a queen is attacked. This is a >>major speedup and the assumption is very good for all the pieces. >>There is a value that seems to be on the threshold of right and >>wrong, and it can be found by noticing a sudden drop in problem >>solution depth when you get too agressive (like 1/2 attacked value.) > >I must admit that I do not quite understand how you actually prune. >Could you please elaborate on this? > >=Ernst= Ok, here is more detail. I do several plies of null move selectivity, and 2 plys of static selectivity. Here is how the static selectivity works: If the current STATIC score (same as stand pat in quies) is less than BETA, then I go full width. Otherwise, I execute a static analysis of the board looking to see what is attacked for the side who just moved (similar to null move but static.) The analysis is not terribly sophisticated, it does not need to be since you can take conservative assumptions. Refining them even more runs into a serious point of diminishing returns so it doesn't seem to be worthwhile. Here is how the attack testing works. Start with highest valued piece and work your way down to lowest valued piece. So for each piece: If 2/3 of the pieces value is not enough to prevent a beta cutoff, then quit, and BE SELECTIVE. Otherwise, Is piece up-attacked? If yes, then go FULL WIDTH. Is piece down attacked but defended by a pawn? If so, then no problem, move on to next attacked piece. If piece is attacked at all, then count attackers and defenders, if it's defended more than or equal to the number of times it's attacked then everything is cool, move on to next attacked piece. If there are no attacked pieces, then take the static score as your beta cutoff. I'm not positive I got every single detail correct. But the idea is simply to notice what is attacked and statically make a decision about whether the threat is serious or not. If any piece is seriously attacked we still assume (since it's the attacked guy's turn to move) that we will get 1/3 of the loss back. All these assumptions and our static analysis is subject to error, but it turns out it is quite reliable overall and buy's a lot more speed than normal null move close to leaf nodes. Since null move is simple I've tried to take the static stuff out of the program, but each time I get a noticable strength loss. I would actually prefer to keep pure null move for its simplicity. I will always do what seems to work best like most of us. There are a couple other refinements I should mention. We do some simple static mate threat stuff and also consider pawns on the 7th as big threats. My old program REX used 4 ply of this kind of selectivity and also looked at other advanced pawns. Once you are more than 2 or 3 ply from quies, it becomes difficult to pick up deep threats. The current program reverts to static selectivity in pure king and pawn endgames. This routine is cool. I can do several ply of this because I essentially count the distance of the king to each enemy pawn. For instance if the white king is 4 squares away from ANY black pawn, there can be no threat (except positional which we also take into consideration) for 7 or 8 ply. Of course we also count distance from queening and other considerations but you can make nice assumptions with a little thought. Null move loses many ply in some of these endings but this static stuff is actually faster while losing less depth on problem solution. My thinking (as I already mentioned) is that this kind of stuff might make a better program than null move. Null move is nothing more than estimating a lower bound on the score. How you do it is irrelevant, it's HOW WELL you do it. - Don
This page took 0.03 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.