If both of you have 3 minions on the board, each of your minions has a choice of 4 targets, which is already up to 4^3=64 choices. Then considering each order of attacks, and the fact that you can play any card of your hand before or after attacks, and the branching factor has the potential to explode.
As for the order of actions, I did mention that. The basis of my argument is that you shouldn't consider an entire player's turn as a "turn"; instead, consider each action as a turn.
And if you want to get truly smart, you also have to consider what the opponent might do, which, as viewed by the player, opens up the search space to a lot more cards both in their hand and in their deck.
So yes, each turn the branching options to play is relatively small compared to the other examples. However, the evaluation of future moves and the "true" board state is much, much harder and has a huge branching factor.
> We use an evolutionary algorithm to evolve sequences of actions that could make up a single turn. The fitness function is the quality of the board state of the end of the turn, as measured by some straightforward metrics.
My interpretation of this (and your suggestion) is that they take the number of possible actions in one turn, and prune them according to how they affect the board state. That seems to be what you're describing.
Evaluating those pruned action sets across multiple turns seems like the next logical state.
In Hearthstone, you have a specific amount of options you can play (anywhere between 0 and 10-ish), and each option may have one or more targets (usually again between 0-10 ish). This sounds high, but you're able to discard a lot of those options much more easily than you would in Go/Chess (eg. damaging yourself is seldom a good idea).
There's often multiple options you can play per turn, but each option has to be evaluated under the current state of the board since playing a single option can radically alter the game state. So a much fairer approach is to look at a branching factor of about 15, with multiple successive "turns" (eg. each option is a single "turn", and you can play multiple turns before ceding control to the opponent).