You would need to define what kind of complexity. I would broadly break it into things that are complex to perform (crazy APMs or accuracy), things that are co

You would need to define what kind of complexity. I would broadly break it into things that are complex to perform (crazy APMs or accuracy), things that are complex to understand (the stack or layers in MTG), and things that are complex to predict (e.g. time-delayed abilities and the correct time to use them, like Baptiste's lamp in Overwatch). AI have basically constant performance across a performance complexity curve, because the complexity typically derives from physical interfaces the AI doesn't use anyways. E.g. their APM is not limited by how fast their fingers can physically move. AIs do very poorly on tasks that are complex to understand. The best Magic: The Gathering AI's I've seen are awful (though also likely far less well-funded). Best-case scenario is basically an AI who makes plays that don't make any sense, but are at least valid plays. It's a crazy difficult problem. E.g. there are various ways to make infinite mana with combinations of cards, and the AI needs to a) realize that it can use those cards in order to create infinite mana, and b) that it can do this multiple times (I.e. it can pay for a spell that costs more mana the loop generates by going through the loop multiple times). That's very hard thing to do; human players somewhat frequently don't realize when they have loops. Add on top of that that a game of Magic can enter a state where a loop of effects becomes recursive but doesn't result in either player winning. The game is a draw, because it cannot progress anymore. Detecting these can be non-trivial, because they might involve side effects that look like someone should win (I.e. you lose a life and I gain one, then I gain 2 life, then you deal 1 damage to me, then I gain 1 life, then you deal 2 damage to me. Life totals shift around, but net to 0 by the end of the loop). I think the AI do well at complex prediction tasks as well, by nature of their response times and access to prior information. I would expect an AI to beat humans by a wider margin the more complex the prediction gets. Humans have finite time and thus experience; the AI is going to have more "experience", and be able to recall it at a faster rate.