Author: Robert Hyatt
Date: 14:49:01 12/03/02
Go up one level in this thread
On December 03, 2002 at 13:09:42, Pat King wrote: >On December 03, 2002 at 11:29:56, Robert Hyatt wrote: > >>On December 02, 2002 at 22:46:50, Bob Durrett wrote: >> >[snip] >>>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. >> >Perhaps there's a middle ground here. You can sort the scores of the fail-lows >at the root, cost O(B^2) at worst, and then probe the hash table for the >corresponding variations. You'd know the PV was worth (say) exactly 314, >variation 1 < 271, variation 2 < 141, etc. As a practical matter, how useful are >those less-than scores? >[snip] > >Pat How can you do that? You don't know _exact_ scores for the moves that failed low. You only know an upper bound on each, as the real scores for each of those moves could be even worse had the entire sub-tree been searched. Fail-low scores don't contain any information that can be compared between them, all they are useful for is to compare against the best move... and we already know and have proven they are worse, just not by how much.
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.