I wouldn't even use the word "exponentially" - Civ is infinitely more complicated game than chess in a computers perspective. In chess there are probably less than 100 possible moves in each turn. In Civ there are so many possible moves you can't even imagine that number. The basic approach of chess programs (seeking through a search space of possible future moves) just isn't viable in Civ.
With respect, I'm afraid you're terribly misinformed about chess. Above, I gave the number of chess permutations (not including 9-Queen games because that's been shown to be too difficult to calculate). It is indeed a number you cannot imagine.
Also, the best chess programs don't work by "seeking through a search space of possible future moves". They begin with a database of openings that includes grandmaster games over the past hundred years or so. If you stay "in book" during the opening, the computer will move almost immediately and will play perfectly. (That's why Kasparov played such weird openings and defenses against Big Blue, and also partly why he lost. His idea was to take it out of book almost immediately.)
But once you're out of book, the computer examines positions (not moves). This used to be done by brute force until IBM programmers worked in conjunction with human grandmasters to produce algorithms based on "rules" developed over time about such things as the effect of pawn positions (closed, semi-open, and open, etc.) and other things. That is, the best computers now emulate what humans do namely, they ignore examination of pointless and futile variations, which reduces the number of positions they must examine by many orders of magnitude.
The best programs also now have strategic algorithms, which they had lacked before. Becaue they will and do take advantage of a 7 by 10^35000 tactical matrix, they are nearly impossible to beat tactically. You will not, for example, catch them in any Morphy-type wow-what-a-surprise combinations that end with untenable positons for them. In fact, they will unleash tactical surprises that you have missed, forcing for example the loss of your Queen in six moves.
But the best programs no longer do brute force strategic examination. Rather, they have a singular strategic algorithm, taken directly from the play of people like Capablanca, Petrosian, and Fischer. In other words, they work to simplify the position as much as possible through the exchange of equal material, constantly on the outlook for even the slightest positional advantage. They do this by "scoring" the variations they examine, and then playing the one with the highest score. In the rare event of score ties, they will select a random one among them.
And so, the computer's middle game is fairly boring unless the human falters tactically.
But the end game is all book, just like the opening. Every known ending position is programmed into it, and so its only task in simplified ending positions is to work "backwards" from the winning position to the current position and then moving accordingly.
The point of this whole TLDR is that it is a false dichotomy to compare AI algorithms for chess and for Civ. There is a completely different underpinning play model. It's made more difficult in Civ NOT because of the possible permutations but because of the inability to devise the kinds of databases that chess models use. The Civ AI must play "by the seat of its pants" because there exists no century's worth of opening and ending positions.
The difference is easier to see if you consider the way both chess programs and the Civ program offer levels of play, from most difficult to easiest. The chess program null hypothesis is the scoring of positions, and so its default is to play perfectly. For easier settings, it's simply a matter of selecting the positions with lower scores thus giving the human a chance to take advantage of "mistakes".
Civ, on the other hand, works oppositely. Its null hypothesis is to make the best possible play within the rules at the lowest levels, and then to "cheat" at the highest levels by ignoring rules that bound humans.
I hope this helps to facilitate a better understanding of how the two compare or rather, how they really don't at all.