Author: Robert Hyatt
Date: 12:36:18 09/11/99
Go up one level in this thread
On September 11, 1999 at 11:40:37, Ed Schröder wrote: >>Posted by Robert Hyatt on September 11, 1999 at 09:44:46: >> >>In Reply to: Re: Interesting mate test for hashing posted by Ed Schröder on >>September 11, 1999 at 02:28:00: >> >>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). > >I will try it in this way then. > >>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... > >You were right. In the current code when updating the hash table I clear the >best move now in this case. On fast time controls (20/30 secs) it gains 4% >and on longer time controls (60/90 secs) 8%. Not bad for adding 1 instruction... > >I assume the gain comes from searching more of the same moves (PVS alike?) >from the hash table thus getting more hash hits. I am interested in PVS but I >wonder if that isn't the same as the best move from the hash table? > >Ed OK... then we are 'in sync' here it seems.. As far as PVS, the main advantage is that since almost everything is searched with a null-window, it saves nodes, _IF_ you do well at move ordering (I have no doubt that you do well so PVS might be a win for you too)... It reduced my trees by 10% and loses nothing at all... unless you screw up move ordering, then it can make the tree bigger as you first search with a null window, then you have to re-search with the normal window... > > >>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.