Author: Vasik Rajlich
Date: 05:55:18 01/20/06
Go up one level in this thread
On January 19, 2006 at 15:01:04, Joachim Rang wrote: >Hi, > >after a question below regarding the "superiority" of MTD(F) and the article on >Wikipedia about that I decided to modify the entry and added a sentence in which >I question the "superiority" of MTD(f) over PVS since it has "practical issues". >Naturally some guys over in Wikipedia now want to see proof of my statement and >want to know what kind of practical issues there really are. So I have two >questions: > >1.) Would you support the statement that MTD(F) is _not_ superior to PVS and >while save in some circumstances a few % of nodes has "practical issues" which >make it a less desirable choice? > >2.) Could you (briefly) name some of the "practical issues"? > >regards Joachim > >P.S.: If someone feels encourage to reformulate the article on MTD(F) and >Negascout (PVS) more knowledgeable please feel free to do so. ;-) Joachim, you've got the perfect guy to ask on your team - Fabien knows this stuff like the back of his hand. The simplest way to summarize the practical issues is that you don't have true search bounds during node visits. Let me give an example: [D] r2q1r2/pp1n1ppk/2b1p3/N1ppP2p/3P4/2P4N/PP3PPP/R2Q1RK1 b - - 0 1 We want our search to understand that 1. .. Qxa5 is losing here. Now, to make the illustration as simple as possible, let's assume the following: 1) We are doing a material-only search 2) We have a quiescence search of captures only 3) We use no extensions/reductions Finally, in our hypothetical search, we are using MTD (f) and use null move "normally", ie. it only has to fail high. So, at iteration == 7, we start by looking (at the root) for a score of -1 (ie. one pawn advantage for black), and we succeed: move node type depth remaining ---- --------- ------ 1. .. Qxa5 fail high 6 2. Qxh5+ fail low 5 2. .. Kg8 fail high 4 3. Ng5 fail low 3 3. .. null fail high 0 We likewise succeed looking for a score of -2 with the first move 1. .. Qxa5, while failing looking for a score of -3. So, 1. .. Qxa5 is the move, and -2 the score. Of course, in a PVS search, iteration == 7 would be enough to avoid 1. .. Qxa5, because after 1. .. Qxa5 2. Qxh5+ Kg8 3. Ng5 we are not yet doing a null-window search and hence won't allow a null move. (Or allow it only if it fails high above the full root upper bound.) If you think about the problem, it is that during the MTD (f) search, when we reached the node after 1. .. Qxa5 2. Qxh5+ Kg8 3. Ng5, we had no idea that this was going to be the critical node whose score would eventually become the final search score. This is the so-called "true bound information" which MTD (f) takes away from you. In other words, in MTD (f), you don't know what the important nodes are until you have finished the entire search. BTW - as you can probably guess, I haven't totally written off these null-window type tricks, they have their uses. Rybka WinFinder 1.0 uses a 99% MTD (f)-type search, and the latest Rybka versions (ie. Beta 10 & 11) are using some pretty wild null-window-search ideas, you might be able to figure them out a bit from playing around. 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.