You don't have to go through the complete search space if it turns out optimal strategies are sparse. What do I mean by that? Take a second-price auction: the dominant strategy here is to always bid your true value. Meanwhile, the search space for this would be any real number in between 0 and your true value. What does this mean for computational games like Chess or Go? It may mean while the search space is exponential, there may exist computationally trivial strategies that work. I would compare this to Kolmogorov complexity, except instead of having a program as your output, it's a strategy.