Author: Vasik Rajlich
Date: 06:15:17 07/16/04
Go up one level in this thread
On July 16, 2004 at 07:24:28, Fabien Letouzey wrote: >On July 16, 2004 at 06:33:20, Vasik Rajlich wrote: > >>There is one interesting caveat in comparison to PVS. A PVS engine has the >>choice to treat null move as any normal move, or to require that the null move >>fails high. (ie within bounds, but not fail high, is not enough) The latter is >>somewhat logical, and IIRC this is what Crafty does. > >I think it's much more than somewhat logical!!! > >IIUC, you are talking about allowing null moves in the PV (in PVS). > >Imagine a PV node where null move gets the best score (inside of the >window). That means passing is the best option, which is the >characteristic of Zugzwang positions. They are exactly the positions >in which you don't want to try null move :) > >One of the reasons why null-move pruning is safe is that it is only >"kept" in incorrect lines, never in the PV. > Well, if you're right, then the conclusion is that MTD (f) is not compatible with null move. However, I am not sure that there is anything special about the PV. 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? Anyway, I am not sure what the answer is. It can only be tested inside a PVS engine. 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) >>An MTD (f) engine must treat a null move as a normal move. I couldn't come up >>with a way to circumvent this restriction. It seems to be an inherent >>restriction of the MTD (f) search. > >>Another way to look at this: an MTD (f) engine must accept null moves along the >>"pv", where "pv" is defined as following the fail-high moves, and >>highest-scoring fail-low moves. > >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. >>Vas > >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. Vas >Fabien.
This page took 0.09 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.