Author: Don Dailey
Date: 20:59:26 10/05/98
Go up one level in this thread
On October 05, 1998 at 22:28:24, Roberto Waldteufel wrote: > >On October 05, 1998 at 15:38:32, Don Dailey wrote: > > >> >>Another idea I have experimented with is "cheating" on the null move >>test. It works like this: If your static evaluator (sometimes I >>call this the stand pat score), returns a score above beta at an >>internal node, the move is a candidate for selectivity. >>In this case, instead of doing a >>null move search with a zero width window around beta, you can >>do one with a window of beta-n where n is some small positional >>margin. The idea is that you are more likely to pass this null >>move test and the end result is that your program will be much more >>selective. Don't forget you must return a score of greater than >>beta, I just return the stand pat score which I know is above >>beta or I would not be doing the test. You can experiment with >>various margins or make them change dynamically based on depth. >> >>The end results? A VERY fast (and extremely selective) program. In >>practice you will be able to solve tactics on the same depth (but >>much faster) but you will miss more positional maneuvers. I have >>done very thorough testing of various margins and have found this >>a wash so to speak. I cannot prove the program is weaker or stronger. >> >>But I present this idea for those (if any) who have not thought of >>it and want to experiment with it. I view it as another knob to turn >>in your quest for a better chess program. >> >>By the way, I have chosen not to use this technique in Cilkchess. >>In principle it should not matter since as I said you cannot prove >>to me it plays worse (or better.) But my own phychological bias >>tends to make me prefer to error on the side of covering all the >>bases. >> >>If anyone has any experiences or opinions on this, I would love to >>hear about it. >> > >In your experiments, what values did you use for n, and how (if at all) did n >vary with depth? You get speedups right away with very small margins. Where a pawn is 100, you can try values of n like 4 or 8. I always kept this small. I would be uncomfortable with anything more than 1/4 pawn. You should feel free to experiment however. I didn't do any serious studies of varying n with depth, but I would guess this is the way to go. >>---------------- >> >>I might as well explain something else I do that has always proven >>to be a benefit to my programs. I have even tried to throw it away >>but am forced to bring it back since it is clearly an improvement. >>Near leaf nodes of the tree, but still in the main search (not quies) >>it has always payed off handsomely to not use the more dynamic null >>move selectivity. Instead I use my own homemade static routine that >>essentially does the same thing. For programs that have a static >>exchange evaluator this would be a no-brainer implementation. In >>my program, I first determine if the static (stand pat) score is >>above beta > >Do you do a fast evaluation, or do you do the full positional score here? Maybe >you could do a very fast rough evaluation based on material and only evaluate >the positional score if the margin for error is small, ie fast eval-opponent's >threat eval=beta+delta, where delta is the margin for error. If delta turns out >to be large, then the positional score is irrelavent. I use a full evaluation at this point. It won't make much difference unless your evaluator is very slow but you are right, lazy evaluation could be used. But you should take care that your true static score is at least beta before doing this test, so your fast evaluator minus a liberal lazy margin should still be above beta. >> and again consider this a candidate for selectivity. >>Then I determine statically the attack potential of the enemy >>army. This determination is based on what is directly attacked >>and what is defending it. In fact it is not very sophisticated >>at all and simply errors in the favor of being conservative. For >>instance it is much less sophisticated that Bob Hyatt's SEE routine. >> >>Here are a few of the considerations: >> >> 1) If a piece is up-attacked, assume you will "get back" 2/3 of >> that pieces value. (you can experiment with the ratio) > >Do you mean 1/3? In the example given below the queen is attacked by the bishop, >which you asses as a threat value of 6. Is this calculated as 2/3 x 9 or 9-6? If >you mean the first of these, then you are only getting back a third of the >queen. > Sorry, I wrote this in a hurry. I basically consider the ATTACK VALUE 2/3 of the piece attacked. In other words you will get 1/3 back which usually happens in practice. For instance you attack a queen with a bishop, probably the queen can at least capture the minor piece, or another piece can capture something and the queen escapes. If a minor piece is attacked (perhaps 2 minor pieces are forked) it is almost always the case that at least a pawn can be had for your trouble. Even when you are wrong, you are only 1/3 wrong! Of course this can be fatal but so can any selectivity. The bottom line is that this works well and can make your program stronger. The 2/3 number I give is subject to tinkering. There seems to be a "just right" number which is around 2/3 that can be tuned by using a good tactical set. When that fraction gets smaller, your program starts missing tactics, when it gets bigger the program slows down too much. I think the number we actually used might have been 5/8 or 11/16! It probably doesn't matter that much as long as you are above that threshold where you suddenly start losing problems. You may find it useful to use a different ratio depending on which piece is attacked and by which piece. We did a lot of tinkering with our old program and the desciption I give captures the basics but doesn't perfectly describe all our rules. >> 2) If a piece is attacked by a greater valued piece but defended >> by a pawn, assume it is not attacked at all. >> >> 3) If a piece is attacked by a piece of equal value, count the >> attackers and defenders. If there are more attackers assume >> 2/3 of the piece is lost. >> >> 4) Don't forget to consider pawn on the 7th as a big attack. I >> think we even consider a pawn on the 7th as not being an attack >> if the square in front is occupied. >> >>There are lots of opportunities here for making assumptions and >>playing with the degree of risk you are willing to accept. For >>instance the 2/3 figure could be tweaked or even changed dynamically, >>or you could use a more thorough SEE evaluator etc. Also you can >>do some static mate threat testing too if you want to extend the >>idea but it is not necessary (for us) to get a nice improvement. >> >>So basically I apply this static test and compare the attack value >>of the opponents position to our distance from beta. Here is an >>example: >> >>In a white to move position, the program calls the static evaluator >>function and notices that white is 3 pawns greater than beta. >>Presumably white has a great position and would like to stop >>searching. But first we want to know if black has any substatial >>threats. We call the threat detector routine (as described above) >>and notice that white has its queen directly attacked by a bishop. >>If the queen has a value of 9 pawns, then 2/3 of this is 6 pawns. >>Because blacks threat value is 6 pawns and we are only 3 pawns >>above beta, we conclude that the position is too dangerous to >>stop in. If a minor piece had been attacked instead of a queen >>we probably would have taken the cutoff. >> >>Our program still uses null move searching predominantly. It turns >>out that doing 2 ply of this static stuff seems to be the right >>number for us (at last two levels near leaf nodes of main search.) >>If we use more than 2, the program weakens, if we >>use 1 ply of this it's just slightly weaker and if we do not >>do this at all and use pure null move searching all >>the way to then end, the program is clearly weaker. > >Do you think the two pruning methods interact much? I mean, compared to no >selectivity at all, is the null move speedup plus the static pruning speedup >greater or less than the sppedup of the combination of both tequniques together? I'm really not sure. Naturally they both work together since each null move search in the null move selectivity will end with this static selectivity being done at the end. My recollection is that the static stuff does more pruning. You can get away with it near the end nodes of the search since a depth-2 null move reduction is not capable of seeing anything more than immediate threats anyway. Once you are deeper in the tree you need null move to find threats of threats (or indirect threats.) It's probably no secret why using 2 ply of this is the best formula (at least for me based on the way I do things.) >>Our old Socrates serial program that won the 93 ICCA international >>did not use null move at all. We did 4 ply of this stuff, all statically >>based. We had more sophisticated rules and looked at certain kinds >>of mate threats, ones where the king was on the edge and also did >>some passed pawn analysis (pawns on the 6th.) Even though we only >>did 4 ply of selectivity and did not do null move pruning, this is >>the fastest program (in terms of iteration depth and speed) I've >>ever written. I'm still wondering whether null move pruning (as >>wonderful as it is) is the final say. It is certainly not the >>only way to write a very strong chess program. >> >>- Don > >Maybe the absence of null move pruning made it more useful to use your static >pruning technique at more levels in the tree. I imagine the relationship between >the two methods is probably very complex. I remember that we worked very hard to determine the right number of levels to do this at and 4 seemed to be the right number. More than this was too risky and less was not enough to get maximum strength. Of course this all depends on many factors and how much effort you invest on picking up things that can be missed and so on. We could probably do another couple plys of this if we added more rules to cover more mate threats, more passed pawn stuff and perhaps a safety margin at deeper levels (sc > beta + margin before allowing a selective test) among other things. Another thing to make it a little safer is based on what I call "compulsion screening" which is a term I made up. If a high compulsion move (like a check) is made, do not allow that same side to be selective when it is his turn again. In other words, if white gives check and black replies to it, then do not allow white to "stand pat" on his turn even though his score is above beta. It is slightly counter-intuitive because you are used to thinking of the guy who is in check as having to go full width (which of course is true) but just about the most common way for a program to fool itself is for the program to give check when in trouble so that more pressure comes to bear on the selective portion of the tree which of course leads to selectivity errors. The surprising thing about this particular idea is that it is remarkable cheap and will gain you many extra problem solutions. I even use it with null move pruning although of course it is not absolutely necessary. But it is a nice way to cover indirect or even direct mate threats based on checking sequences which of course are common in chess and which null move prunning can miss near leaf nodes especially. >Best wishes, >Roberto I think I've practically talked myself into trying purely static based selectivity again! But null move prunning is pretty powerful and it's hard to believe you can do much better although Rebel seems to prove this is possible. - 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.