5 ms·

Hacking Hearthstone with machine learning – Defcon talk wrap-up

118 points by declan 12y ago

minimaxir 12y ago
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.)
declan 12y ago
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-hearthstone-card-values 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 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.
- pilif 12y ago
  >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.
  - declan 12y ago
    The article says only "Hearthstone team" and "they," which is ambiguous, especially given Blizzard's history in this area.
- joshschreuder 12y ago
  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.
  - declan 12y ago
    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.
  - tks2103 12y ago
    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.
rockstarstats 12y ago
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.
bausson 12y ago
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?
- pmalynin 12y ago
  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.
  - bausson 12y ago
    Wow, OK, weird. Aren't a and h supposed to be constant here too, just unresolved ones?
  - scrollaway 12y ago
    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).
  - pkrs 12y ago
    You're thinking about Big O notation, which is not the case here
    - pmalynin 12y ago
      http://tutorial.math.lamar.edu/Classes/CalcI/ConstantofIntegration.aspx http://tutorial.math.lamar.edu/Classes/CalcI/ConstantofInteg...
- pkrs 12y ago
  Clearly a mistake in my opinion, fortunately point is still valid regardless. a + 1.16h + i/6 < a + 1.25h + i/4
NickM 12y ago
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.
- Retric 12y ago
  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.
  - NickM 12y ago
    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.
- nacho_weekend 12y ago
  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.
Strilanc 12y ago
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.
- GFK_of_xmaspast 12y ago
  Doesn't have to be perfect, just has to be good enough to win.
scrollaway 12y ago
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.
larksimian 12y ago
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 :)

118 points by declan 12y ago

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.)

declan 12y ago

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-hearthstone-card-values 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 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.

pilif 12y ago
>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.
- declan 12y ago
  The article says only "Hearthstone team" and "they," which is ambiguous, especially given Blizzard's history in this area.
joshschreuder 12y ago
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.
- declan 12y ago
  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.
- tks2103 12y ago
  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.

rockstarstats 12y ago

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.

bausson 12y ago

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?

pmalynin 12y ago
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.
- bausson 12y ago
  Wow, OK, weird. Aren't a and h supposed to be constant here too, just unresolved ones?
- scrollaway 12y ago
  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).
- pkrs 12y ago
  You're thinking about Big O notation, which is not the case here
  - pmalynin 12y ago
    http://tutorial.math.lamar.edu/Classes/CalcI/ConstantofIntegration.aspx http://tutorial.math.lamar.edu/Classes/CalcI/ConstantofInteg...
pkrs 12y ago
Clearly a mistake in my opinion, fortunately point is still valid regardless. a + 1.16h + i/6 < a + 1.25h + i/4

NickM 12y ago

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.

Retric 12y ago
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.
- NickM 12y ago
  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.
nacho_weekend 12y ago
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.

Strilanc 12y ago

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.

GFK_of_xmaspast 12y ago
Doesn't have to be perfect, just has to be good enough to win.

scrollaway 12y ago

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.

larksimian 12y ago

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 :)