Author: Fabien Letouzey
Date: 07:21:25 07/16/04
Go up one level in this thread
On July 16, 2004 at 09:15:17, Vasik Rajlich wrote: >On July 16, 2004 at 07:24:28, Fabien Letouzey wrote: I am starting to get your point (I'm a bit slow). Interestingly it seems to apply to plain alpha-beta as well, which never uses any re-search (and no PV node in my terminology, all nodes are treated in the same way). I am used to problems due to segmented-window algorithms (aspiration, PVS/NegaScout, the MTD family, ...), but this null-move topic seems somewhat independent! >Well, if you're right, then the conclusion is that MTD (f) is not compatible >with null move. 1) We know that null move does not work in Zugzwang positions (among others). 2) With some algorithms (alpha-beta, PVS), we can detect *some* (as in "extremely few") cases of Zugzwang when the null-move score is the best AND inside of the window. So one way of seeing your point is "why bother detecting it in only some cases?". Indeed I expect the change to have no effect at all in practice. At the same time I can't see any benefit from doing it, as we know "in advance" that the heuristic does not work in those cases. The last word in my case is that I certainly won't allow illegal moves in my PVs :) For MTD(f) and other "heavily-segmented-window" algorithms, it's simply not possible to detect those cases anymore. Still the impact should be neglieable, so I don't claim that "MTD(f) is not compatible with null move"! >However, I am not sure that there is anything special about the PV. Probably not, except when displaying the PV is important (analysis, debugging ...). >Let's assume that you have a PVS engine which treats null move as you advocate, >and also doesn't check for mates after a null move. (Otherwise the example will >need to be more complicated.) A position arises where white, to play, has a >winning combination Bxh7+ Kxh7 Ng5+ Kg8 Qh5 and black cannot stop mate. At depth >X, your engine searches this variation, plays a null move for black, runs out of >depth, and the score is outside the A-B bounds. Are these sorts of variations >really less important than variations which end up inside the PV? You can even take alpha-beta as the algorithm, since this avoids additional issues. >Anyway, I am not sure what the answer is. It can only be tested inside a PVS >engine. Me neither but thanks for bringing this subject, I will certainly spend some time thinking about it. >One more note: aspiration search is a less extreme form of MTD (f). If your >search returns from the first window with a (root) fail-high or (root) fail-low, >you may end up with a null move in your PV. (unless you ignore information from >the hash table during the re-search) Indeed I make no difference between aspiration, MTD(f), etc ... when reasoning about a single node. I call them "segmented-window search algorithms". The same even applies to NegaScout. Also yes, there are plenty of ways one can do things differently at PV nodes in PVS but it seems a common opinion is that it is a bad idea. >>I think it's more complex than this. Eventually the PV is made of two >>"semi-PVs" (one failing high and one failigh low) that must agree on >>the score. There can't be a null move at the same place in both, >>since the null move can only fail high in its own node (contrary to normal >>moves). >Yes, true. The MTD (f) "pv" consists of following the highest fail-high at each >node. It has the additional property that each node along this PV will have also >failed low during the search. Anyway, an MTD (f) engine may end up with null >moves along the PV. Yes. My point was that since the second "semi-PV" cannot have a null move at the same place, the PV (= sequence of optimal moves) has to be truncated at that point. Now I realise that you are talking about collecting the PV from the transposition table whereas I always use the model of collecting the semi-PVs using additional memory and then computing the true PV from them. It should not make any difference in the conclusions though. It would be interesting to know how often (if at all) MTD(f) engines encounter null moves in the main line. Unfortunately I expect most of them not to store a move at all in case of a null-move fail high (but keep the previously-known best move instead) AND getting the PV from the transposition table. In that case there is no way of knowing ... >>Note that I am not a MTD(f) expert, but very interested in reasoning >>concerning the PV. >Yes, same here. Of course, a lot of "search conclusions" are not reflected in >the PV. Hence the question "does doing things more correctly in only a few nodes make any difference?" :) >Vas Fabien.
This page took 0.01 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.