Author: Ed Schröder
Date: 08:40:37 09/11/99
Go up one level in this thread
>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 >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.