Author: Andrew Williams
Date: 03:49:31 09/12/99
Go up one level in this thread
On September 12, 1999 at 00:50:23, Dave Gomboc wrote: >On September 11, 1999 at 23:25:22, Robert Hyatt wrote: > >>On September 11, 1999 at 23:03:25, Bas Hamstra wrote: >> >>> >>>I'm working on it too, based on your advice... I understand the principle: it's >>>cheaper to prove a move is worse than the first move, than to determine it's >>>exact score. >>> >>>You say PVS gives you as least 10% over alphabeta%. Others have reported that >>>MTD(f) gives you at least 10% over PVS (someone mentioned 15%). >>> >>>ab 100.000 nodes >>>PVS 90.000 nodes >>>MDT(f) 81.000 nodes ??? >>> >>>What is your opinion on this? Is there any reason to not do MDT(f) right away? This issue is highly complex. We had a very interesting discussion here a few months ago. All we could really conclude is that you'd have to compare both techniques in the same program to get any real data. I like it. Don Dailey has had some success with it. Vincent Diepeveen doesn't like it. Bob has tried it and has some reservations (see below). I'm sure others here have their opinions too! >>> >> >> >>mtd(f) has its own unique problems. (a) you need a stable evaluation, not >>one that varies widely in the scores it produces. (i) I tend to think that this is characteristic of a good program anyway. (ii) Is "stable evaluation" synonymous with "small positional component"? The jury is still out on that one. >> (b) you have hashing issues >>to resolve, in that you really need to store two bounds, since every mtd(f) >>search fails high or low, and since you keep re-searching after shifting the >>root window... you need both bounds so that when you get a fail-low in a >>position, you can also remember the fail-high that happened when the window >>was different... This is definitely correct. You can't plug in your aspiration/PVS hash table and get any sensible results. Like many hashing issues, once you've got it correct, you leave it alone for a while :-). I think mtd(f) would be more sensitive to an inefficient hashtable implementation than PVS. Another thing is that you probably will want to hash quiescence nodes, so you need a bigger table. >>(c) lazy eval is a killer because you need to use fail-soft >>to get the best bound back to the root, and lazy eval tears this up badly... >> See below. Bob could have added: (d) There are problems with maintaining an accurate PV. You don't have nodes where the score is > alpha and < beta, so you can't build your PV in the normal way. You have to use your hash table to keep track of it. I devised a metric for testing the accuracy of PostModernist's PV and found that on test sets (each one starting with an empty hash table), my PV is pretty good. Its accuracy drops away dramatically during games, however. Because the PV nodes keep getting overwritten. I'm still looking at this. >>so there are lots of problems to solve... I don't use mtd(f) and don't plan >>to do so. Whether you get that 10% depends on a _lot_ of things. When I tried >>this, the best I got was 1/2 the speed of my PVS code... because of my eval and >>lazy exits mainly... I'm not willing to reduce the size of my tree by maybe >>10% with mtd(f) but make my program 2x slower by turning off lazy eval. > >You don't need to turn off lazy eval completely to use mtd() methods. Don >Dailey already explained this in an earlier post. Instead, base early-exit >decisions on the established score range at the root instead of locally. > >Dave I've tried this and this is what I use. But I'm so cautious with it that lazy eval now makes hardly any difference in my program. Oddly enough until the discussion we had before, I was using lazy eval against the test value, and was quite happy with it. Don's idea made me think hard about it and I decided to be more conservative and use the external bounds. But I might have been OK previously, because my lazy margin was so huge. Whatever you decide, Bas, I hope you'll keep us posted. Andrew
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.