The search tree size isn't an insurmountable issue. For exple OpenAI 5 managed to play DotA (though admittedly relied heavily on perfect timing and the ability to look at every enemy on the minimap at the same time, and lost a lot when people learned to play around the only strategy it knew).I think it'd be feasible to get an AI to play a modern deck.

I think it'd be much harder for the AI to do deck building in a vacuum. You could model it as every game starting with you building your deck, but I can't see that converging stably.