Hacking Hearthstone with machine learning – Defcon talk wrap-up | Hacker News Reader

Hacking Hearthstone with machine learning – Defcon talk wrap-up

elie.net

118 pointsdeclan31 comments

The interesting thing to me is what exactly Blizzard Entertainment said that prompted the author of this blog post (a Google research lead) to decide not to release the utility that at Defcon he said he would.

Excerpt: "Following Defcon we had a series of conversations with the Hearthstone team about our research... they were very concerned that our real time dashboard that can predict your opponent’s deck will break the game balance by giving that person (that is, whoever has the tool) an unfair advantage. They also expressed concern that such a tool..."

There's no evidence his utility was derived from reverse engineering or a TOS violation. It appears to be based on evaluating a large number of Hearthstone matches and using those results to create a mathematical model that lets you find "undervalued" cards. One application of the model is a utility that can help to predict "what your opponent is going to play based on previous turns." https://www.elie.net/blog/hearthstone/how-to-appraise-hearth...

Blizzard has taken aggressive legal action before. As EFF tells it, Blizzard filed "a DMCA lawsuit against a group of volunteer game enthusiasts who created software that allowed owners of Blizzard games to play their games over the Internet. The software, called "bnetd," allowed gamers to set up their own alternative to Blizzard's own Battle.net service." https://www.eff.org/wp/unintended-consequences-under-dmca

This time, I wonder if the decision not to release the utility was prompted by a friendly query from a Blizzard developer or a C&D nastygram by a Blizzard attorney -- with a lawsuit threatened if he didn't comply.

>This time, I wonder if the decision not to release the utility was prompted by a friendly query from a Blizzard developer or a C&D nastygram by a Blizzard attorney -- with a lawsuit threatened if he didn't comply.

according to the article it was the former. And considering that the latter would be even better PR for the authors, I would assume the article to be true.

The article says only "Hearthstone team" and "they," which is ambiguous, especially given Blizzard's history in this area.

Seems a bit tin-foily, they state in the post: "...they were very concerned that our real time dashboard that can predict your opponent’s deck will break the game balance by giving that person (that is, whoever has the tool) an unfair advantage.

They also expressed concern that such a tool makes the game less fun by taking away some of the decision-making from the player."

Nothing in there indicates aggressive legal consequences for the author to me.

It seems fair enough - it's a game, and anything that would ruin entertainment value for players is obviously not something that Blizzard would want released.

I've spent 10+ years paying close attention to lawyer nastygrams to security researchers and academics, and that's exactly the type of language they would use. But as you say, perhaps I'm being too cynical in this case.

If they want to avoid ruining entertainment value, they should make a game that is not so easily solved by a computer program. They deliberately avoided mechanics that introduce complexity when designing Hearthstone.

I do not see why anyone other than Blizzard should be interested or required to cater to Blizzard's game design decisions.

> They deliberately avoided mechanics that introduce complexity when designing Hearthstone

...which is the exact reason it became so popular.

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.

[0] http://en.wikipedia.org/wiki/Computer_Arimaa#Computer_perfor...

Awesome, they have a very popular game.

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.

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.

No one is going to be "solving" Hearthstone using any of the analysis provided by the author here. The author is missing several huge pieces of the puzzle including card & deck synergy, synergy with hero power, option cards, meta-oriented target cards (aka tech cards), and most importantly, that cards themselves are a resource. You can immediately tell the latter isn't taken into account when you see cards like Shieldbearer, Voodoo Doctor, and Sacrificial Pact in the undervalued list (all low mana cards with little benefit). You won't find any of those cards in any legend-tier or professional deck at the moment because they provide very little utility or board presence. Nothing is shown in their research that provides any information that players don't already know.

He even mentions in the article that Blizzard is very supportive of their research on game and card balance, but they specifically mention that they are concerned about the real-time dashboard that can predict your opponent's deck. The prediction part probably especially puts them off considering there was a video released last week that shows someone allegedly using a network vulnerability to predict exactly what cards an opponent draws during a game.

It is quite possible that they asked him nicely, and he agreed out of professional courtesy (I'd probably do the same in this situation).

Look at the pros and cons from the researcher's perspective.

Pro

His professional and personal reputation is enhanced by his research findings, which do not depend on the dashboard. What does the researcher gain by releasing the dashboard? Not much.

Con

If he releases it, he potentially changes the character of the game if a lot of people start installing and using the dashboard. He makes life harder on the Hearthstone team, and Blizzard. Ultimately the risk is that the game see falling interest and support, and gets cancelled. So what does the researcher lose by releasing the dashboard? Possibly one or more aspects of a game he clearly likes.

It was probably not hard to convince him not to release it.

It might be easier to use machine learning for card prediction in Hearthstone than you might think at first glance: the problem space is constrained by class choice, metagame, and limited card pool.

If your opponent is using a Hunter deck at a reasonably high level of play for example, he's using one of two deck types, and due to Hearthstone's 30 card deck limit, there are a finite amount of bombs he can put into the deck.

Contrast this with MtG decks: although you might know the overall archetype of the deck, the problem space is much larger, and much more likely to have tiny variations, especially in the number of card copies in a deck (Hearthstone only allows 1-2 copies of one card a deck; MtG allows up to 4, in addition to any number of basic lands.)

Modeling cards as independent and linear is a vast vast oversimplification. It doesn't account for card synergy, exhausting your opponent's counters, managing your mana curve, managing your hand size, etc.

For example, Shadowstep is an alright card... until you combine it with Leeroy Jenkins. Then it's 6 damage for 2 mana, and basically the reason Miracle Rogue decks exist.

Linear and independent is a reasonable place to start, but nowhere near the goal.

Doesn't have to be perfect, just has to be good enough to win.

As someone who has played quite a bit of Hearthstone, I wish he had released his machine learning tool, even though I probably wouldn't use it myself. Such a tool would basically punish people who copied a pre-existing popular deck verbatim, and reward people who creatively designed their own decks to be different from the mainstream.

I think it's worth mentioning that high level players can already do a pretty good job of predicting the cards in peoples' decks. The best players will often experiment with modifying existing decks or building their own from scratch, partially because there's a significant advantage to not using a popular deck that your opponent already knows how to anticipate.

Hearthstone has a funny kind of a sandwich pattern, where the best and worst players tend to create their own decks, but the vast majority of the middle is largely dominated by the same few decks that you'll see over and over again. It would be nice if a tool like this could help break that pattern.

Your assuming a reasonably balanced game. There are plenty of examples where card games Basicly* just had one winning solution at some point. Granted, these types of games tend to be fairly fluid as new cards are added all the time.

*aka, there was a type of deck that is dominate even if it allows for various minor changes within that theme.

True, but in practice Hearthstone has been relatively balanced, and allows for a lot of different winning strategies that are all competitive. Right now I can think of at least seven very different decks off the top of my head that have been really popular in the last couple weeks, and it's pretty common to see people hit the top ranks with totally new deck ideas that nobody has seen before.

It's possible that tomorrow someone will find a game-breaking deck that beats the pants off of everything else out there, but it seems unlikely. The thing is, the game is somewhat self-correcting. The more popular a certain deck is, the more other decks will evolve to counter it.

Good point. At the same time, when you have a person add/remove even one or two cards to a popular deck it can RADICALLY change the playstyle due to the 30 card limit. Every top player has their own twist on the meta decks.

> Such a tool would basically punish people who copied a pre-existing popular deck verbatim, and reward people who creatively designed their own decks to be different from the mainstream.

At the lower levels, maybe. High level players are doing the exact same thing this tool is doing, except in their head and potentially a lot better (taking into account variables the tool could not possibly know). Yet people still play the same old decks at high level and just rotate between them to try and have the upper hand.

I don't think HS has enough room for pure creativity rewards at a high level yet. Maybe after the first expansion; after all, every card released increases the number of potential combos exponentially.

Cool initial look at the problem space. I think a Nash HearthStone deckbuilding solution is very possible, but it's the definition of building to one client given the aggressive legal stance Blizzard tends to take. The best commercial chance would be to try to sell it as a balancing tool so devs could make sure all classes stay viable for new releases. Given board + life + hand information is clear, alpha beta for the gameplay strategy combined with a simple genetic algorithm for deck peturbation, initialized with the best decks from current players, could probably be superhuman competitive.

Card value calculation should look not just at mana but also at the card itself as a cost. Something like Wisp might be great value/mana but it's appalling value/card. That's just obvious and simply to fix. Keep in mind the Warlock hero power(2 mana and 2 self hero damage to draw a card) as a reference point for the value of 1 point of 'card'.

The worst error, I think, is the the assumption that points increase linearly in value. Hearthstone has clear thresholds of usefulness. You'd almost always want to draft a 4attack/5hp for 4 mana creature, you'd rarely want to draft a 5attack/4hp for 4 mana creature, despite their model valuing 1 point of attack at .57 and 1 point of hp at .40.

For instance their Estimated cost for Light's Justice is 2.6 and for Fiery Waraxe 2.5. Except Light's Justice is godawful and Fiery Waraxe is one of the best cards in the game.

Why? Because Fiery Waraxe will kill almost any 1, 2, or 3 mana drop(most of those creatures have 2-3 hp). Light's Justice will tickle them and cause you to take massive amounts of damage.

It's also the reason Chillwind Yeti(4 attack/5 hp) is a 100% pick in Arena drafting(where you tend to build non-gimmicky general value decks). It very very often trades 2 for one and results in card advantage, without needing any combos. The increase from 4hp to 5hp is much more important than the increase from 3hp to 4hp.

Overall I really liked their experiment, despite disagreeing with their method/results :)

He mentions that he wishes Replays were added to the game for statistical analysis purposes. As someone who has dealt with the problem space at hand, I cannot agree more. Replays are something cheap that really should be added to the game.

Can't be that hard - Hearthstone uses Protobuf internally. I hope we can get something like that soon; whenever a game becomes popular, I weep at the amount of analysis and research that could be done on it but is not due to lack of public analytics.

Well, looking at the video, 11mn in, i see a weird system simplification: * 6 = 6a + 7h + i * 4 = 4a + 5h + i

get "reduced" to: * 1 = a + 1.16h + i * 1 = a + 1.25h + i

I wonder why it isn't i/6 and i/4... basic mistake or I missed something?

It's a trick from calculus, when you do an operation on a constant, that doesn't make it dependent on the variable, it is still a constant.

Wow, OK, weird.

Aren't a and h supposed to be constant here too, just unresolved ones?

Funny thing here is it's not corrct to do that either. Because some attack/health values are better than some others even though they may be lower. For example, 4 attack is vastly superior to 5 against Priest, and 6 is vastly superior to 7 against all classes, because of certain cards which affects enemy minions with a minimum attack value of 5 and 7 respectively.

So War Golem (7/7 for 7) is a lot worse than Boulderfist Ogre (6/7 for 6).

You're thinking about Big O notation, which is not the case here

http://tutorial.math.lamar.edu/Classes/CalcI/ConstantofInteg...

Clearly a mistake in my opinion, fortunately point is still valid regardless.

a + 1.16h + i/6 < a + 1.25h + i/4

Reply on news.ycombinator.com