It really doesn't.
When developing AI you have a tree of all possible moves and outcomes. Calculating the effects on any one move is trivial for a modern computer (if the rules being complicated was the problem with hearthstone then it wouldn't run on most computers. For any computer game the rules have to be simple enough for it to run, and thus simulating those rules (for a single move) is not a problem). However, when you have to look at all possible moves, well that still usually isn't too bad, calculating 20 moves isn't a big deal either. BUT when you have to look several turns ahead, the problem then becomes exponentially more difficult. If you have 20 moves (no matter how complicated the rules for each move) and want to look 4 turns ahead, that is 202020*20 = 160,000 moves.
I'm assuming you don't have much experience with programming or AI, but if you do, this might be a clearer explanation:
Say a function calcMove() is O(n) with n being how complex the rules are.
That means calcXMovesThisTurn(x) is O(x*n) with x being the number of moves per turn.
And calcXMovesForYTurns(x,y) is O((x*n)y).
So to increase the time to calculate the best possible move, you can increase x, n, or y. The thing is, for the game to even be runnable n has to be small enough that O(n) can run on your computer, thus there is an upper limit to what n can be. x on the other hand doesn't matter (in a 2 player game with no AI) because the computer doesn't need to calculate the results of every possible move, just the one the players actually select. The biggest factor is y*, and that is bound by how long the game could theoretically go on for (in hearthstone I'm not sure what it is, but if you take into account fatigue damage (and all possible heals, etc.) I imagine it does exist (you can only have so many reno's, healbots, etc. in the deck and even an upgraded hero power restoring hp/armor is still going to get over taken by the fatigue counter after 4 turns). In chess I'm also not sure if there is a definite upper limit (if it isn't timed chess). In general I don't think there is (since stalemates are possible with only two kings on the bored, although I think there is a solution for some positions of only 2 kings that take around 150 turns to resolve).
I'm not going to go much further, but to give an example:
In chess you have 16 'minions', pawns have between 1-4 possible moves (regular move, initial double move (forget what it's called), and 2 side attacks), so 8 * 4 = 32 possible moves for all the pawns (worst case given an arbitrary position of the rest of the bored). Rooks have 8 + 8 moves (up to 8 different moves vertically and up to 8 horizontally) * 2 (2 rooks) = 32. Same for bishops (another 32). Knights have 8 moves each (4 initial directions, and two possible 'curves' in their move for each direction) so 16. King has 8. Queen has 8 + 8 (rook moves) + 8 + 8 (bishop moves) so another 32. So all together, given an abritrary position with all of your pieces alive on the board, the worst case is going to be 32 + 32 + 32 + 16 + 8 + 32 = 152 possible moves for one turn. If you want to look 4 full turns out (152 for you plus 152 for your opponent in one turn) that is 3044 = 8,540,717,056. Obviously you can trim this down some, but this is the absolute worst case (which I will do for hearthstone as well).
In hearthstone you can have a maxium of 10 cards in your hand, 7 minions in play, 1 weapon, and 6 possible secrets that the enemy could have. Each minion (plus weapon) can attack (in the worst case) 8 possible targets (7 enemy minions plus face) so that is 64 possible moves for minions + weapon. If all 10 cards are zero cost, then that is a factorial 10! possible card plays, which is 3,628,800 possible moves. Actually if they play all 10 cards. The number of possible card plays for a 10 card, zero cost hand would be 10! + 9! + ... Then add that 8 out of 64 possible attacks. Then double that for a 'full turn' and then take that to the 4th power for 4 'full turns' and you have the worst case. So in this case it does look like in the very worst case hearthstone might be more difficult to compute, but that is because the number of moves are more, not that the "rules are more complicated".
Realistically though there are going to be a lot less possible moves in both games (a more realistic hand would be 4 cards, with enough mana for 2 playable at the same time this turn, which cuts that 3,628,800 number down to 7 (4 + 3), but then you'd have to do the same for the chess moves, which I am not sure what a more realistic number would be, but I don't think 10-20 would be out of the question. In which case chess would be more difficult for a computer to calculate).