Author: Don Dailey
Date: 21:12:53 02/24/99
Go up one level in this thread
On February 24, 1999 at 19:16:27, Bruce Moreland wrote: > >On February 24, 1999 at 15:37:58, Don Dailey wrote: > >>My program is a mixture of static rules and null move. I do null >>move when I have significant depth remaining, but when I am near >>end nodes I do a simple static attack analysis. This has proven >>to be a significant improvement to my chess program. It is faster >>than null move and slightly riskier, but the net affect is >>a stronger chess program (for me.) Even though it's probably >>riskier, it does pick up things null move will miss although the >>converse is also true. > >Can you describe this or give examples please? I know that some people do this >but I haven't the vaguest idea how it works. > >bruce Ok, I'll describe it. There is nothing about it that is particularly sophisticated, it's just another variation on a theme. Essentially, it's a lot like a Static Exchange Evaluator but with simplifications. What you are trying to measure is of course whether the side to move is likely to lose any material, so you can take some liberties that SEE might not take. You only apply this routine (I'll call it the static selectivity tester) when a call to eval is already above beta. I do this anyway when determining whether to do a null move search. But I think it's more important to do it with this tester. Now you must evaluate the attack potential of the enemy or side NOT to move. The dumbest and simplest test, which works pretty well but is far from optimum is to consider the highest piece that is attacked and take some fraction of it's value. Something like 2/3 is appropriate. As an example, if a queen is attacked, you are making the assumption that it will be lost, but that you will recover 1/3 of it's value. Before I continue, I would like to share a little history of how we came up with this idea. One day me and Larry Kaufman were lamenting the appearance of new programs that used some kind of unknown selective search and seemed to benefit from this. We of course did not have a clue about how this was done. We tried a lot of stupid stuff and of course none of it worked very well. But Larry made the observation that the queen was pretty good at taking care of herself, and that even when it was hopelessly attacked, you could almost always get a piece back for it. Generally this involved simply taking the piece that was attacking the queen. Since the queen was the highest valued piece other than the king, he asked me, just for fun, to implement a rules that said IF you are not in check, and your current STATIC score is 6 pawns above beta, just prune the move out of the search. I implemented it, we measured a nice little speedup (nothing huge) and he tried a bunch of problems, and we solved every one of them in the same depth we normally would. We started to get excited and then we run a bunch of self-test games. Our new selective version proved to be a modest but noticable improvement. We were elated. But then I said to Larry, why not look first to see if the queen is even attacked? One thing led to another and we started implementing all kind of rules, noticing what was attacking and what was defending this or that. Before long we had a full blown selective search program which became RexChess. We didn't know what the other guys were doing, but we had stumbled on the right principle ourselves. Looking back, it almost seems that we were stupid not to pick this up before, but this is always the case with new discoveries. They seem almost trivial once you have the benefit of hindsight. Of course the basic principles were discovered by others well before us, but we were forced to figure them out on our own since no one would tell us what they were doing. So most of these ideas evolved from this work. To continue on, the next step is to do this test on the largest piece that is attacked and work your way down. If you determine that a piece is attacked, you take 2/3 of it's value and test this against beta. For instance if a knight is attacked, consider it 2/3 of a knight etc. There are a few rules to determine if something is attacked, You can simply use SEE if you have it, or you can do something much simpler. The very simplest, but of course wasteful, is to consider anything that is under direct attack as being lost. We do this for up-attacks. With down attacks we don't even consider it an attack if the attacked piece or pawn is defended by a pawn. Otherwise we look at the lowest valued defender and do the math. We don't play this out several ply like a good SEE routine might do, we just assume the worst and play it safe. We don't bother to check to see if the defending pawn is pinned either or anything this elaborate. With equal attacks we simply count attackers and defenders and compare them (I think.) In some version we didn't even consider same piece attacks as attacks because if his knight is attacking your knight you can simply remove HIS knight since it is your turn to move. However we feel that this is a bit too risky even though it gives you a nice speedup. We also have some advanced pawn rules, a pawn on the 7th, if not blocked is considered a queen attack. In versions of our programs that do a lot of this kind of selectivity, we have stuff for pawns on the 6th too. Also we have some simple but common mating themes, the most useful one is that if a major piece is attacking a square next to the king with some backup, we go full width. There are a lot of refinements to this and we have tried them all. It ends up being 6 of one, half dozen of the other. It's hard to improve in any substantial way on this basic scheme. You can play with speed vs accuracy tradeoffs until you are blue in the face. The 2/3 number I gave you needs to be tuned. We use a value slightly higher than 2/3, this should be adjusted just so, there is a point where if you use too small a fraction you will suddenly start missing a lot of tactics. We have also experimented with having different fractions for different pieces, but have never demonstrated any real gain for doing this. All of this offends my sense of precision and beauty too, but I just haven't found a way to improve on this scheme which is a hodge-podge of assumptions and hacks. The interesting thing about this for us is that null move selectivity is clearly a big win at deeper levels due to it's superior threat finding ability, but near leaf nodes of the main search, this always ends up being better. I really WISH null move "all the way" was best (for us) because it's certainly a cleaner way to do things. You might try using this with Ferret just to see what happens. Run your SEE routine to get a tactical score and try using 2/3 of the value returned (on the 2 levels just before the quies search instead of null move) just to see what happens. Probably you've hacked and tweaked your program to do whatever it does very well already and this might not be an improvement for you, but then again, maybe it will be. I said before that this sometimes picks up things a real null move search might not. This is mainly a side effect and serendipitous because my routine sometimes makes a conservative assumption and goes full width where a null+quies might not. Rex was built on this whole idea, no null move at all. In its day it was considered a very FAST program. The earliest version of Socrates that won the 1993 international championship was my LAST program that didn't use null move pruning and it also used this kind of selectivity since we were not yet willing to try null move prunning. I ported this program over to Unix and play with it occasionally and I am still impressed with how fast it is, it does this kind of selectivity on the last 4 levels of the main search, like Rex does (or maybe Rex does 3 ply of this, I'm not positive.) I would love to make the executable of this program public domain if it were not for the fact that I do not OWN it! It beats every public domain programs out there pretty easily and it also beats the current serial CilkChess on a 32 bit machine. It's still a good program even without null move prunning. I think null move prunning would improve it however. I think there are probably several modern programs that use some version of this static based selectivity, and Rebel is one of them. Rebel may not do it anything like we did, but it shows that there is more than one way to skin a cat! - Don
This page took 0.2 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.