>did you look at the already existing playing MTG AIs:
https://www.slightlymagic.net/wiki/List_of_MTG_EnginesYes. I'm very likely going to use the guts of XMage to handle card text and encoding the game state and all legal actions. I'm deliberately trying to get a simpler version with only three cards working first so I can see if it's possible to "solve" (i.e. test every single possible action and response for every possible game and determine the optimal play each time) such a game.
A major issue is that determining what is in the opponents hand based on previous plays is pretty important in situations where such information cannot be brute forced and instead needs to rely on dependent probabilities.
>I believe exhaustively trying out all decks is not going to fly and deckbuilding should be centered around synergies + looking at what currently works (top decks).
I had decent success building a GA that could tweak the list for a simple burn deck by adding or removing single cards as a mutation. I only tested against a very simple opponent and all potential plays were hand-coded.
>I would personally settle on an AI bot that plays perfectly that I could feed decks to test.
The issue is that "plays perfectly" is an extremely tough bar (even against only one opposing deck). As a trivial example: Magic is full of "infinite" combos where a given loop can be completed an arbitrary amount of times. Knowing the "correct" point to stop the looping is extremely tough to code perfectly.
It's also possible to have, say, a trillion tokens on the board and it's legal to pick any one of them as a target - handling this kind of situation is also pretty hard to handle computationally.