MTD(f) versus Alpha-Beta

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

MTD(f) versus Alpha-Beta

Postby H.G.Muller » 13 Dec 2005, 21:15

I 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:
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?
User avatar
H.G.Muller
 
Posts: 3167
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: MTD(f) versus Alpha-Beta

Postby Dann Corbit » 14 Dec 2005, 06:10

For MTD(f), some things that can cause problems:
1. If you have a really fine detail in your evaluation function (e.g. if you return scores in thousandths of a pawn or millionths of a pawn, you will pay a severe penalty due to the linear search at the end)
2. If the starting guess is bad, MTD(f) goes right into the crapper.

Modifications often brought to bear on MTD(f) include:
1. Use a cruchy evaluation function (e.g 9 or 10 bits of resolution) at least early on in the search.
2. Use a different step size at the end, or bsearch a small interval instead of +1,+1,+1 to find the endpoint.

At any rate, PVS with zero window on the non-pv nodes outperforms MTD(f) search.
Dann Corbit
 

Re: MTD(f) versus Alpha-Beta

Postby Chan Rasjid » 14 Dec 2005, 08:28

Vasik of Rybka just said he dumped mdt-f as without a truescore, difficulty
for a nullmove search (may be only for pv nodes ? again fruit dont nullmove for pv nodes )

Someone suggested a good non-uniform skipping ... 4, 8, 16, 32, 64.... 64, 32 ....4, 2, 1 . This should be far better.

Also may be good to use eval() / 10 when returns should be very fast.
Most engine win is when there is a huge score jump, not with differences of 1/10 or 2/10 of a pawn.

Rasjid
Chan Rasjid
 
Posts: 73
Joined: 23 Feb 2005, 16:36
Location: Singapore


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 1 guest