Author: Tom Likens
Date: 20:48:19 02/10/03
Go up one level in this thread
On February 10, 2003 at 23:12:57, Russell Reagan wrote: Russell, Comments are interspersed below :) >On February 10, 2003 at 22:53:47, Tom Likens wrote: > >>A fail-low is the converse situation. It indicates that the true >>value of the position is less than the lower bound we set (i.e. alpha). >>This can be trouble, because the search is telling us that it sees a >>problem, but it doesn't know know the true extent of the problem. >>Usually, this situation needs to be resolved. Most programs will spend >>extra search time trying to obtain the real score and hopefully find >>a better move. > >I always hear people saying "Program X is failing low" in live computer chess >events, or when a programmer is talking about a game, "My program failed low >after move 31." Is the human just guessing that the program failed low, since >it >is taking an unusually long time? Or is there something in the program to tell >them this? If so, is this only at the root where you detect a fail-low as a bad >thing? It would seem ridiculous to double the time every time a node somewhere >in the tree got a score back that was less than alpha, or maybe I overestimate >how often it happens. So are we talking about "at the root" fail-lows, or >interior fail-lows? Normally, the fail-lows reported by the programmers are root fail-lows. The main indication to the programmer, is that the score returned by some iteration of the search is less than the lower window bound initially set at the root. A lot of programs will print out a "--" symbol or some such indicator to show they are failing low, (fail highs will get a "++" symbol or something similar). Fail-lows *inside* the tree are handled differently. And as you rightly pointed out, doubling the time at every internal node that failed low would be a good way to get a never returning search. Internal fail lows occur when every node below the current node being searched failed high and then returned. An internal fail-low gives us an UPPER bound to store in the hash table. One interesting thing to note for these nodes, is that there was no best move found by the search (every move tried failed high), so on an UPPER hash match you should not try to use the stored hash move since it will be invalid. >>This can happen at the root if the program is searching the initial >>position with a +/- window around a presumed valid score instead of >><-INF,+INF> (the so-called "aspiration search"). You could avoid this >>problem altogether by using <-INF,+INF> as your initial alpha/beta >>bound, but the total search time on average would take longer. > >When you say "You can avoid this problem..." above, do you mean that the program >will search each root move with a window of <-inf, +inf>? That would seem to >defeat the purpose of alphabeta and make your search go 36x as long on average. >So, the other alternative I see is that you mean to do the initial search with >something other than a <-inf, +inf> window, and I've always seen people use >infinite windows when they start the root search. Could you clarify what you >mean please? I'm confused :) Only the root position gets the <-INF,+INF> bounds. All the other bounds internally are handled in the normal way by the search. Alpha/beta is still perfectly valid if you initialize the root window to +/- infinity, you just won't get the artificially inflated cutoffs of a bounded initial window, but you *will* get the main benefits of the algorithm. One way to handle this (among many of course), if you use an iterative deepening search (at the root), is to search the first couple of shallow iterations with an infinite window and then use the score returned as the center of subsequent aspiration windows. Sorry, for the confusion. regards, --tom
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.