Chess has far fewer potential moves than Dominions. A Dominions AI built on the straightforward paradigm of a chess AI would need to consider every single possible unit and spell in every possible situation and would need to think ahead until the possible completion of the game. Way easier when combat resolution is just "one unit wins", new units are never added, and there are no spells. If an AI could be made which understands the game, you'd have to wait years between turns for it to play out every possible situation and figure out is moves.
I know it isn't really the thread but there are objections to both your points :
1) "Dominions has more potential states than chess". Yes, but that was what was said when we managed to make AIs for checkers and said we couldn't because chess is multiple orders of magnitude above checkers.
2) "chess AI would need to consider every single possibility". Nope. The latest AIs in chess beat the previous ones (and the grand masters) because they don't try to consider every possibility, but try to solve their problem more humanly, going to a relatively better state in a few moves, without considering the end of the game.
This year's advances in Chess AI are basically putting usual RTS AIs considerations into a chess logic and improving it, which may be useful for the future of Strategic Games AIs
How the hell am I suppose to assault this fortified outpost?
Use rituals ?
If you can, try to use the heat++ ritual (breath of the desert ?), the one that will put the temperature of the province in the positives.
Otherwise, try to use one of the spells (Locust Swarm, maybe another too) that consume their supply, so they all starve.