Author: Vasik Rajlich
Date: 10:40:52 07/16/04
Go up one level in this thread
On July 16, 2004 at 12:13:25, Fabien Letouzey wrote: > >On July 16, 2004 at 11:36:06, Vasik Rajlich wrote: > >>On July 16, 2004 at 10:21:25, Fabien Letouzey wrote: > >>>I am used to problems due to segmented-window algorithms (aspiration, >>>PVS/NegaScout, the MTD family, ...), but this null-move topic seems >>>somewhat independent! > >>I did quite a bit of thinking about this. Generally, the more segmented your >>algorithm, the less flexibility you have in dealing with this (and similar) >>issues. > >Also the more inconsistencies that must be dealt with. > >>In plain alpha-beta, you could set any criterion for a null move that you >>wanted. (Ie you could require any score for the null move to be accepted.) In >>PVS, you can set your requirement for a null move anywhere inside your window, >>and you advocate that that required score should be at the very end of the >>window. In MTD (f), you have no choice. (That I can see.) > >>Note that null move will end up in your PV (if you treat it as a normal move) in >>more than just zugzwang cases. Imagine the following: white can sacrifice a >>piece with Bxh7+ Kxh7 Ng5+ Kg8 Qh5, with a mating attack. Black can delay this >>by throwing away a piece with .. Bb4+ axb4, and then he can play a null move >>which exhausts the available depth. The final score for the variation is roughly >>equal - and this could easily be your PV. Every move is "best" - right down to >>the final null move. > >You are right of course, thanks for correcting me. > >>There is no doubt that having null moves in your PVs will cause some problems - >>but it will also save some nodes. That's the general null move tradeoff - the >>question is if the balance is different along the PV than outside it. Basically, >>MTD (f) forces you to be more aggressive with your use of null move. > >>I think there is a big practical difference between MTD (f) and PVS: in MTD (f), >>you are always failing at the root. PVS is also segmented, but in practice the >>general case is that you don't fail at the root. In those cases, the bounds >>passed to your search are usually the "true" bounds. This could be useful >>information. In fact I can't rule out that this gives PVS a decisive advantage. > >Actually in PVS I think of every PV node as a root. If PV nodes really are >different (as they seem to be regarding move ordering), that would justify doing >other things differently as well. > Do you mean that you order moves differently at PV nodes? I guess I should take a look at your code. It doesn't sound like a bad idea. >As for the "true bounds", Tord mentionned that he used some form of "aspiration" >together with MTD(f). The guess part of aspiration can obviously be applied to >any algorithm and he makes some decisions during the search depending on those >values. So I am not sure about the "decisive advantage" although I don't like >the idea of MTD(f) at all. Maybe Tord found something interesting. In MTD (f) you do have root aspiration values, but these don't seem that useful. > >>It shouldn't be too hard to collect a "true PV" for and MTD (f) engine, although >>it would be overhead and only appropriate for debugging. Anyway I am in the >>middle of a massive re-write so this test just goes on top of a growing list ;) > >Let us know of the result! My guess is that you will never notice any blunder >because of it, although it might occasionally appear in the PV. > >>Note that a PVS engine should behave in the same way, if you allow it to. (Ie >>rather than doing a null move search at beta, do it at alpha, with a possible >>re-search at alpha-beta.) > >I thought that's what you meant above, or are you going MTD(f)? ;) PVS with MTD (f)-like driver. My first engine was MTD (f), and I hope that tests will justify using small/zero width windows in at least some situations. Note that MTD (f) is a degenerate case of PVS. > >>>Hence the question "does doing things more correctly in only a few >>>nodes make any difference?" :) > >>As mentioned above, it's possible that the difference is not trivial. > >It's just "forward pruning at exact-score nodes" but I don't like the sound of >it for some reason :) > >>Vas > >Fabien. Vas
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.