Author: Don Dailey
Date: 14:44:35 12/17/97
Go up one level in this thread
>The only forward pruning is by recursive null move. I recently >understood >something Bob Hyatt and Bruce Moreland had mentioned on occasion >about allowing the null-move to collaspe straight into the capture >search. >I implemented this (it turned out to be a simplification over what I was >doing >before) and it was a big win. Hi Dan, I know a lot of programs seem to do this. My program does not, and I'm wondering if I did not implement it correctly myself since most people seem to think this is the best. Here is what I do, I would like some comments from other programmers: I use a reduction factor of 2, like most but not all programs. If my reduction factor takes me into the quies search, I resort to a "static board analysis" instead of null move. Essentially, I look at what is attacked and how it might effect the score if it is won and in this way compute an estimated lower bound on the score based on this analysis. My rules for doing this are not complex, they are very simple. For instance if there is an up-attack, I assume the piece is 3/4 lost or something like this. Normally a lost piece can sacrafice itself and get a little something back in exchange for its life. The analysis is superficial, but I usually error on the conservative side. A pawn on the 7th is considered an attack of a queen. I do no pruning at all if our "stand pat score" or static evaluation if not already equal or above beta. I know there are programs that use only static evaluation. If anyone remembers REXCHESS, this was one of those programs. I've tested this algorithm a lot and it's faster, and consistantly outplays this other thing I believe you guys are doing. But it makes me wonder if I'm missing some fine point of the implementation. Can any of you elaborate more on exactly what you do here? I can give you guys a more exact description of what I do too if anyone thinks it is at all interesting. But I noticed at the Dutch championship (and other tournaments too) that we do not seem to be "outsearching" anyone. We used 4 Alpha processors (466 mhz) and everyone else used 1 of something else, usually some type of Pentium or Sparc. I keep getting the feeling that I'm not getting the most out of the selectivity. There were a number of cases where our opponents report greater depths than us. However the extra hardware does seem to help a little, we have lost only 1 game in our last 22 games at the Dutch championship and suffered 3 draws (some of the draws we were damn glad to get!) At the Aegon I noticed Bruce's program seemed really FAST like Fritz. I remember wishing my 32 processor SGI program was that fast! I was rubbing my eyes trying to figure out if something was wrong with them. But I have noticed there are many ways to "play games" with the selectivty and choose quality for time tradeoffs. By cheating with margins and using a reduction factor of 3, we can make our program "iterate" very fast. I actually self tested the super fast version against the boring slow version and got an almost dead even result after several thousand games at various levels. I would appreciate any insights you guys have about these tradeoffs too and more details on what you folks do. P.S. Dan, here is what I do with our move ordering, but everyone seems to have their own variations of this: 1. Hash table move if available 2. All captures (highest victim, lowest attacker order) 3. Killer A 4. Killer B 5. rest of moves in no particular order I only store killers if they are NOT captures, and they must produce a cutoff (as opposed to simply being the best move.) Also, a trick I've used in the past seems to help too, identify losing captures (usually downcaptures of pawn defended material) somehow and place them lower in the list. I don't remember where I put them anymore, maybe right after the killers. This helps some positions a lot but many may not respond. I have not yet reimplemented this. Which brings me to a point the newer programmers should pay attention to. Be sure your perfomance tuning experiments test a lot of positions. It's very easy to draw the wrong conclusions if you only use 2 or 3 positions to experiment with. Also you should take the average speedup or slowdown of each position individually, don't just take total time or node counts. Often 1 or 2 positions will dominate the others in respect to time and distort your perception of the results. I do not use the history heuristic although I used to. I should probably take another look at it in view of Bob's experience with it. Maybe it will pay off when we are searching as deeply as the single processor micro's are :-) -- Don
This page took 0.01 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.