Author: Robert Hyatt
Date: 12:59:21 09/04/02
Go up one level in this thread
On September 03, 2002 at 12:44:35, Vincent Diepeveen wrote: >On September 03, 2002 at 06:12:26, Uri Blass wrote: > >>On September 03, 2002 at 05:29:37, Omid David wrote: >> >>>On September 02, 2002 at 20:37:35, Vincent Diepeveen wrote: >>> >>>>On September 02, 2002 at 13:42:18, Omid David wrote: >>>> >>>>>On September 02, 2002 at 13:34:16, Robert Hyatt wrote: >>>>> >>>>>>On September 01, 2002 at 17:08:58, Omid David wrote: >>>>>> >>>>>>>On September 01, 2002 at 12:08:21, Uri Blass wrote: >>>>>>> >>>>>>>>On September 01, 2002 at 11:55:32, Vincent Diepeveen wrote: >>>>>>>> >>>>>>>>>On September 01, 2002 at 10:20:08, Uri Blass wrote: >>>>>>>>> >>>>>>>>>if you search for aske plaat you will find his stuff on >>>>>>>>>mtd online probably. i'm amazed that you don't understand >>>>>>>>>that Frans is using nullmove. >>>>>>>> >>>>>>>>I know that he is using null move but I do not use null move when I search the >>>>>>>>line that is in the previous pv because I consider it a waste of time. >>>>>>>> >>>>>>>>Null move is for prunning illogical lines. >>>>>>>> >>>>>>>>The pv cannot be illogical line so the only case when I can save nodes by null >>>>>>>>move pruning when I am in a pv line is when the position is zugzwang. >>>>>>>>In other words I can save nodes only if null move pruning is wrong. >>>>>>>> >>>>>>>>I understood that MTD says that the pv may be wrong but the first ply of the pv >>>>>>>>is always right so it does not make sense to prune after Nc6. >>>>>>>> >>>>>>>>Uri >>>>>>> >>>>>>>It depends on what you want; if you want "the first move, only the first move, >>>>>>>and nothing but the first move", then use MTD(f). But if you also want the PV >>>>>>>(as most of us do), avoid it. >>>>>>> >>>>>>>The use of null-move pruning follows the logic behind each method: In MTD(f), >>>>>>>you only want the first move, so you are free to use null-move pruning even in >>>>>>>the PV, something you shouldn't do in regular NegaScout/PVS. >>>>>> >>>>>>You are not thinking this thru clearly. null-move on the PV makes perfect >>>>>>sends. You are searching one ply different. It might suddenly change things >>>>>>in a significant way and null-move is the fastest way to dismiss a bad line, >>>>>>whether it was part of the PV from the previous iteration or part of some >>>>>>non-root move that is hopeless. >>>>>> >>>>>>You should try it in a program, doing it everywhere and only doing it on non- >>>>>>PV searches. I think you will be surprised. I was. The comments in main.c >>>>>>should explain when I made this change myself after someone (Bruce I think) >>>>>>suggested it and testing proved him correct. >>>>>> >>>>>> >>>>>> >>>>>>> >>>>>>>P.S. >>>>>>>Aske Plaat first introduced MTD(f) in his 1995 article "An Algorithm Faster than >>>>>>>NegaScout and SSS* in Practice" available at >>>>>>>http://www.cs.vu.nl/~aske/Papers/hk.pdf >>>>>>> >>>>>>>For a more intuitive explanation, look up http://www.cs.vu.nl/~aske/mtdf.html >>>>>>> >>>>>>>Plaat suggests that MTD(f) is faster than NegaScout, but he researched only >>>>>>>fixed-depth full-width trees. I haven't seen any publication concerning MTD(f)'s >>>>>>>behavior in variable depth trees (e.g. using null-move pruning). >>>>>> >>>>>> >>>>>>I suspect it is "break even" once you get it right. NO way to avoid at least >>>>>>two searches, and, in general, more than that. Which means that with a program >>>>>>with a complex evaluation, the researches are going to cause problems and make >>>>>>it catch up to PVS or even pass it. >>>>>> >>>>>>I think that for normal programs, they should be equivalent if they are both >>>>>>implemented with the same skill and development time. >>>>> >>>>>Actually I think MTD(f) needs more time for fine tuning. For example, you have >>>>>to adjust the evaluation function to a good degree, since the behavior of MTD(f) >>>>>can change to a great extent depending on the eval function; while PVS isn't >>>>>that dependant on the eval function. >>>> >>>>It is the opposite. MTD works for idiotic random tree searches (especially >>>>not having a qsearch like in aske's experiments that's the case). >>> >>>This confused me for some time: didn't Aske use at least qsearch? He speaks of >>>fixed-depth full-width trees, but even there (in such a brute-force framework) >>>lack of qsearch doesn't make sense. What's the point if I capture your piece and >>>don't see the recapture in the next ply... >>> >>> >>>>Also >>>>for programs who are very bad in ordering moves and have huge overhead >>>>otherwise to determine a good PV (which i get with PVS directly out of >>>>hashtable already, like if score drops it doesn't take that much >>>>time here for example, where others take ages when score drop which >>>>i explain by a program that needs too much overhead). If you have pawn = 32 >>>>then MTD works great of course. >>>> >>>>If you have pawn = 1 it works EVEN better. >>>> >>>>the more silly your evaluation the better. of course major bugs which cause >>>>big deviations in evaluation are not very good. >>>> >>>>However fritz is well tuned. >>>> >>>>But by far best working is just returning material >>>> pawn=1 >>>> knight=bishop=3 >>>> rook=5 >>>> queen=10 >>>> >>>>try it with these piece values. then compare all algorithms. you'll see, >>>>MTD will outperform *anything* with simple evaluations. >>> >>>With simple evaluations (material only) I think you are right. Such experiments >>>will be closer to Aske's ones. >>> >>>Once I worked for some time on the MTD(f); my major problem was the odd/even >>>problem of the evaluation function. Although using the value of two plies ago >>>(instead of last ply) minimized this problem, I still got better results with >>>the PVS. Well, but maybe I didn't spend enough time on that... >> >>I prefer not to work about something that can cause me to lose information and >>it is not clear if it is better. >> >>Not having correct pv is losing information. >> >>Even if Vincent is right and MTD(f) is good for Movei of today because of it's >>simple evaluation I still prefer not to try it because I expect my evaluation to >>be changed in the future and I do not like the idea of working on something only >>to undo it later. >> >>Uri > >I do not know how you program, but switching diep from PVS to MTD >used to be a single flag. I'm not lazy evalling nor forward pruning, >so there didn't change much in qsearch either for me. Sincethen i >ignored the #define and i wold need another few minutes of modifications >to test again with MTD. It's real simple. > >We talk about a couple of tens of lines only. Then your mtd(f) implementation is horrible. There are _lots_ of differences between a pure PVS program and a pure mtd(f) program. Which I suppose says a lot about why you didn't like mtd(f) very much... Just hunting for the true score at the root is more than a few lines of code. Then there are the hashing issues with upper and lower bounds and best moves...
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.