Simple improvements in the tree search algorithms to reduce the effective branching factor are enough. Those have exponential effects.

Improving the evaluation function is "merely" a constant improvement.