Author: Roberto Waldteufel
Date: 18:24:06 07/13/98
Go up one level in this thread
On July 13, 1998 at 13:40:08, Robert Hyatt wrote: >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 >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... Hi Bob, Thanks for the explanation, The extra 30 is a clever idea, and 60 is a good choice for the value of a ply, since it is divisible exactly by most small integers. I can't help but wonder if there might be a better way of identifying small sets of "singular" moves than the standard method used for a single such move, expanding all those inferior nodes just to discover how inferior they really are. Maybe it would be possible to do something less general, but computationally much cheaper. What I have in mind is some set of "rules" written into the search routine to recognise a subset of those moves that would prove to be singular by the normal method. The rules would not try to get the singular moves in all cases: it would be allowed to miss some singular moves, as long as it never flagged a move as singular when it was,t really. The rules would be purely based on the current board position at the node in question. A good example might be the racapture of a piece that has just captured a friendly man next to the king in the case where the only recapture is with the king. This could be detected very easily on the fly without searching the other moves that would ordinarily be pruned by alpha-beta. There are many other cases that could be quickly detected from the position. Pawns on the 7th rank might be another good candidate for this approach. If the rules covered enough of these special situations, they might become a viable alternative to the method of searching the remaining (bad) moves, albeit with reduced depth. With careful design, the rules could easily be added to over time. What do you think? Roberto
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.