Maximum calculations is just a limit, it doesn't mean that it will need to calculate that much. For instance, on turn 1 without coin you have a total of 4 cards in hand, there is only 4 possible moves for it to make so it only needs to calculate those 4 moves, not 10k or more. As the board fills up the number of possibilities grows exponentially and it would start roping out if there wasn't a limit so the limit is just to keep it from taking too long in complex situations.

4W-21L is pretty awful but you didn't say anything about what mode you're trying to play or anything about the decks you're trying. For the past week the default AI was too slow but Joyadmin fixed something server side today that made my unranked low MMR raptor rogue deck go from 30-40% win rate back up to ~90%. If you're trying anything new then expect lots of misplays with new cards and report any bugs that you notice if you want them to get fixed.