Author: Robert Hyatt
Date: 06:44:46 09/11/99
Go up one level in this thread
On September 11, 1999 at 02:28:00, Ed Schröder wrote: >>There are only three choices here. >> >>(1) best <= alpha. We don't know anything about any of the moves. Yet I >>believe Ed (and I thought you as well) said that if you take this 'best' >>move and store it in the hash, it works well. In my test, it didn't. >> >>(2) alpha < best < beta. This is a move with an _exact_ score that is >>correct. Also known as a PV-candidate move normally. >> >>(3) alpha < beta < best. This is a fail high move. It is better than the >>best that is allowable. It is _not_ the best move at this level however, >>it is just good enough to produce a score >= beta and terminate the search early. >>This is the case that feeds (1) above at the previous ply. If we try >>_another_move here we might get an even _bigger_ score here, and back up an even worse >>score to the previous ply. But alpha/beta makes us stop _now_. > >I like to try this. One question: what is "best"? > >the score of the node? > >the best score sofar on this ply? > >Ed In this context, "best" is the true score of the node. But we are fiddling with it to say that "it is the best score at this node, regardless of whether it is below alpha, between alpha and beta, or above beta. In a minimax search, 'best' is completely clear for _any_ node in the tree, as there is always one score that is better than the rest (unless all are identical of course). Where I am having trouble in this is understanding how it is possible to choose 'best' when _every_ score is <= alpha. IE I don't think anyone would claim that it is possible to choose the 'best' move when all scores are <= alpha, simply because of the way alpha/beta works... IE if you use fail-soft, which can return scores outside alpha/beta bounds, do the scores really 'order' the moves at that node? The theoretical answer is clearly no. Is there a practical chance to do reasonably well? I don't see how, but it would be nice if it is somehow possible. I ran two 12-hour tests overnight, and the normal approach (no best move on fail-low nodes) remains better by a significant amount. Yes, some positions do better with your 'best' trick. But for my program, more do worse. Overall, over the Nolot test suite, the current crafty was about 10% better than the 'new crafty' which used the 'best' trick being discused. (I ran two runs with one cpu, as SMP would make the node counts impossible to compare).
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.