Question from StackOverflow

[BB+]

Well, go there if you want... What is the state of the art in computer chess tree searching?

I'm not interested in tiny optimizations giving few percents of the speed. I'm interested in the most important heuristics for alpha-beta search. And most important components for evaluation function.

I'm particularly interested in algorithms that have greatest (improvement/code_size) ratio. (NOT (improvement/complexity)).

Thanks.

PS Killer move heuristic is a perfect example - easy to implement and powerful. Database of heuristics is too complicated.

I find it strange that someone answers "MTD(f)...is a big improvement over standard alpha-beta,", when I think almost everyone who has used MTD(f) in computer chess has given it up (including both Rajlich and Dailey). My recollection is that it didn't gain much more than ~20% in the best case, and much less in practise. The general conclusion (I thought, from Romstad and others) was that PVS with a small aspiration window was just as good. See http://talkchess.com/forum/viewtopic.php?t=21360 for instance.

The title asks for "tree searching", but the question itself says "alpha-beta", so I'm not sure what the original direction was. I can mention (as can CPW) other algorithms like SSS*, B*, and conspiracy numbers, that might be superior for a given purpose.

[zwegner]

Well, go there if you want... What is the state of the art in computer chess tree searching?

I'm not interested in tiny optimizations giving few percents of the speed. I'm interested in the most important heuristics for alpha-beta search. And most important components for evaluation function.

I'm particularly interested in algorithms that have greatest (improvement/code_size) ratio. (NOT (improvement/complexity)).

Thanks.

PS Killer move heuristic is a perfect example - easy to implement and powerful. Database of heuristics is too complicated.

I find it strange that someone answers "MTD(f)...is a big improvement over standard alpha-beta,", when I think almost everyone who has used MTD(f) in computer chess has given it up (including both Rajlich and Dailey). My recollection is that it didn't gain much more than ~20% in the best case, and much less in practise. The general conclusion (I thought, from Romstad and others) was that PVS with a small aspiration window was just as good. See http://talkchess.com/forum/viewtopic.php?t=21360 for instance.

The title asks for "tree searching", but the question itself says "alpha-beta", so I'm not sure what the original direction was. I can mention (as can CPW) other algorithms like SSS*, B*, and conspiracy numbers, that might be superior for a given purpose.

Łukasz Lew should be well known to most Go programmers. I suspect that most of the replies were a bit too pedestrian for his purposes.