Author: Tim Foden
Date: 09:29:21 08/05/00
Go up one level in this thread
On August 05, 2000 at 11:37:01, Larry Griffiths wrote: >Which Algorithm is considered the best now-adays. > >NegaScout? MTD? PVS? Others? I am looking to implement one of the best search >type algorithms in my program. I would like to get it into the 2000 rated range >as this has been my lifetime goal. Then, maybe install winboard or something so >it can compete against other programs to get a rating. >I dont like MTD as it seems to be complex. It is generally possible, and I would say advisable, to implement the search in small steps. Get one version working before moving on to the more complex version. Thus the searches you mention above, plus plain A-B search, can be ranked in order of implementaion: 1) Alpha-Beta 2) PV-search 3) NegaScout 4) MTD(f) To get from 1) to 2), you need to implement null-window search for non-PV lines. To get from 2) to 3), you implement the safe forward pruning near the leaves, or use razoring if you have extensions. You might want to switch 2) and 3) around. To get from the 3) to 4) you add the MTD(f) driver on top of the whole thing. The thing to remember about MTD(f) (if my memory serves me well) is that I think it requires a fail-soft version of the underlying search. Fail soft is: when you detect a cut-off (value >= beta) you return (value). Fail hard is you return (beta). At some point it would be advisable to implement the Null move heuristic. All of this is from some hazy memory, so please forgive me if I turn out to be talking nonsense. :o) BTW, I don't necessarily think you need the "best" search algorithm. Just a good one. I really don't think MTD(f) is a requirement to get a program that is 2000 (or even 2500) rated.
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.