Search space size is no longer a great heuristic of how difficult a game is for the latest in AI approaches. For example, an RTS game has an absolutely enormous search space as well (effectively every unit of several hundred can move in every direction for every single tick of the game clock, many units have spells and many spells are meant to stack with other spells) and Alphastar is a convincing demonstration that this is not out of the reach of current AIs. And you similarly have imperfect information where you don't know what your opponent is doing unless they are sufficiently close to your current units.
Even the meta-game/deck building aspect doesn't seem all that insurmountable as it doesn't seem fundamentally different from say a build order other than that it cannot change dynamically on the fly.
Even the meta-game/deck building aspect doesn't seem all that insurmountable as it doesn't seem fundamentally different from say a build order other than that it cannot change dynamically on the fly.