>> Thanks. Hi everyone. May name is Elie and today we are going to talk to you about new game
hearthstone. This is a (inaudible) work and does not present our way point of view.
If you are looking for a new job we are hiring so if you are interested come talk to me after
the talk. With that out of the way, let's get started. Hearthstone is a digital
collectible card game developed earlier this year. It is based on War of Warcraft and
(inaudible). Everything is too interesting sometimes and consequences that happens. For
us, at some point during the last few months we started to be more and more interested in how
the game is structured, how we can understand better (inaudible) rather than playing
it (inaudible). I remember June I think I played only up to Level 5 and probably like 100
(inaudible). Which is a huge down from I use to play. If you haven't tried it you should. It
is available on your computer, Mac and PS and on Mobile edition. Looking at this it's
also was a very good excuse for me because I finally talked my wife to come on stage with me.
That's something I want for a long time. So please be nice to her. (Applause) So what are we
talking about today? We're going to talk about game complexity. How to have about 500 cards now
and (inaudible). The question is, can we use (inaudible) can we find things which makes us
given an edge. That's what this talk is about. We wrote about our research in Blizzard. I know
some of them are in this room but we didn't get any response so I think they're fine with it.
So while we wanted to talk to you. First thing we want to tell you about how to find
undervalued cards. So each card has a value and the question is, are they better bang for the
buck than others. The second thing we wanted to tell you and the thing we really keep under
wraps and the surprise is Def Con is can you predict what you're going to play? Yes it's
possible. We're going show you how. We also wanted to tell you about how to predict the game
outcome. It's interesting. Except we don't have time. 45 minutes is too short. So
we'll write about it. Of course we wanted to tell you about the alien invasion. No, wait. Not
this one. How many of you play can you please raise your hands. How many of you reach legend? No
one. Sorry. Legend for those (inaudible) what a normal game looks like. It is a board game.
Turn by turn. Two player. Each person is represented as a hero which is inspired by world of
Warcraft characters. You are at the bottom. Here I'm playing the (inaudible) hero and (inaudible)
which is a solo player only hero. The game ends when one of the two heroes reach zero.
(Inaudible) it is on the right side of it. You use decks. And cards for each limit is a limit.
You can use only 30. Not 29 or 31. Just 30. Each card has to show (inaudible). So every turn
you draw a card and the card goes into your hand. This is my hand. And you can see one of the
cards highlighted in green. It means I have to ask mana to play. The mana is the resource
we use to play cards. You also have a ‑‑ your friend also has a hand. You only see the back of
it. Those who are curious know they do not know the card ahead of time. So (inaudible) on the
right side you go from one of the first turn as to turn ten. After turn ten it should
replenish but do not increase. So the maximum amount of mana you can have at the given time
is ten. So card can be a weapon (inaudible) which you play immediately. It can also be
minions or creatures. You can have up to seven on the Board for each player. You open it at
the top. Here you can see for instance I am playing (inaudible) and my opponent has
three minion. So you see what hearthstone looks like when you play it. It's obviously designed
to play on a tablet. Because we designed like this. And they simplify the law compared to
magic because you don't have to deal with land. It's very simple and very easy for people to get
in and get their first card which is how they make money. (Inaudible). Here is a quick
video of me playing hearthstone just to show you the game. You can see this is my turn. Bring a
new card into game. I draw a game which goes to my hand. I play another card and I take
another turn. Then my opponent has a secret (inaudible) turn. This is what a turn looks like.
On the video it is awesome because the guy plays me fast. You have up to 90 seconds so
sometimes you have to wait and drink coffee. So some people play two games at once. What
makes the game so interesting? Everything is a card. If you look at all the game structure
the hero is a card. Everything is a card. The card is the thing we're going to look at in depth.
So a card has a minion. (Inaudible). The first one is a mana. You play the card from
zero to ten. And then you have basic attributes in this card which is (inaudible). Four here.
So that's a card and this is a very boring card. Nothing special about this card. What
makes the game fun is there a lot of card which have a lot of interesting effects. Three of my
favorite cards. (Inaudible). What's very interesting is you can play as intended or very
special combo and that's basically how you win the game. So one of the fun aspects of the
game. Now that we know cards the question is, is there a better card or card which are better
bang for the bucks than others? How do we find those? I know it's early in the morning and
the head hurts but bar with me please. We're going to start with the basic assumption of how
we're going to (inaudible) them. The first thing is the mana card is professional to the
(inaudible). Which mean if you play one card it's less powerful than a three mana card. If you
had them everyone would play the most powerful and overrun people. It is a bit unbalanced
but not so much. Two is the power of the card roughly increase which means a two mana
card is twice as (inaudible) as one. (Inaudible). It was means the highest card was (inaudible)
and would have no chance of success. (Indiscernible). Card effects have a constant. It
means given (inaudible) or any effect have the same price regardless of the card. There is
no secret. All of this is a card. Which brings us to the fourth one which is having a
card has value. Remember you only get one card each turn. So even holding a card has some
value which, of course, is interesting value of the card. Finally, we believe there is no
secret. We believe it has no hidden factor and what you have in the card is exactly what the
value of the card should be. So if we were (inaudible) you would get the value of the card. The
question is how you sum them is another question we're going to explore but there is nothing
secret bit and you can actually look at it. That's where we start. As I said the mana is a
price and price is equal to the (inaudible) and the value. There is nothing else on the card so
we the exact price of mana is exactly the sum of those attributes. You put it into a
(inaudible) function. You say for attack which is A is the attack position which is the
base point. How much mana cards have one attack. Plus five (inaudible) where etch is the
question. Which is the base point. How much one count in mana plus I which is interesting
value of the card which is how much mana does it cost to even hold the card. With that you can
without looking at it you can compare it to (inaudible). Very common card is the (inaudible).
We can also put in a question. Interesting value. We want to convert it to our (inaudible).
So same thing. We're going to be very, very high‑tech. We're going to go back and forth and
we're going to just divide by six. Yes that's really hard I know. (Laughter) Then give you
one mana point. So for one mana point you get one attack. One to 16 counts and interesting value
of the card. On the other hand, we're going to divide by four. By doing this you say one point
what you get is one attack and 1.25 (inaudible) for interesting value. Here you can image as we
see one of them gets better bang for the bucks. Gets more points than the (inaudible). And that's
the kind of imbalance we're going to look for. Let me give you a more interesting example.
Fire ball. My most hated card. It's very simple thing. For those who don't know what a fire
ball is it is a big ball of fire that can pulverize you and you die. So, basically, this one is
very simple. You pay four mana and you blast the guy. So very simple. One mana is 1.5. All
right. We already know fire ball is great. How about we make a giant fire ball. It's called a
(inaudible). Bigger. Stronger. Meaner. The fire blast is basically ten mana. For ten mana
you get ten damage. Well okay. But then might be bigger but the bang for ‑‑ the value is not
that great. You get one mana, one damage. If you have ten mana you can play two fire
ball‑and‑a‑half for the price of one. So the value of the fire blast is less interesting than
the fireball. What's interesting is this is a new version of the fire ball. Earlier in the year,
we had a premier version which use to cost eight mana. Where at that time the mana cost was even
lower than the fireball. Where basically for the adjusted value we get 1.25 damage for one mana.
So something is not right here, right. Let's compare the two. If you take ten damage you think
the fireball should do four damage not six. And you're, like, well okay but the fireball
is properly priced. You should do six damage for four. Well in this case a power blast should
be (inaudible) damage not ten. Give me back my fire blast. Even if you look at the (inaudible)
you can see there are some decisions which are ‑‑ of course we don't have all the
(inaudible) and this is based on tactical secret analysis. Complexity is the basic whole
idea of finding the value card. How do we count that to hundreds of cards. We're able to do 130
cards because attribute is a bit complicated so you have to cross deck. A bunch of decks you have
to process. We did 130. How we do that. We model the card as we did before. Then we use those
cards and reverse (inaudible) using linear algebra. Don't worry it's not as bad as it
sounds. And use (inaudible) for the real value. The last step is where you say here is my real
value. Here is my face value: You get a negative and you find another value card. That's as
simple as this. Not that bad. So let me show you on a very simple card how it looks like. Then
when we that I will show you. Let's take three cards which have charge. Charge is you put
the card and the cards can attack as soon as it come into play. We have four. We have the
(inaudible) and the commander. We're going to show two more cards which have different
shares. The reason why they the commander is the middle is because it has both attributes.
One of the ideas of having linear algebra you can commute coefficient. That's why we can
convert cards because it is very complicated. So we do as we did today. We put them into an
equation. So we have four attacks. We have a charge partition which is ‑‑ partition
plus the intrinsic value of the card. Then we're going to reverse the attribute partition.
To do that we put them into a matrix which is basically a table. And we put them like
this. You say well performer gets four attacks, three counts, one charge, zero shield and one
(inaudible). Then I do the same for the rocket EER. Here you can see it has one and one. Then you
add the two other cards which has (inaudible). Then you have one line of (inaudible) which is
the lead square and boom you get partition. And the partition are one attack, the A, minus one for
(inaudible), two for charge, and one for (inaudible). Dude that doesn't make any sense. Yes you
are right. It is because you only have five cards. Five cards is not a good partition because
there is too much instability. So now how do you find the real price? Well now we're going to
be back to kindergarten where you learn how to add stuff. Basically what you do is you say
it's four times one plus two times minus one plus one plus one. And the price is six. So
the real value according to our computation is six. The card is fair. There's nothing different
between the face value and the real value so you are, like, not interested. Let's try again.
It's game. A lot of people said the formula isn't the value. Let me ‑‑ let's try again. So it's
one attack, one count, one (inaudible), one shield plus the value of the card. So it's one
times one, plus one times one minus one plus one. Now it's two. Wait. Two? No. The card is
one right? You are right. That is why it is an undervalued card and should cost twice. Even with
our partitions you can always see this card is clearly undervalued. That's basically
the idea we have is it always works. So I did post that online and we got a lot of good
feedback about it. A lot of good comments. Thank you anyone who pointed out. The most important
one was, hey dude you should take into card dependency. That's actually true. Thanks to
you. The charge would be basically a factor of the attack. And mode of the attack.
So now we now use attack time and charge. Same thing for wind free. Now we know it's to the
attack of the card. One where we have a large feedback. The question is about shield should
be. It is a coefficient and related to half. Related to attack. Difficult. If you have
idea, let me know. The thing is up. So that's a comment from someone on the blog which
actually wrote me a long post. Actually cards have a budget. And the budget is two times the
mana plus one. I have no idea how we come up with the idea. It is absolutely reasonable and
when you do it the partitions look way better, it is true. I just didn't know how this guy
get it. But thanks. So after writing code and de‑bugging and de‑bugging and de‑bugging you
have something and voila. You get your coefficients. So these are the coefficients. You can
see the most valued coefficient is ‑‑ I'm sorry. I must mention because we use a budget idea
that I've been proposed now two partition points is roughly one mana point. Basically you are
trying a minion got you five to add to the card. The damage cost you 1.5 mana per point. Joint
card ‑‑ a single card cost you roughly 1.5 mana. Then the shield is pretty expensive one
mana. We also have negative coefficient which is basically decrease the price of the card
as you expect. Having your joint card is the highest one followed by these cards discard. And then
we have overload which is (inaudible) you pay another price. All this is perfectly
fine. We're really happy. We have this guy. We did something which was very clever which was
the single target and multiple target the coefficient is different. I am going to show
you why. Keep in mind that we tried. So one way to neutralize what looked like as a result is
you have a ‑‑ can put on the graph where X is how much these are the face value and the Y is
how much the card is worth. So on the left triangle, the unvalued the cards are in green
and the overpriced cards on the right. Of course because the averaged priced, card is under
value and over value you know that is interacted to the ones which are closer to the lines of
fair price. What's interesting is the people who are out here outlier. And there is quite a
few. The reason why we have a lot of low value cards is because when we model cards our
card which have a shared ability are mainly lower value. Not because they the algorithm
favors one over the other just because when we did model, you can see on the side, model them
on the left side of the graph. Highest cards usually have special ability which is not
captured by this model. Which another one for a special ability. So no more blah, blah.
What is the result? Well one of the most under value card is Soulfire. We do believe it
actually should be at least one mana. Light's Justice is also undervalued. This one a lot of
people pointed out that they did use fro attacks for one mana which is somewhat of a kill if
you think about it. Not surprising the Mortal Coil or shield are not perfectly and
Argent Squire and there is also Explosive Trap and somehow it actually gives you something
which seems reasonable to most people. The one which is a bizarre is Sacrificial Pact,
probably a bug in the code. We also have high valued cards. The one which is most powerful is
fire which I believe it's probably seven mana or six. So somehow the algorithm gives you
reasonable results so we believe we're on the right track. If you want to look at it full detail,
all the partitions, all the card ranks they're on my website. You can just go there and we keep
updating it. And show how to make it better and we say let us know. How do you take it to the
next level? So far we have only used cards the question is how to make it better. It's really
difficult. At least without extra data. And this extra data is how people play the game.
Most of all the cards depend on the state of the game. We don't have insight about it unless you
have a lot of replay. Of course Hearthstone being very, very new we don't have that. So for
us we get our hand on the hundred games played between May and June. We'd like to thank our
friends for that. Thank you very much. We really hope that it will give Blizzard will give to
us and allow us to do our own analysis. I don't want to do too much but I think we're going to
look at things ‑‑ there is no reason to hide anything. (inaudible). With this data you
can do interesting stuff. The first one is you can price a card which has unique effect. To
get started. The Twilight Drake is a card which is a 41 for four mana and has special effects
when it comes into play it give a battle cry, it will give one half one additional half for
each card you have in your hand. Obviously the value of the card depends on how many cards you
have when you played it. So you can build a model, say if I have one card in my hand then you
have one extra hand and then it's one ‑‑ the real value is 1.3 mana. If I have two it's 1.9
up to nine. You have a maximum of ten cards. The maximum is nine so it's 5.9. The question
is now you are at this table you need to use replay data to be able to know how people played
it. Are many playing it with eight cards in their hands, four, two cards? You do it and
this thing is ‑‑ it draws a exact graph. What you see is the following. In the red on the
left side you see when people play it with less than up to four cards and the card becomes
undervalued. Basically if you play with four cards you get three mana values on your card.
If you play with five cards you have a 2.6 value. With six you have a 2.2 value. This is a
first one where if you play it with seven or eight you get the value of your cards. The average
real value of the card you take the averaged, is 3.7 which is right next to what is the face
value. So based on that we do think the price is fair. Basically exactly what it is.
It's also interesting to show that looking at this we get the same conclusion a blizzard so we
think we have something which is very similar to what they have. They have way better data and
better insight. Let's look at another card which is one of my favorite cards, Edwin VanCleef.
What it does is it will gain two for each time you play a card before it during the game. All
you have to do is look at the replay and how many cards were played during the turn before it
to get its value. And for reasonable number of cards played before I know you can go
way (inaudible) for reasonable number if you have two it's 1.09. If you have 6‑six you
begin to get value out of it. And when you play five or six cards the value is just
outrageous. If you play very, very different points. As you can see it is not at the time
undervalued. It is. Two cards before it ‑‑ I'm sorry three cards. No two cards before it
then you get five mana worth of your cards. And for four cards before you get to seven worth
the cards and so forth. So the average is 8.1. So the average value VanCleef is 8.1. So as you
claim this VanCleef is undervalued and I believe the value is between five and seven.
I believe it should not be eight, should not be nine. But three in my opinion is way too.
It is not according to the (inaudible). People play four for Chris but otherwise would
give you a 6‑six or 8‑eight. So this is one of the cards which is the most undervalued. Last
one. We go to a question about how you deal with (inaudible). So card which has (inaudible)
affect is one of the simplest ones. What it actually do is it does damage of the minion. So
easy right. All you have to do is count how many minion you have on the Board then multiply
by number of damage and voila right. I look at these numbers and there's something completely
wrong here right. Two minion on your cards is already worth 13 points of mana. Well
something is going wrong somewhere. It doesn't make any sense. What's wrong? It turns
out because we use the broad damage. Remember I told you we tried to be clever and single
targets versus multiple targets. This is what happens when you try to be too clever. Okay let's
try again. Go back to single card. Way better. Now it makes more sense. That's how we used
we should not use multi‑target versus single target. You should only use one board, not two. And
it makes sense. Now the card becomes a good deal when you have three minions. Same thing
you can see visually sometimes it's undervalued. Sometime it's overvalued. Most of the time
it's between the two so the card is perfectly balanced. The lesson is don't try to be too
smart. We also like this idea because actually looking at it helps us value it because we do
make sense. And when something is strange we look at it helps us validate and we're going to
tell you about how you can predict and will let you tell a little about that. >> Hello
everybody. My name is Celine and I'm going to show you in game two. The tool is a web
application written Titan. It runs on a small web server, called Flask. So you can just
get a web page. Just to your game as you can see on the screen. Or you can use any
devices with web browser such as a tablet. For this tool implements all the algorithms.
So the main screen in our tool is a realtime dashboard. Use it to track again metrics, play
cards, and predict the cards when you open and join your game. So the first box on top of
the game metrics. So mana advantage is difference between how much mana you spend and how
much mana you open and spend, At the page it is the difference between how many cards you drew
and how many cards you open and drew. And the other advantage is the difference between how many
cards you have in hand and how many cards you're opponent has in hand. So this metrics appears
in green. If you have the advantage. And in orange if the advantage is for your opponent.
In our study we found that those metrics are the most predictive of the game outcome. So we won't
go into details today due to lack of time, but we will do a blog post later about it.
Metrics you can see your deck. So you can see how many card of each type you have in your deck
in the two columns. Two for total. Which one of them are on the Board in green. And P for
played in red in the G Column. So below your deck there is a box that shows what cards your
opponent played. Every time your opponent plays a card, it will appear in this box. Same with
total card in your deck, T for Total in Column and played card in the P Column for played and
how many are dead in the two columns, D for dead. So below your deck there is a third box
that shows what cards your opponent played, overtime your opponent plays a card it will
appear in this box. Same with the total card in the T column and the dead card in the P
column and dead card in the T column. The last is the final box which will show you
prediction of which card your opponent is going to play based on the previous cards he's
played. So how did we manage to get the game data? We could use packet sniffing meeting to get
the game data. It gives you the best data which is a violation of bus ops of service so we
didn't use it. We could use OCR for good recognitions so it gives you a good data. But it
costs a lot of CPUs and is not very reliable. So we ruled it out. So we ended up using the
Debug log. So you can put your game in debit mode. It is a simple method to get awesome
data. But it has some limitations. Like game data you can see your opponent, play and
rank or which card attack which card and there's updates. So (inaudible) system as good as
the one in (inaudible). So now you will see it in action in a short video. So this is the left
side of the game. I am playing against him. So I show my card and you will see he starts with
an extra card in his hand because he has to draw and that advantage. I am picking up a
card. So we have the same number of cards as you can see on the dashboard. There's no more
advantage for Elie. Now I'm playing Argent Squire. So you can see the card will appear in
green in my deck. And I have spent one mana point. Now as the game evolves, the changes and
the prediction appears at the bottom. You can collect your data to get more room for your
(inaudible). And now I'm going to play advisory. And let's get a closer look. In the
prediction. So yes it's work. (Applause) He tries to kill me with (inaudible). (Laughter) It
saves me. In addition to the (inaudible) you can also see the (inaudible) in the screen. It
allows you to see what happened turn by turn during the game. So our tool will be available next
week on github. So we currently need help with how to improve points using OCR, currently
using text file. Need someone to display the game history, macquest, the Windows packaging
and (inaudible). If you want more info don't be afraid to talk to us after the
presentation. Thanks. Back to you now. (Applause) >> All right. Before you get all your
hopes too high, and tell you about how black magic is done. Just a word of disclaimer.
Because Naxramas has been released (inaudible) so some shifting, the prediction are not
accurate. As I said we don't have access to a lot of games. So it takes us awhile to build a
model, so expect it to not to perform well for the next few weeks. That being said, it will
catch up as soon as the number of cards has been released and tabulated. Probably next season.
Which is August. End of August. It's very simple. We model card affinity which is which card
plays with each other then we have an evaluation function which will return one of the
most affinity to be played based on previous cards played by your opponent. Then we have a tool.
The tool goes through a bunch of replay. Then learn from those played (inaudible). Then we have
this tool in the game which has the algorithm and shows the card that has been played and tells
me the most likely card to be played. That's basically what it looks like. We're going to see
each and that will be the last part of the talk. As I said, Hearthstone have about
500 yards. If we were to look at all the card combinations it would be almost impossible. We
would have an impossible number of combinations. So we expose the fact that in practice cards
really work well together and some cards do not work well together. You have the combo and
the combo is (inaudible) plus force of nature which is one. It's likely you have the other.
On the other hand, you do not have force of nature. Does it make any sense this is not what
you need to model? We model after things like this. We use simple system, you can see which
is called end run. Here is the simple versions which is called bigrams which is modeling pair
cards. What we look at is we look at the replay as the sequence of cards which has been
played by all opponents regardless of the turn and say the (inaudible) has been played
then the day played the task master. That's one bigram. We recall the infinity between the
two. We say if you played the armor with me then you are likely to play the task master.
We look at second part of the stream, well the task master is followed by accolades of pain so
we call there is an affinity between those two cards. That being said we know the cards are
random. Right. You get one card random so to model that we use what we call unordered engram.
Where we say (inaudible). If you play sometimes armor (inaudible) later you are likely to play
task master. You are likely to play (inaudible). We also try (inaudible). Turns out the best
model is in this one which is (inaudible). How do we value the cards? Very simple again. Daily
poison and shift which are two cards. Then we say what is the affinity of those cards? For
daily poison we know that that Fan of Knight and then blade 250 times. So we look at those. For
sure we know that Fairy has been 400 times and you played (inaudible). So we combine them
and again very simple (inaudible). We say how many times those appear you get the
ranking. The ranking is on top because it's 250 plus 400 one followed by the 500. And then
you put the card wherever you want and say this is my separation because I only want
two. That's how it works. It turns out more complicated it won't work. This one works
really well. How did we do? We took 50,000 replays and we did by class because each card has
some unique cards and we did one track. And we run the code, first we write the code then we
run the code. Then we ran. Actually the algorithm basically (inaudible) was in less than
three minutes. Then victory. I was actually shocked at how good the thing was. By turn three,
the highest prediction had a 97 percent chance to be played. Which mean that's out of 100
games, the first prediction returned after three will be played. Sometime in the future
we don't know if it is the next card but it will be played. If you want to look at it deeper,
this is a curve of the average prediction of the algorithm for ten predictions, turn by turn.
You can see actually why. Because you get more and more information. The more cards that
have been played the more we can look at the affinity so the accuracy increased and then it
starts to decrease after turn eight because there's less cards in the deck of your opponent. So
the balance is somewhat between times four and times eight. If you look at the ranking
functions. The ranking functions do work. The green represents our best prediction. The orange
represents our lowest prediction which is number ten. You can clearly see that the best one
actually extremely good up in the high 90s starting in at three whereas the lowest one is
barely above 20. And they are converging because the algorithm makes less and less mistakes but
there is also less and less room for error. So the last I wanted to tell you guys hindsight we
should have two hours and 45 minutes. We didn't know where we were going when we applied
for the talk. So we wanted to tell you about predicting the outcome. We also are looking
into optimizing that deck for mana. Because we know mana is the key factor to win. And by
popular request we're looking at proper requests and comparing deck of time. Why is winning
versus control, how it's work. What are the parameters and stuff. I think we are looking
forward to do is share ideas of things you would like us to do. We'd like to finish by giving a
shout out to a lot of people who gave us feedback. We love to do it! We read comment that's
people post to us. It's really important to help us get better. But that being said, big thank
you to you people. I would like to thank Neal and Zac which spent a lot of time helping us
prepare and gave us inside with feedback. And our anonymous friend who gives us replays.
Thanks a lot. (Applause)