Author: Robert Hyatt
Date: 12:35:39 01/22/98
Go up one level in this thread
On January 22, 1998 at 14:28:27, Stuart Cracraft wrote: >On January 22, 1998 at 13:33:42, Don Dailey wrote: > >>By the way, I use an algorithm called mtd(f) and there is no concept >>of a "window" in the search itself (just the search driver.) All >>searches return quickly and are guaranteed to fail! In some sense >>the same moves get searched over and over on the same iteration >>although the hash table tends to avoid most of this work (except >>when it is needed to prove a point.) The search driver is tricky >>piece of code and the obvious approach is quite bad (don't use a >>binary search mtd probe strategy!) >> >>The thing I hate about mtd is the data returned is so different >>from a conventional program. You cannot get a nice list of moves >>showing progress and the pv appears many times (usually modified) >>each time. Even though I have good root move ordering I stopped >>thinking about it with mtd(f). Your ideas almost sounded foreign >>to me because of this! Massaging my root move list would clearly >>be a problem for efficiency. MTD is so good I cannot imagine >>using anything else though. I am getting over 15% speedup over >>my very best implementation of pvs search (margin on first move, >>zero width on siblings with research on fail hi's) I prefer >>PVS's behavior but cannot ignore the extra performance of MTD(f). >> >>The (f) refers to the type of driver used. I don't strictly use >>the 'f' driver because I found some enhancements of my own but >>it's basically mtd(f) >> >>- Don > >I tried MTD(f) at one point and was impressed as well. Also, I saw >the tables in Aske Platt's thesis comparing it with other search >techniques for three strategy games. Those tables show really good >speedups for chess. > >Now, the question. I still have my MTD(f) code but it does not >record the principal variation. > >How did you do it? Please be as specific as you can. Now that my >transposition table is working much better, I'd like to consider >re-using my past MTD(f) code. > >15% is nothing to sneeze at. > >--Stuart Note that you have to have a couple of characteristics in your program or you will have big troubles: 1. you need a psuedo-stable evaluation. It can't produce large swings from iteration to iteration. If you do, you get too far off the mtd(f) window and require extra re-searches to get back, only to be too far off in the other direction the next iteration. This killed me because my evaluation can produce significant variations from one iteration to the next (+/- .5 is not uncommon) 2. no extensions depending on alpha and beta values. These cause more search inconsistencies than Carter's has little liver pills. 3. you should modify your hash table to store both upper and lower search bounds, since you will be searching the same tree over and over, and failing high one time, failing low the next. I didn't like it because for me it was slower. I didn't want to constrain my eval to not produce significant variations from ply to ply. And I hated not getting a good PV as it made debugging and testing very difficult. you can get some stuff from the hash table, but not always enough. It has it's place in one type of parallel search. The way I did the parallel search in Cray Blitz it would be totally useless however. I'm a PVS'er for life, probably. :)
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.