AI: Checking possible target combinations takes far too long

[Alex-Vasile]

The issue is straightforward to describe: Many cards have targeted triggered abilities, e.g. "When {A} {do B to} target ..." or worse "when {A} {do B to} up to...". These sorts of cards really slow down an AI game.

See previously reported issues with [[Deepglow Skate]] in #9438 and [[Elder Deep-Fiend]] in #9518.

They are especially bad if the AI has them since it will keep checking all possible targets whenever it gets priority. The number of options for it to check can explode.

However, they will slow down the game even if the human player is using these cards.

Further something strange is going on in terms of when this slowdown is occuring. For example, If you have 30+ hands and Deepglow Skate in your hand, you will be able to cast the spell without issue. The slowdown will only occur AFTER the spell has resolved and the player is choosing targets.
(This strange behaviour may be AI difficulty setting related, perhaps on lower levels it does not think far enough ahead for it to get to the point of evaluating all possible target combinations).

Either way, I proposed two change to deal with these issues:

1. For spells like Elder Deep-Fiend, or for abilities like Deepglow Skate (once it's entered and its ability triggered) the AI should do nothing until the player has chosen targets. There is no point for the AI to guess what to do as checking all of the combinations takes too long, and it cannot respond until after the player has made their choices anyway.
2. When it comes to the AI's turn to cast such spells, or when looking ahead to see if it should counter the Deepglow Skate, it should use a worst-case scenario heuristic (the player who has to make the choice will make the choice that puts them furthest ahead and hampers each of their enemies).

Or if 2 cannot be implemented generally, then some more serious pruning must be applied to the decisions that the AI evaluates.

[github-actions]

Deepglow Skate - (Gatherer) (Scryfall) (EDHREC)

{4}{U}
Creature — Fish
3/3
When Deepglow Skate enters the battlefield, double the number of each kind of counter on any number of target permanents.

Elder Deep-Fiend - (Gatherer) (Scryfall) (EDHREC)

{8}
Creature — Eldrazi Octopus
5/6
Flash
Emerge {5}{U}{U} (You may cast this spell by sacrificing a creature and paying the emerge cost reduced by that creature's mana value.)
When you cast this spell, tap up to four target permanents.

[Alex-Vasile]

If the server has enough memory this will slow down the game, but it can cause out of memory errors. see #6979