Author: Robert Hyatt
Date: 08:29:56 12/03/02
Go up one level in this thread
On December 02, 2002 at 22:46:50, Bob Durrett wrote: >On December 02, 2002 at 22:33:14, Robert Hyatt wrote: > >>On December 02, 2002 at 18:01:00, Bob Durrett wrote: >> > ><snip> > >>>(2) If a chess-playing program were optimized to display multiple lines, would >>>the search algorithms and position evaluation code be any different from those >>>of a chess engine optimized for one move [and it's line] only? >> >>Probably not. But alpha/beta is not designed to produce anything other than >>the "bst" move... >> ><snip> > >I hope I am not asking another "How Do You Do Brain Surgery" type question, but: > >If you don't mind, would you please quickly think up a GENERALIZATION of >alpha/beta which would do what's needed here? I am hopeful that you will >present a broad outline of it here as soon as you can. > >: ) : ) : ) : ) : ) : ) : ) : ) : ) : ) : ) : ) > >If no such algorithm could POSSIBLY exist, then why not? Within the framework of alpha/beta there is no way to do this. Why? Because alpha/beta doesn't search the entire tree. It searches the first branch at the root, for the score, then it uses that score to prove that the other root moves are worse, without proving exactly how much worse they are. And therein lies the problem. To get the second best move, you don't just prove that it is worse than the best, you have to search it completely to see exactly how much worse it is, and that drives up the time exponentially. > >If that is too much to ask, then could you please instead present some offhand >thoughts about what sort of search algorithm might be worth considering for this >application? > >Bob D. Classic best-first doesn't have this problem. Unfortunately, it can only search 1/2 as deep, which is the problem...
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.