Tiered Search and MTD(f)

[FlavusSnow]

Has anyone tried a tiered search?

It seems to me that a search using MTD(f) as its first tier, and PVS as the second tier might be beneficial. I understand that this could add inefficiencies into the search, because you're applying the static evaluation to nodes that you might otherwise not; however, you're getting more accurate evaluation at each node, so a smart programmer could use this accuracy for better pruning (which could result in fewer total nodes evaluated in practice). I also think on a highly threaded system this might scale better because the loads could be better balanced if you split the tree only on the first tier of search. And finally I think that if you were to perform the same logic to this type of search as PVS, meaning you run test searches after a PV is defined, the theoretical penalty of searching in this way could be reasonably reduced. By this I mean to run MTD(f) type search for 8 ply, and evaluating these 'leaf' nodes by using a 4 ply PVS and then testing the rest of the root nodes with a 12 ply MTD(f) search to verify that its the best move. I only chose MTD(f) for the first tier because its been shown to visit fewer nodes on average than most other algorithms.

My train of thought is that conventional searches result in an ELO vs. depth curve that is logarithmic. i.e. going from 1 ply depth to 4 ply depth has a much higher effect on performance than going from 21 ply depth to 24 ply depth, practically speaking. So at some time/depth you'd reach a point of depreciable returns where it makes more sense to do something else with the CPU time than to increase the search one more ply. As a starting point, I'd guess that a variable (iterative deepening) first tier and a static (4 or 6 ply) second tier would work best.

Am I way off here?

[hgm]

Not sure what you have in mind here. MTD(f) searches with a null window, and PVS with a null window in the root is indistinguishable from MTD(f). So how do you want to 'evauate' your 'leaf nodes' of the first tier with PVS? Re-open the window completely? That would be horrendously expensive...

[FlavusSnow]

yes, but to a relatively shallow depth. I agree its expensive, but the question is if its worth the expense. I couldn't imagine a 2 core machine doing very well with it, but maybe a 32 core machine would do better this way than by extending a conventional search by one ply

[hgm]

As yet I don't see how you would gain anything back. Playing with window limits (i.e opening the window more than strictly needed for obtaining the root score) is possible also without invoking MTD(f). I am not sure why it is not commony done. I once did a quick experiment with pruning an N-ply search whenever an (N-4)-ply search would fail high above beta+150. This seemed competative with normal alpha-beta + NMP, even when I searched the null move first. (Which seems obviously the wrong order, when it is reduced to only N-2, and thus likely much more expensive than an (N-4)-ply search even when you take the window shift into account.)

[FlavusSnow]

yeah, and I think what you've described is similar in concept. The only reason I had thought of MTD(f) was that it visits fewer nodes, so your penalty for opening the window on these nodes should be less.

In the end, though, I tend to agree that maybe there is not much benefit in doing this. I'd like to think that more accurate eval at a node would lead to better pruning, but I'm no programmer.

[hgm]

But if I understod you correctly, you proposed opening the window for the tip searches, which were PVS. Not for the MTD(f) part close to the root.

I also thinks the statement that MTD(f) requires fewer nodes is debatable. I think that people who have tried it, usally find the opposite. And I would expect MTD(f) to turn into a complete disaster when the search tree no longer fits entirely in the hash table. (Which on modern machines is almost always the case, except for the fastest bullet games, perhaps).

[FlavusSnow]

Yes, only at the tip nodes. I figure with iterative deepening it might be doing the same work as what you described, though, depending on the pruning techniques.

And yeah, if you've filled your hash table it'd be slow. I would probably keep the MTD(f) hash isolated from whatever hash scheme was used for the PVS. Except that the PVS could supply good information on the 'best next move' for the next iteration of the MTD(f) search.

But in all actuality, a 32-core 2.0 Ghz system with 32 gig of ram running 64-bit linux can be had for less than $4,000 now since the 6100 series opterons came out. At the end of the day, I think the search should be designed for a highly threaded system like this, not designed for a single thread and then tried to get speed-up out of multiple cores.