Author: Don Dailey
Date: 18:59:57 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 Hi Stuart, I have problems with PV's. In Cilkchess 1, I implemented MTD(f) and Aske Plaat improved the driver (I was doing it wrong and still getting a small speedup over PVS.) Aske Plaat implemented the PV reporting which basically walked the hash table and picked up the best moves. However I don't think this is a good strategy if you want accurate PV's. Cilkchess 1 had trouble reporting PV's and often the 2nd move would be a silly blunder. This was scary and made us think the search was broken but it solved every problem in our test sets in the expected depth. We won Dutch championship without a single loss out of 11 games and pronounced the search SOUND. We are now are confident it's a PV issue only. But for the tournament we simply did a 2 ply search to get the opponents move and hoped the quality of it was high enough to be a good predictor. We never got blunders but often predicted weaker moves or did not see simple tactics in the prediction. In Cilkchess 2.0 I implemented the PV again using the same technique. At the Dutch this year we kept predicting these horrible moves for our opponents and basically rarely got to think on the opponents time. Our hash table was broken too and we operated with 1/16 of the hash table we could have used and this may also affect the PV thing. We lost a game and could only manage 2nd place with all that hardware and our PV implementation is partly to blame (and the fact that the program basically sucks!) We tried to fix the PV problem in the middle of the tournament, mainly by paying attention to "beta." We have no Alpha in our search and beta is equivalent to alpha (and beta) in other programs. We did some hack to make sure we did not change the 2nd move in the hash table unless the score is properly bounded. On my list of "things to do" is to experiment with this in general (not for PV reasons) to see if there are conditions under which you should or should not change the best move in the hash table. The end result seemed (this is a subjective judgement) to be an improvement and in 1 game we actually predicted almost every single move of the opponent, having 45 minutes on our clock at move 60 while the opponent had to reset for speedchess (they allow this in this tournament.) I thought the problem was fixed for good but in the next few games the bad behavior reared it's ugly head again but seemed much less severe. All of my non MTD programs had sound PV's to the best of my knowledge. I am soon going to implement PV's the right way and tackle this problem. Essentially a PV is just information passed toward the top of the tree (the root node) in recursive fashion and is trivial to implement. I don't know what problems I will find but I intend to get it right. I will definitely post my results if you find it interesting. MTD(f) is hell bent on not doing any more work than necessary and causes problems with PV's but I don't think they are unsolvable. I definitely want sound PV's. I mentioned there were things about MTD I didn't like and this is only one of them. I would love to throw it out completely and actually tried to, but could not even come within 15% of matching its performance. It's really quite powerful on the serial as well as the parallel program. Unless you are a performance freak (which I am) don't use it! - Don
This page took 0.01 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.