Author: Anthony Cozzie
Date: 17:11:02 01/14/04
Go up one level in this thread
On January 14, 2004 at 18:25:34, Tord Romstad wrote: >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. I base this on my own experiments with Zappa and MTD(f). The exact same scenario happened in a game vs the Baron. Score falls, takes Zappa extends time ilke crazy, still gets only 8 ply in 1 minute (!!) makes bad move, loses. >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. How much RAM does a Palm have? anthony
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.