"The game can be used to encode a Turing machine" is not at all the same as "it is difficult to write a program that can play a legal action in every situation". It's the latter that seems to be difficult for the bot authors.
> "it is difficult to write a program that can play a legal action in every situation"
This is trivial (just forfeit).
The hard part is figuring out the best possible action to select from. MTG is particularly hard at this because:
* Some actions are only allowed in certain conditions (e.g. in response to, in a specific phase, etc)
* Actions vary significantly not only in their effects but also in their inputs (some require targeting a creature, a player, an opponent, a card in hand, a card in exile, a name of a card that could exist). Some have a varying list of inputs (target many creatures). This variance makes it hard to encode the action space.
* The state space is huge. It is not only determined by the cards in play, but is also affected by the meta-game (to play optimally players have to play in a specific way to avoid getting countered by a card that could be in play by the opponent, because that card is legal to play and is commonly used by decks that look like what the opponent is playing).
* Technically the state space is also infinite because you can create infinite loops that keep creating more and more triggers/creatures/etc.
