Author: Bruce Moreland
Date: 13:37:48 07/20/99
Go up one level in this thread
On July 20, 1999 at 15:06:25, Don Dailey wrote: >I got tired of dealing with the MTD problems with Cilkchess and spent >a signficant amount of time creating a version with a good PVS >implementation. I was highly motivated to make this work and the >effort is what convinced me that MTD was better, certainly at least >for me. I actually didn't want to use MTD and was looking for a good >excuse not to. > >The version I had could switch between MTD and PVS with a simple >command line switch and I ran timings with all sorts of positions. >When I tune and do timing comparisons, I use a large set of positions, >not just a single one. I mention this because I have seen people do >this and draw conclusions based on it. What stood out was that MTD >was pretty consistantly faster (less nodes) to do a given search. >Occasionally PVS beats it but not often. Yes. With a single position I think that you run a high risk of achieving a local optimum that has minimal relation to the truth. My evidence for this is simply common sense, which I think is good enough in this case. I use LCTI to do speed tests, since it has no mates, has both tactical and positional problems, and has both endgame and middlegame positions. I think that this is probably still not good enough, since I've notice wide variation between parallel runs due to search indeterminism. If I can get repeatable results with a single version the odds that I can compare two versions properly are low, I think. But it's better than guessing, and I take my results with a healthy degree of skepticism. >But what really stood out was that I was expecting the difference to >be trivial, after all I was comparing to a good PVS implementation. I >really don't remember the exact numbers, but it was substantial and >way too much to ignore. It was over a 15% speedup. > >If I used MTD with NO lazy evaluation versus PVS with lazy evaluation, >PVS would be a win because lazy evaluation is a big win. If you >measure improvement by the number of nodes needed to do a given >iteration then MTD is a big win there is simply no question about >this, certainly not with Cilkchess. Lazy evaluation is a nodes per >second optimization and I have no reason to believe it would suddenly >not work with MTD. MTD is simply another kind of aspiration search. I'm not sure first that I'm understanding why you can't use lazy eval with MTD. Is it because you trash your hash table and get search instabilities? If so, that sounds like a serious practical problem. I'm not sure why it's fair to factor out lazy eval. My own goal here is not to do the fewest nodes necessary to reach depth D, my goal is to get to depth D in the least amount of time. And if PVS + lazy eval < MTD, I'll take PVS + lazy eval. I'm not dismissing MTD though, certainly. >I did implement lazy evaluation the right way with Cilkchess and I do >get big speedups, I don't think MTD has anything to do with this now >that I know what I was doing wrong. But I haven't actually proved >that I get the same lazy eval speedups. If I still had the PVS code >in cilkchess I would go chase down all these things to but I'm not to >motivated to do this since I have no reason to believe there is any >relationship. > >I talked to Franz Morsch and he also tried MTD and verified that it it >was a speed improvement for his already very fast program. I don't >know the exact detail of his implementation and which of his programs >are now using it, but it was nice to hear this kind of verification >that others are having good results with it. There is always the >possiblity that I simply implemented MTD better than PVS or there are >errors somewhere and I am being fooled. Maybe Vincent is right and it >doesn't work on certain programs because of implementation details, I >can't say that it's right for everyone, all I can say is that it is >right for me. > >It turns out that MTD implentation is actually a big simplification. >All the re-search code and crap suddenly gets simple and all the >details are in the driver routine (which is actually simple too once >you figure it out.) The recursive search is trivial stuff. Lazy >evaluation and PV reporting has to be handled correctly however, but >this is true of any search implementation. > > >I have a primitive program called "Occam" playing on the chess server >now. I don't have any kind of aspiration search in it, just pure >alpha/beta, no PVS, no MTD or anything. I will implement PVS first so >that I can do comparisions. Whenever I finally get around to doing >all of this I'll post some solid numbers over some random positions >and then some with the ECM problems. Cool. >By the way, what is the state of the ECM problems? Is there a subset >of them available that have been culled and de-cooked that are in >common usage? Several of us including you did some preliminary work on this last year. I don't think it went anywhere after that. I use the un-culled set. I think it is fine for trying to measure effective tactical speed. I simply hope that it's large enough that the problems will plague distinct runs equally, still allowing for decent comparison. bruce
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.