Author: Tord Romstad
Date: 15:25:34 01/14/04
Go up one level in this thread
On January 14, 2004 at 16:56:20, Anthony Cozzie wrote: >On January 14, 2004 at 16:26:42, Ed Trice wrote: > >> >>> >>>Have you considered trying MTD(f) instead of PVS? I am not sure it is any more >>>efficient in practice, but it is easier to code, and has the additional benefit >>>of making you feel different, original, interesting, intelligent, handsome and >>>attractive. >>> >> >>Well Aske Plaat would love to hear that :) >> >>But doesn't MTD(f) trigger a great deal of researches? I remember trying that >>once and it bloated the tree. > >---- opinion mode on ---- > >MTD(f) has two big problems. > >1, you ponder the wrong move occasionally because your PVs are less accurate. >If you are pondering the wrong move 20% of the time that is equivalent to a 10% >time loss. This is not a *big* problem by any stretch of the imagination. It does indeed happen that the last few moves of the PV are wrong or missing, but I have *never* seen as obviously wrong move as the second move of the PV. This does of course not mean that it never happens, but it is clearly very rare. On the other hand, it *does* happen that the PV contains only one move, and there is no move to ponder at all. This happens maybe once every 5 or 10 games, but usually when the game is already won or lost. >2, MTD(f) is at its worst when the score is dropping. A fail high in MTD(F) is >much faster than a fail low (1 child node vs all child nodes). This is true. The average branching factor is clearly lower when the initial direction of the search is downward. >Unfortunately, >this is when you need your search the most: you are in trouble, and you need to >make exact moves to win/draw (you might already be lost, but thats just the way >it goes). Most of us extend the thinking time in such situations, and try to avoid making a move before the search fails high. By the way, there are a few things you could try to solve the problem you describe, although I haven't yet tried them. The main idea is to give up quickly if the search appers to fail low. The easiest thing to do is to just abort the search if the first move at the root fails low, and immediately start a new search with a lower search bound. It is certainly possible to find refinements to this idea, but as I said I haven't experimented with it yet. >I remember some Zappa-Gothmog games where Gothmog had been searching >8 ply, got in a tight spot, made a 6 ply search, played a huge blunder, and went >from -1 to -5 the next move. It is quite common that the search depth reached varies a lot from move to move in Gothmog (a difference of 3 or 4 plies is not unusual), but usually this is due to DFP rather than MTD(f). A sudden dramatic drop in search depth usually means that most of the DFP is disabled for some reason. And in general, if you want to knock MTD(f), you really need to base your conclusions on something more substantial than games against Gothmog, which undeniably is the slowest, weakest and most buggy MTD(f) engine known to man. Gothmog is nothing but a clown, and although it occasionally shows some entertainment value, it is not a serious chess program and should not be evaluated as such. The situation you describe can be observed in about every second game played between a fast, strong engine and a slow, weak and buggy one. You cannot make any conclusions about the relative merits of the algorithms used based on such games. > >---- opinion mode off ---- > >Most people that try MTD(f) will give up very fast because it requires a >two-limit hash table rather than a bound hash like most people implement. Most MTD(f) programs use a two-limit hash table, but it is not a requirement. I have also seen PVSers claim that a two-limit hash table works better than a one-limit table for them. >Its a >difference of style, but in my opinion worst case performance is key when for >search. There is some interesting room for work IMHO with MTD(f)/PVS hybrids. There is. It is possible that I will experiment with this in the near future. MTD(f) is obviously not suitable for devices with limited memory, I am therfore forced to evaluate alternative techniques before porting my engine to Palm OS. The next version of Gothmog will probably include the possibility of choosing between MTD(f) and PVS in the init file. There will also be an option to disable all DFP. Acronyms used in this post: MTD(f) = "Memory-enhanced Test Driver with initial guess f" PVS = "Principal Variation Search" DFP = "Dubious Forward Pruning" Tord
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.