I think you're looking at things with a sort of hindsight bias. Victory at chess was at one time considered to be
the indicator of the emergence of true 'intelligence' in computing. The reason is that it's an extremely open, creative, and strategic game spattered with a minefield of tactical nuance. Nobody, human or computer, is getting even remotely close to scratching the depth of the game from a numeric point of view. There are some specifics on the numeric complexity of the game here [1].
The reason I point out the unfathomable numeric complexity is that it makes the games, from the perspective of an AI, effectively infinite. AIs are calculating, but to an extremely superficial degree relative to the depth of the game. E.g. - when a chess program says it's calculated to 30 ply (15 moves for both sides) what it really says is that it's seen up to 15 moves deep after intentionally ignoring or pruning 99.9999999999% of moves which it thinks probably aren't good -- something it still often gets wrong, but its 'understanding' of what is 'not wrong' is strong enough that it still results in a phenomenally strong level of play, compared to humans. There's no doubt that perfect play in chess would still go 1 billion - 0 against something like AlphaZero.
So what matters is not the number of decisions to be made but the individual complexity of the decisions to be made. And in most games we consider complex the individual decisions are not really that complex, and complex systems can often be broken down into very simple games. For instance a great example of this is a 4x game. Taken as a whole they seem complex, but they're really just a large number of relatively simple components that are mostly independent. E.g. - Given this state, where do you explore next? Given this state, what do you research next? Etc. Another benefit for AIs in that in games we consider more complex, the value of any given mistake often becomes diminished. If you make a single bad move in chess, it's enough to lose the game. In a 4x game the weight of individual decisions is not so high, it's all about the big picture. But as perhaps computer success in Go shows most clearly, actually seeing the big picture is not really necessary to produce play like you do.
This, I think, is why research has moved more onto real time competitive games. Crushing humans at chess, go, and now poker as well is a pretty solid proof of concept for computers beating humans at any turn based game. When you start adding bunches of different layers to games I think it's more likely to handicap the human than the computer. Imagine playing some sort of 100x100 chess. We can only speculate, but I imagine the distance between the top AIs and humans would be far greater than it is in 8x8 chess.
[1] - https://en.wikipedia.org/wiki/Shannon_number