Author: Fabien Letouzey
Date: 09:13:25 07/16/04
Go up one level in this thread
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. 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. >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)? ;) >>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.
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.