I don't think that's necessarily true. Hearthstone is made by a well-known company, polished, and most importantly free. There's not much else to directly compare it to.
However, the massive popularity of stuff like DOTA suggests that there's plenty of appetite for games with deep, complex strategy.
There are ways to add computational complexity to a game without making it more difficult for new players to learn. Witness arimaa[0] compared to chess.
Someone who beats it with a computer program should not be negotiating with them for the release of the software. Especially with the nontrivial risk of lawsuit by a multi-billion dollar company hanging over his head.
*Edit - Just to be clear, there was no specific C&D made here. But I would definitely consider legal action a real threat when crossing Blizzard given how many times Blizzard has used legal tactics in the past. In additional to the aforementioned bnetd (which is a more defensible case), there was the implementation of the World of Warcraft clone in the Starcraft II engine that was shut down by legal action. That dude was a kid.
If Blizzard wants you to not do it, they will take legal action.
...which is the exact reason it became so popular.