RememberBestMove in hash
Posted:
23 Oct 2006, 15:12by Giuseppe Cannella
hy,
what mean the RememberBestMove() function in
http://www.brucemo.com/compchess/progra ... ashing.htm
and when it is used ?
thank
Giuseppe
Re: RememberBestMove in hash
Posted:
23 Oct 2006, 16:02by H.G.Muller
It is pseudo-code for taking the best move that was stored in the hash entry (MOVE best), and communicating it somehow to the GenerateLegalMoves() or MakeNextMove() such that this move is tried before any other.
Bruce's pseudo-code isn't very explicit in how MakeNextMove() determines which move to pick as the next move, when there are more than one MovesLeft(). But in real chess engines this is crucial. Trying the best move first causes alpha-beta pruning to reduce the minimax tree to approximately the square root of its size, trying the moves 'worst first' would not reduce the size at all. So if the size of an 8-ply tree is 1,000,000,000,000 nodes, optimal move sorting speeds up the search by a factor of a million compared to really poor move sorting. Trying the moves in a random order whould probably not save more than a factor 100.
Telling the search which move was the best for this node is the most important function of the hash table. But the search must know what to do with this information, i.e. adapt the move ordering accordingly.