MTD(f) versus Alpha-Beta
Posted: 13 Dec 2005, 21:15I encountered claims that MTD(f) would be a much more efficient search strategy then regular Alpha-Beta. However, when I tried it out I hardly found any difference, and the slight difference I do find is in favor of Alpha-Beta.
Is this an indication that my hash table is very inefficient?
I tried to figure out the absolute efficiency of the various search algorithms, by determining the minimum number of nodes that has to be considered to be able to evaluate the root to a certain depth. (By putting the narrowest possible window around the final value, and then adding the counts for all considered subtrees (plus one for the node itself) to get the subtree size for nodes that do not fail high. For nodes that do fail high I take the count for the subtree of the move that causes the fail, plus one.)
This number can then be compared to the various practical searches. For instance, a 9-ply search from the initial position gave the following result:
Cases B-D were done with a narrow window, (final_score-1, final_score+1). In none of the cases scores were taken out of the hash table.
Case D-E only used the most rudimentary move sorting, trying the best move from the previous (one less deep) iteration first, and otherwise random order. Apparently this is a factor 8 worse than the theoretical optimum. Translated to a branching factor, (9th root) this is a factor 1,26. With hints from the hash table on the best move, rather than from the previous iteration (not doing the 'internal' iterations) we are a factor 3 away from perfection (13% per ply).
Conclusion: over the full 9 ply, the ineffciency grows quite bad. Case F is the most realistic for real operation, using the best-move hints from a hash-table filled by a previous, less deep search. The difference between an open and narrow window is not very significant, not even when accumulated over 9 ply. This suggests that using the best move from the hash table is pretty efficient at quickly narrowing the window, and little can be expected from window manipulations (like aspiration searches).
In principle, there seems a lot of room for improvement, though, (a factor 3). I am not sure how I can compare this to MTD(f) results. The latter is quite different in character from Alpha-Beta searches, the same node (rather than the same position elsewhere in the tree) is visited there several times with different window. Without retrieving the results of these nodes from the hash table this is never competitive. I guess I should count such revisits as one to compare with the results above. This requires hashing on the complete history, rather than on position, if I want to separate the revisit effect from the transposition effect.
Can it be that my results are not representative, because the opening position is rather tame, and the value does not change much from one iteration to the next?
Is this an indication that my hash table is very inefficient?
I tried to figure out the absolute efficiency of the various search algorithms, by determining the minimum number of nodes that has to be considered to be able to evaluate the root to a certain depth. (By putting the narrowest possible window around the final value, and then adding the counts for all considered subtrees (plus one for the node itself) to get the subtree size for nodes that do not fail high. For nodes that do fail high I take the count for the subtree of the move that causes the fail, plus one.)
This number can then be compared to the various practical searches. For instance, a 9-ply search from the initial position gave the following result:
- Code: Select all
A) 10,2M Required nodes
B) 15,5M Re-search at same depth with best move from hashtable
C) 24,9M One-deeper search with best move from hash table
D) 53M Best move from previous iteration of internal iterative deepening
E) 84M Internal iterative deepening with window fully open
F) 31M As (C) with window open
G) 14,6M As (B) with window open
Cases B-D were done with a narrow window, (final_score-1, final_score+1). In none of the cases scores were taken out of the hash table.
Case D-E only used the most rudimentary move sorting, trying the best move from the previous (one less deep) iteration first, and otherwise random order. Apparently this is a factor 8 worse than the theoretical optimum. Translated to a branching factor, (9th root) this is a factor 1,26. With hints from the hash table on the best move, rather than from the previous iteration (not doing the 'internal' iterations) we are a factor 3 away from perfection (13% per ply).
Conclusion: over the full 9 ply, the ineffciency grows quite bad. Case F is the most realistic for real operation, using the best-move hints from a hash-table filled by a previous, less deep search. The difference between an open and narrow window is not very significant, not even when accumulated over 9 ply. This suggests that using the best move from the hash table is pretty efficient at quickly narrowing the window, and little can be expected from window manipulations (like aspiration searches).
In principle, there seems a lot of room for improvement, though, (a factor 3). I am not sure how I can compare this to MTD(f) results. The latter is quite different in character from Alpha-Beta searches, the same node (rather than the same position elsewhere in the tree) is visited there several times with different window. Without retrieving the results of these nodes from the hash table this is never competitive. I guess I should count such revisits as one to compare with the results above. This requires hashing on the complete history, rather than on position, if I want to separate the revisit effect from the transposition effect.
Can it be that my results are not representative, because the opening position is rather tame, and the value does not change much from one iteration to the next?