Author: Robert Hyatt
Date: 10:40:08 07/13/98
Go up one level in this thread
On July 13, 1998 at 05:07:11, Roberto Waldteufel wrote: > >On July 12, 1998 at 17:08:49, Robert Hyatt wrote: > >>On July 12, 1998 at 13:03:08, Roberto Waldteufel wrote: >> >>> >>>On July 11, 1998 at 21:03:15, Bruce Moreland wrote: >>> >>>> >>>>On July 11, 1998 at 18:49:39, Roberto Waldteufel wrote: >>>> >>>>>I never reduce the depth when the side to move is in check, but I find that if I >>>>>do the same for moves that administer check it sometimes blows my search sky >>>>>high, hanging the machine for an inordinate amount of time. It's a pity, because >>>>>I also found many times that this method discovered long mates as you describe. >>>>>How do you overcome the problem of situations where the number of checks becomes >>>>>excessive, eg a king being chased around the board by a queen that lacks >>>>>supporting pawns or pieces to deliver a mate? >>>> >>>>I'll tell you what I discovered when I messed with this some time ago. I'll >>>>start at the beginning in the off chance that someone else is listening as well. >>>> >>>>The dawn of man extension is to extend when you check. This seems to help >>>>programs along certain tactical lines where the king is in trouble. I do this, >>>>I've always done it, and everything below here assumes that giving check is an >>>>unqualified one-ply extension, that's a constant. >>>> >>>>If you try to be super-aggressive and extend both when giving check, and when >>>>getting out of check, you'll simply blow sky high. >>>> >>>>So if the goal is to try to extend checks more, there needs to be some >>>>constraint to the extensions. An attempt at constraint involves only extending >>>>when you are in check, and have exactly *one* legal way out. This will appear >>>>to work fine in most middlegame situations, and it will completely destroy some >>>>of these long mate test problems. >>>> >>>>It is my opinion that there needs to be some further constraint on this >>>>extension. You'll see some positions bog, sometimes really badly. I'm not sure >>>>exactly why this happens, but your reasons for why it might happen seem good. >>>> >>>>I've done experiments with two ways to constrain this extension. One is when >>>>you only allow it to happen a couple of times along one line, and another is >>>>when you somehow choose to only do this extension perhaps 75% of the time that >>>>the conditions are met for it. >>>> >>>>Either of these seems to stop the bogging enough that your thing can still play >>>>chess while using this extension. >>>> >>>>bruce >>> >>>Hi Bruce, >>> >>>Thanks for your excellent explanation. My mistake was that I had not thought of >>>the 75% factor. This way makes a lot of sense, and I will definitely implement >>>this. I don't think it makes a difference whether the actual extensions occur on >>>the checking ply or the check evasion ply, as long as replies to checks are >>>allways examined full width, so perhaps it would be simpler to do it all at the >>>same node, like this: >>> >>>if side to move in check then >>> if only one legal reply then >>> newdepth=depth+0.75 >>> else >>> newdepth=depth >>> end if >>>else >>> newdepth=depth-1 >>>end if >>> >>>Do you extend any replies to checks that have more than one choice? I can think >>>of one or two interesting cases, like double check, or Bxh7+ when the Black king >>>is on g8 and White has Nf3 and Qd1 (or Qe2). Maybe the 75% figure would need to >>>be different for each case. Have you tried anything like this? >>> >>>Roberto >> >> >>once you do singular extensions, as we did in Cray Blitz, this becomes moot, >>because such a position is obviously "singular" by any definition you would >>want to use. >> >>But as far as working on the "one-legal-response" extension, Peter G once >>suggested, and I tried in Cray Blitz, a modification he called "one sane >>reply." Here there may be multiple moves, but if only one is reasonable >>then you extend that one anyway. An example would be two moves, one moving >>the king to a safe square, the other interposing a piece that can be captured >>for nothing, still leaving you in check. The king move would be extended >>anyway. When I started playing with this, I didn't like it, but later >>found that "singular extensions" was just a general class of these types >>of positions and our singular extensions code worked pretty well, although >>it does have a high cost. >> >>One thing I have planned is to try singular extensions again, using my >>current fractional-ply increment (same algorithm as in Cray Blitz in fact.) >>I had planned to do some further singular extension testing in CB, to see if >>it would be useful to extend on positions where there are many moves but at >>least 2 appear to be "singular" type moves. Extending would be dangerous, >>except that you *could* extend each 1/2 ply instead of 1, or extend each >>of the two 3/4 ply rather than 1... Lots of things to try here, once I get >>singular extensions into crafty. Right now I am staying busy with the SMP >>search, which is certainly non-trivial to get right. > >Hi Bob, > >Thanks for your reply. I like the idea of a half ply extension for two moves >instead of a 1 ply extension for one. In a sense you are restricting the amount >of extension emanating from a node and the sharing it between its most deserving >children. I suppose there is nothing to prevent you also extending, say, one >third of a ply on three moves, or one quarter of a ply on four moves, etc. >Perhaps also the moves might not all get identical extensions. If a sacrifice >has three plausible defences of which one seems more sensible than the other >two, you could extend the most sensible one half a ply and the less >sensible-but-still-plausible two replies each a quarter of a ply. It might take >a lot of work to determine the best ratios for the many possible situations, but >it certainly sounds like an idea with some promise. don't forget this is computationally very expensive... because normally when you get a beta cutoff you just return beta. now you have to confirm that this move is significantly better than the rest, which means searching the remainder of the moves *after* you would normally exit. To find that a "set" of moves is "singular" is even more expensive, but it does seem interesting... > >When you extend a fraction of a ply, how do you implement it? There are two ways >I have tried, but I am not sure which is best. One is to maintain a counter that >loops in a cycle - eg for the 75% extension for the "one legal move" criterion, >I increment the counter, test if it has reached 4, and extend 1 ply if it is >still <4, or reset it to 0 and don't extend when it =4. The other method seems >more sensible to me, but requires a lot more code modification: instead of >reducing the depth by 1 every ply, I reduce it by some larger fixed amount, eg >8. >Then for a three quarter ply extension, I only reduce the depth by 2 instead of >8. How do you do it in Crafty? > >Best wishes, >Roberto I have ply=60 in crafty... When I start an iteration search, I start depth at 90 for a one ply search (really 1.5 if you notice). The two ply search starts with depth=150 (2*60+30). The purpose of the 30 will become apparent soon. Now, so long as depth >= 60, I do the normal search stuff, and when I call Search() recursively, it is with depth-60. So notice that initial 30 has no effect at all. If I find a one-reply position, I increment ply by 45 (3/4*60). Note that this will add to that 30 and now I actually search an extra ply deeper. Because now depth will be a whole ply deeper (suppose it was 90 before the one-reply position, which is the same as "1", but now it is 90+45 which is 135, which is >= 120 which means two plies of search left. If you follow that, here is what might happen: pos initial depth final depth check 90 150 (one ply extend on check) one-reply 90 135 (3/4 ply extend) check 75 135 (one ply extend on check) one-reply 75 120 (3/4 extend) check 60 120 one-reply 60 105 check 45 105 one-reply 45 90 check 30 90 one-reply 30 75 check 15 75 one-reply 15 60 check 0 done, into q-search. check not detected. so you see, the 3/4 lets us extend 3/4 of the positions since the depth is in units of 60, with anything < 60 treated as zero. so what you see happening is that if you have 4 one-reply extensions in a path, only 3 of them do anything. If you have 8, only 6 do anything. You could make this 1/2, so that only every other one-reply extension would actually drive the search deeper...
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.