Register

Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simulator)

Anything and everything about Cardcraft...err, Hearthstone.
Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simulator)

Postby raffy » Mon Dec 23, 2013 5:44 am

Note: this thread is temporary and will be moved to a more appropriate location if the project is successful. (I moved it.) -Al

Focus is a Hearthstone Simulator, currently under development. The main goal of the project develop a Hearthstone AI, which can be used to develop strategies, evaluate decks, solve for lethality, and experiment. The first goal of the project is solving lethal (boolean) in one-turn from a providing board state.

Original idea: viewtopic.php?f=3&t=4574&start=850#p20978
Image

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Mon Dec 23, 2013 5:45 am

Reserved #1
Image

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Mon Dec 23, 2013 5:45 am

Reserved #2
Image

Site Admin
User avatar
Posts: 273
Joined: Tue Mar 16, 2010 3:05 pm

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby Alaron » Tue Dec 31, 2013 2:35 am

Edgy,

Very interested in where this ends up and am happy to help where necessary. I'll be creating a separate Hearthstone forum sometime this week as I'm not doing much with WoW at the moment.

Not sure these are bugs, but here's an article that documents several edge cases:

http://ihearthu.com/30-bizarre-hearthstone-rules/

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Fri Jan 03, 2014 5:40 am

Cool. Now I just need to get version 1 released :p
Image

Site Admin
User avatar
Posts: 273
Joined: Tue Mar 16, 2010 3:05 pm

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby Alaron » Wed Jan 08, 2014 5:45 am

I've been digging around SlightlyMagic (http://www.slightlymagic.net/forum/) which seems to be a pretty interesting source for CCG simulation. Obviously, it's focused around MTG, but I imagine many of the problems are similar.

I agree with your current goal for the project (if nothing else, it could be used to create Hearthstone puzzles, which are fun) and I imagine we can probably find a solution that reduces permutations to an acceptable level eventually. My initial thought is options that force optimal play on the current board state (no trades, trades only if mana cost is equal, etc.)

Revered
Posts: 248
Joined: Wed Jul 31, 2013 10:50 pm

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby Tremnen » Fri Jan 10, 2014 12:03 pm

As someone who got stuck at Rank 3 last month this greatly interests me :D

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Sat Jan 25, 2014 2:22 am

Reserved #3
Image

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Sat Jan 25, 2014 2:29 am

Update #1
I just finished manually going through all of the cards and encoding them into a structured language that I hope to be able to interpret. First, I wrote some parsers for hearthpwn.com and hearthhead.com, and pulled all of the card data. I made a few attempts (starting from the first card alphabetically) at interpreting the cards but they failed miserably. I gave up with that approach and started extracting the easy stuff: Taunts, Charge, Divine, etc.. and then did single target Damage, AoE Damage, Heals. Eventually, after seeing enough cards, I think I figured it out, and came up with a pretty simple representation that can encode a significant amount of game logic. I expect that future patches (fixes to existing cards and introductions of new cards) can possibly be implemented purely through the card descriptions.
Code: Select all
{
   "id" : 64,
   "name" : "Swipe",
   "type" : "Spell",
   "cost" : 4,
   "url" : "CS2_012.png",
   "hero" : "Druid",
   "desc" : "Deal 4 damage to an enemy and 1 damage to all other enemies.",
   "text" : "When a bear rears back and extends his arms, he's about to Swipe! ... or hug.",
   "artist" : "Sean O\\u2019Daniels",
   "set" : "Basic",
   "quality" : "Common",
   "action" : {
      "action" : "Pick",
      "amount" : 4,
      "filter" : "E",
      "result" : "Damage",
      "and" : {
         "action" : "Select",
         "except" : true,
         "filter" : "E",
         "result" : "Damage"
         "amount" : 1,
      }      
   }
},

Code: Select all
{
   "id" : 272,
   "name" : "Cabal Shadow Priest",
   "type" : "Minion",
   "cost" : 6,
   "url" : "EX1_091.png",
   "hero" : "Priest",
   "ap" : 4,
   "hp" : 5,
   "desc" : "Battlecry: Take control of an enemy minion that has 2 or less Attack.",
   "text" : "You never know who may be secretly working for the Cabal....",
   "artist" : "Brian 'Chippy' Dugan",
   "set" : "Expert",
   "quality" : "Epic",
   "craft" : {
      "normal" : 400,
      "golden" : 1600
   },
   "disenchant" : {
      "normal" : 100,
      "golden" : 400
   },
   "action" : {
      "action" : "Pick",
      "filter" : "EM",
      "check-attack" : [0, 2],
      "result" : "Flip"
   }
},


I've already developed some proof of concept code that does a depth-first exhaustive scan of the game space for each turn. With the help of a cost function (like maximize value) and some pruning logic (like don't damage a friendly for zero gain), I expect to be able to take a board, and produce a universe of possible ending boards (one turn later), ranked and stored as a heap (in descending value.) There are often situations where the game space explodes (high mana, multiple damage abilities, on damage procs, randomness, many playable cards, flexable hero powers like Fireblast/Heal) so hopefully some of these permutations can be avoided. I'm still not sure how feasible all this is once more complex cards are in play, but I need the cards encoded and playable regardless of my actual simulation approach.

I'm still working out how everything actually works. I've been browsing around looking for hearthstone bugs on various forums and in strategy guides, . Bugs are very important as they help reveal some of the internal logic.
Image

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Sat Jan 25, 2014 2:30 am

Update #2
After implementing more of the features, it becoming apparent that full exhaustive search of the board space is not possible when you consider high mana turns with active minions + multiple playable minions w/different attack orders, placements, and targeted effects. You can easily branch to thousands of permutations from just 1 board-turn where many games go 16+ turns.

So I'm changing the first goal of the project to be a "what do I do next" simulator, where you will be easily able to import the board state, your hand and turn information, and then let it search the 1-turn board space and find you the top solutions that "maximize value" or "maximize surviving minions" etc.
Image

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Sat Jan 25, 2014 2:31 am

Update #3 (from email)
This is the basic model that I'm implementing:

GameState = a way to encode/decode the exact state of the game, including all minions/health/attack/weapon/buff/order/mana/hand/deck information. This form can represent a partial turn too. The GameState can represent any state of the game after the initial hand is selected. (I have a feeling that the proper mulligan response can be represented exhaustively for all 3-4 card permutations (30 choose 3 = 4060 / 30 choose 4 = 27405) for a known deck and there's probably a reasonable approximation for a random deck. Although I guess it does depend on enemy hero class.)

EndOfTurn(GameState) = function that produces a set of all possible final GameStates, starting from the given GameState until the end of the turn (resulting in change of control to opposite player, etc...)

The first iteration of the AI will assign a score to each GameState using some fitness function, like "Maximize Value", "Maximize Hand Size", "Maximize Damage". The GameStates can then be sorted and chosen from randomly (using the fitness as weight) and/or the best solution can be used.

The basic AI vs AI game is implemented like this:
Code: Select all
GameLogic logic = <<choose state with most value>>
GameState state = <<some game state>>;
while (state.alive()) { // P1.health > 0 and P2.health > 0
    state = logic(EndOfTurn(state)) // evolve a turn, choose best one according to logic, repeat
}


A cool use of the software would be to estimate your success rate from a given board state and suggest what actions you should take:
Code: Select all
GameLogic logic = <<choose state with most value>>
GameState state = <<your current game state>>; // including some guess at your opponents deck
loop (10000) {
   GameState copy = state.copy() // copy the game so we can randomize it
   copy.P1.deck.shuffle() // shuffle your deck
   // somehow shuffle P2 deck and hand
   GameState next = logic(EndOfTurn(copy)) // evolve your turn and save it
   GameState end = EvolveToEndOfGame(logic, next) // using above AI vs AI code to finish the game
   end.P1.health > 0 // record success/failure
}
Image

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Sat Jan 25, 2014 4:31 am

Because Kripp's chat after a Bomber is used hurts my head :)
Hearthstone Random Attack Calculator: http://raffy.antistupid.com/hs/rng.php
Image

User avatar
Posts: 14
Joined: Wed Jul 10, 2013 10:10 pm
Location: US-Sargeras

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby Shibumi » Sun Feb 02, 2014 3:50 am

How do you deal with "planning ahead"? i.e. The choice to hold cards that could be played on the current turn (and which might have had a useful effect), but that are better held until some as-of-yet unsurfaced cards are in play.
Shiboomi of <Riot> on US-Sargeras

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Mon Feb 24, 2014 3:17 am

Update #4
I keep getting a lot of interest concerning Focus via pmsg and email. I'm sorry there hasn't been more updates or any demos to share. All I can say is that I'm still playing with some ideas and working through some problems with my original ideas.

@Shibumi
Significant chain-combo plays are probably way beyond the scope of Focus. For one turn, sure. Spread out over many turns, no. The game space is just way too big to think that far ahead without a very intelligent AI.

I'm not interested in the actual AI development, instead I'm more interested in having a platform which lets me perform "Hearthstone calculations" (like evolve 1 turn, apply this card, what happens if I do this?, is this possible?, etc.) Once I have this working correctly, I can implement a pretty good AI for almost free, by just sorting the universe of possible outcomes by "Board+Card Value" and choosing one/some probabilistically.

raffy wrote:So I'm changing the first goal of the project to be a "what do I do next" simulator, where you will be easily able to import the board state, your hand and turn information, and then let it search the 1-turn board space and find you the top solutions that "maximize value" or "maximize surviving minions" etc.

This is what I'm shooting for, for version 1.

Some Thoughts
The biggest problem I've encountered with my exhaustive tree approach is the explosion that arises when you branch on cards with random effects: Bomber/Missiles/Kodo/etc. On one hand, I need to know what kinds of things are possible under all possible outcomes so I can solve the game exactly for 1-turn, but on the other hand, the random branching often only has a few branch-worthy paths -- either the board state changed significantly (something died, a card was drawn, a shield was broken, etc...) or it didn't (random damage done but no events triggered.) eg. Avenging Wrath on a full board of huge minions has like 6K+ possible outcomes.

Take the Mage Hero ability, for example: I have this implemented as: "pick 1 character, apply 1 damage." My code translates this into a set of possible options: "select 1 character" => generates all possible Choose[Characters,1] subsets, branches the game state for each one, and applies one damage to the selected target(s). Since I intend to need no actual game logic (although that's definitely possible as an intermediate pruning step) all possible actions must be considered (even dealing 1 damage to yourself.)

Take a Mad Bomber: I have this implemented as: "repeat 3 times: select 1 minion random, apply 1 damage". This has to be handled as 3 separate branches, considering a minion can die and stuff may trigger after each bomb. But luckily, since I know each of these branches has the same transition (apply 1 damage to a minion), there's a good chance some of game states (after 3 bombs) have the duplicates outcomes due to similar but different bombing sequences.
Image

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Sun Jul 27, 2014 6:00 am

Update #5
Focus is still alive and kicking however it doesn't see a lot of development time. Fortunately, the release of Naxx has invigorated my desire to simulate Hearthstone again. Over the last few months I've rewritten the implementation of most card effects about a zillion times trying to develop a concise yet complete way of describing all Hearthstone interactions w/o causing bugs or being able to correctly imitate strange behavior.

Initially, I focused too much on making the game execute properly and my card implementations lacked a lot of meta information. For example, to know that a card results in a Taunt, I had to clone the GameState, play the card, and then check that all possible next GameStates have a Taunt. My latest approach is far more queryable.

I've added branch support for all forms randomness, including random effects, play order, minion positions, and deck draw! This means given two decks and a sequence of events (to advance the GameState), it is possible to compute statistics across all possible outcomes. In this mode, searching out beyond one-turn is typically impossible for anything very complex. You can collapse random branching (so the simulator just picks one possible random result) either uniformly or based on some calculation across all GameStates for one action. Example: if you encounter a Bomber, you could random select amongst the GameStates where the most minions remain alive (shitty-case analysis.)

For ranked play, it should technically be possible after a few turns, to load in your deck, your guess at your opponents deck, the sequence of events that have occurred, the cards you've experienced so far, your guess at your opponents starting hand + cards played, and then exhaustively evaluate future board possibilities using depth-first search. You can accumulate possible GameStates that maximize some criteria, like minions-on-board or cards-in-hand or whatever. Later in the game, full random branching becomes impossible, but the focus of the game eventually becomes a search for lethal which only requires finding a single solution. Note: as stated earlier, the goal of this project is not to build a bot or automate constructed play.

Zoo has been a problem because I haven't developed a good way to reduce GameState searches that involve minion play order or placement but have the same outcomes. Example: 7+ mana, 7 (1) drops held => 7! final board orderings but also 7! ways to play the cards. 7!*7! = 25.4M GameStates. If you had a Soul Fire, you could interleave it by attacking any possible target and cause a random discard which branches to a ridiculous number of GameStates.

It is possible (especially for early game) to directly compute best possible plays for certain criteria. Example: directly computing the probability of survival across all possible next turn plays, directly computing the play which results in not dying by next turn, computing lethal, etc... It should even be possible to find "maximum BM" sequences, assuming there's some way to decide BM(GameState1) > BM(GameState2) :p

Edit: I have lots of interesting ideas about simulation possibilities. Example: say you have a game you lost, after your opponent drew 10 cards, you drew 9, ended on turn 7, ... etc. Keep a sequence of all actions taken. Evolve a GameState to your turn before death, then evolve all possible forward GameStates and compute win probability. Evolve a GameState to the next turn earlier, again compute win probability. Repeat until it becomes impossible. Look through the results for mistakes or suggestions for better possible plays.
Image

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Mon Jul 28, 2014 3:54 am

Some random card implementations:
Swipe
Spoiler: show
Code: Select all
{
   "id" : 64,
   "name" : "Swipe",
   "type" : "Spell",
   "cost" : 4,
   "ref" : "CS2_012",
   "hero" : "Druid",
   "desc" : "Deal 4 damage to an enemy and 1 damage to all other enemies.",
   "text" : "When a bear rears back and extends his arms, he's about to Swipe! ... or hug.",
   "artist" : "Sean O\\u2019Daniels",
   "set" : "Basic",
   "quality" : "Common",
   "origin" : { "normal" : 8, "golden" : 47 },
   "impl" : {
      "spell" : "PickSingle",
      "filter" : "EnemyCharacter",
      "do" : [
         { "type" : "SpellDamage", "amount" : 4 },
         {
            "type" : "SelectAll",
            "filter" : "EnemyCharacter",
            "exclude" : true,
            "do" : [ { "type" : "SpellDamage", "amount" : 1 } ]
         }
      ]
   }
}

Cold Blood
Spoiler: show
Code: Select all
{
   "id" : 268,
   "name" : "Cold Blood",
   "type" : "Spell",
   "cost" : 1,
   "ref" : "CS2_073",
   "hero" : "Rogue",
   "desc" : "Give a minion +2 Attack. Combo: +4 Attack instead.",
   "text" : "\"I'm cold blooded, check it and see!\"",
   "artist" : "Alex Horley Orlandelli",
   "set" : "Expert",
   "quality" : "Common",
   "craft" : [ 40, 400 ],
   "disenchant" : [ 5, 50 ],
   "impl" : {
      "combo" : {
         "0" : {
            "type" : "PickSingle",
            "filter" : "AnyMinion",
            "do" : [ { "type" : "AddAttack", "amount" : 2 } ]
         },
         "1" : {
            "type" : "PickSingle",
            "filter" : "AnyMinion",
            "do" : [ { "type" : "AddAttack", "amount" : 4 } ]
         }
      }
   }
}

Snake Trap
Spoiler: show
Code: Select all
{
   "id" : 455,
   "name" : "Snake Trap",
   "type" : "Spell",
   "cost" : 2,
   "ref" : "EX1_554",
   "hero" : "Hunter",
   "desc" : "Secret: When one of your minions is attacked, summon three 1\/1 Snakes.",
   "text" : "Why did it have to be snakes?",
   "artist" : "Bernie Kang",
   "set" : "Expert",
   "quality" : "Epic",
   "craft" : [ 400, 1600 ],
   "disenchant" : [ 100, 400 ],
   "impl" : {
      "spell" : "Secret",
      "when" : "OnAttack",
      "attacker" : "AnyCharacter",
      "defender" : "FriendlyMinion",
      "do" : [
         { "type" : "Summon", "cards" : [ 204 ],  "amount" : 3 }
      ]
   }
}

Blood Imp
Spoiler: show
Code: Select all
{
   "id" : 469,
   "name" : "Blood Imp",
   "type" : "Minion",
   "cost" : 1,
   "ref" : "CS2_059",
   "hero" : "Warlock",
   "race" : "Demon",
   "attack" : 0,
   "health" : 1,
   "desc" : "Stealth . At the end of your turn, give another random friendly minion +1 Health.",
   "text" : "Imps are content to hide and viciously taunt everyone nearby.",
   "artist" : "Bernie Kang",
   "set" : "Expert",
   "quality" : "Common",
   "craft" : [ 40, 400 ],
   "disenchant" : [ 5, 50 ],
   "impl" : {
      "auras" : [
         {"type" : "Stealth"},
         {
            "type" : "OnTurnEnd",
            "do" : [
               {
                  "type" : "SelectRandom",
                  "filter" : "FriendlyMinion",
                  "exclude" : true,
                  "do" : [
                     { "type" : "AddHealth", "amount" : 1 }
                  ]
               }
            ],
         }
      ]
   }
}

Anub'ar Ambusher
Spoiler: show
Code: Select all
{
   "id" : 1810,
   "name" : "Anub'ar Ambusher",
   "type" : "Minion",
   "cost" : 4,
   "ref" : "FP1_026",
   "hero" : "Rogue",
   "attack" : 5,
   "health" : 5,
   "desc" : "Deathrattle: Return a random friendly minion to your hand.",
   "text" : "Originally he was called \"Anub'ar Guy who bounces a guy back to your hand\", but it lacked a certain zing.",
   "artist" : "Mike Nicholson",
   "set" : "Naxxramas",
   "quality" : "Common",
   "origin" : {
      "normal" : "Unlocked by completing the Rogue Class Challenge in Naxxramas.",
      "golden" : "Can be crafted after completing the Rogue Class Challenge in Naxxramas."
   },
   "impl" : {
      "deathrattle" : {
         "type" : "SelectRandom",
         "filter" : "FriendlyMinion",
         "do" : [
            {"type" : "ReturnCard"}
         ]
      }
   }
}


Edit: more examples, simplified
Avenge
Code: Select all
"spell":"Secret",
"when":"OnDeath",
"filter":"FriendlyMinion",
"do":[{"type":"SelectRandom","filter":"FriendlyMinion","do":[{"type":"AddAttack","amount":3},{"type":"AddHealth","amount":2}]}]

Timber Wolf
Code: Select all
"auras":[{"type":"SelectAll","filter":{"unit":"FriendlyMinion","race":"Beast"},"exclude":true,"do":[{"type":"AddAttack","amount":1}]}]

Defender of Argus
Code: Select all
"battlecry":{"type":"SelectAdj","do":[{"type":"AddAttackAndHealth","amount":1},{"type":"Taunt"}]}

Totemic Call
Code: Select all
"spell":"SummonRandom",
"unique":true,
"cards":[764,537,850,458]

Truesilver Champion
Code: Select all
"auras":[{
"type":"BeforeAttack",
"attacker":"FriendlyHero",
"defender":"AnyCharacter",
"do":[{"type":"SelectAll","filter":"FriendlyHero","do":[{"type":"Heal","amount":2}]}]
}]

Deathwing
Code: Select all
"battlecry":[{"type":"SelectAll","filter":"AnyMinion","do":[{"type":"Destroy"}]},{"type":"Discard","amount":0}]

Demolisher
Code: Select all
"auras":[{"type":"OnTurnStart","do":[{"type":"SelectRandom","filter":"EnemyMinion","do":[{"type":"Damage","amount":2}]}]}]

Mortal Coil
Code: Select all
"spell":"PickSingle",
"filter":"AnyMinion",
"do":[{"type":"KillingBlow","do":[{"type":"Draw"}]},{"type":"SpellDamage","amount":1}]

Forked Lightning
Code: Select all
"spell":"SelectRandom",
"require":2,
"amount":2,
"filter":"EnemyMinion",
"do":[{"type":"SpellDamage","amount":2}],
"overload":2

Stampeding Kodo
Code: Select all
"battlecry":{"type":"SelectRandom","filter":{"unit":"EnemyMinion","attack-max:":2},"do":[{"type":"Destroy"}]}

Healing Totem
Code: Select all
"auras":[{"type":"OnTurnEnd","do":[{"type":"SelectAll","filter":"FriendlyMinion","do":[{"type":"Heal","amount":1}]}]}]

Mad Bomber
Code: Select all
"battlecry":{"type":"Repeat","amount":3,"do":[{"type":"SelectRandom","filter":"AnyCharacter","exclude":true,"do":[{"type":"Damage","amount":1}]}]}

Avenging Wrath
Code: Select all
"do":[{"type":"SpellRepeat","amount":8,"do":[{"type":"SelectRandom","filter":"EnemyCharacter","do":[{"type":"Damage","amount":1}]}]}]
Image

Site Admin
User avatar
Posts: 273
Joined: Tue Mar 16, 2010 3:05 pm

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby Alaron » Tue Jul 29, 2014 12:33 am

As it happens, I've just poked my head back in as well, so good timing. :) It looks like you came up with a good schema for the cards.

Offhand, the feature I'd be looking for the most is Monte Carlo simulation. 2 preset decks, some common-sense limitations to increase sim speed (obviously with a single random branch choice) and tons of iterations. Could reveal some interesting information.

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Tue Jul 29, 2014 5:44 am

I suspect that even the simplest pruning of the game tree -- collapsing random effects, avoiding friendly-fire, collapsing unit placement, collapsing card play order -- will give ridiculous speed ups. My hope is that a reasonable class-specific AI will be able to branch forward a few turns.

You could get near instantaneous full-game simulations by never branching and just playing randomly (using cards weights). Unfortunately, there's a huge gap in program-complexity between computing one possible outcome and computing all possible outcomes. Especially when you have the intention of inserting hooks that can analyze this process and eventually simplify it. Additionally, it's been difficult to ensure the simulator will function like the real game. For example, tonight I was stepping through Youtube videos to figure out how Coldlight Oracle draw (2 cards per player) is ordered: [A,B,A,B], [B,A,B,A], [A,A,B,B], [B,B,A,A], ... The other week I was reading about Pint-sized + Summoning Portal. There's a long list of "bugs" that have been useful for deconstructing the internal game logic.

w/r/t the card schema, I'm glad I finally found a representation that has allowed me to add a lot of cards without requiring additional language tweaks. I've handwritten 684? card implementations so far, and I can't tell you how many times I got half way through the list and realized my current language isn't sufficiently expressive or too ambiguous :(

In an upcoming post, I'll outline some of the supported features and explain their various required/optional arguments:
- Boolean Auras (Taunt, Shield, Charge, Windfury, Stealth, Untargetable, Stunned, Frigid, Poisonous, ...)
- Valued Auras (Deathrattle, TempAura, SpellPower, Attack, Health, Events, ...)
- Events (OnDeath, OnAttack, OnSummon, OnDamageHealed, OnTurnStart, OnTurnEnd, OnSecret, OnOverload, ...)
- Actions (Draw, Discard, Return, Transform, Destroy, Copy, Resurrect, Damage, Heal, Choose, SplitDamage, Control, Consume, ...)
- Card Features (Do, Battlecry, Choose, Combo, ...)
- Game Features (AddMana, DestroyMana, AddCost, SetCost, ...)
- Modifiers (AddAttack, AddArmor, AddHealth, TempAttack, SetHealth, ...)
- Selection Functions (Pick, SelectAll, SelectRandom, WithRoot, WithAdj, SummonIntercept, TargetRedirect, ...)
- Logic Functions (Repeat, Count, IfAura, IfSelect, ...)

There is still some functionality that I am still refactoring:
- Betrayal/Gladiator Longbow (ImmuneWhileAttacking)
- Gorehowl (AttackAsDurability)
- Holy Wrath (unsure about what shit can occur between the Draw and the spell attack, can I have variable "LastCardCost")

Things on my radar:
- develop a simple to write Before/After test suite (GameStateInitial + [action list] + GameStateFinal)
- create tons of examples to test card functionality
- first-generation test: confirm Initial = Final
- second-generation test: find the set of [action list]'s that gets you from GameStateInitial to GameStateFinal, confirm [action list] is a member of this set.
Image

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Tue Jul 29, 2014 5:33 pm

Thinking further about the Before/After test suite, I realize there is some complexity in describing how certain actions execute.

Imagine you play Arcane Missiles on a board with 7 1/1 minions.
How should I describe this result?
How does the simulator know that Arcane Missiles can perform this result?

IMO the Before/After representation is just a sequence of user-inputs and random-results. For example, "Attack(1,2)", "HeroPower", "Pick(7)", would mean something like, "Use Unit#1 to Attack Unit#2", "Use HeroPower" (say it's Fireblast), "Pick Unit#7 as Target".

However, any game decision should be evolvable from the current GameState, so "Attack(1,2)" is actually just equivalent to a branch possibility, which corresponds to the index of the GameState in the Universe of possible GameStates. "Attack(1,2)" is the 32417-th action possible from the current GameState, after that action is performed, "HeroPower" is the 644-th action possible for the resulting GameState, etc... So the full sequence of inputs can be compiled to something like {32417, 644, 1120}. For example, Flare on Turn 1 would branch as 8775 (27 choose 3) * (3 choose 1) possible actions when deck-order isn't specified and deck-branching is enabled. A Before state that saw {ArcaneShot, UTH, Yeti} and chose UTH could be described as "GameState 4207 of 8775".

Back to the original question, if I assume Arcane Missiles is Card #3:
Inputs: {PlayCard(3), Pick(1), Pick(6), Pick(7)}
Compiled Branches: {12309124, 17, 3, 175}
Image

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Wed Jul 30, 2014 12:11 am

List of Other Hearthstone Projects
Hearthstone Simulator: https://github.com/danielyule/hearthstone-simulator
HearthSim: https://github.com/oyachai/HearthSim
Hearthcrawler: http://www.thecrawlerforum.com/index.ph ... Downloads/
HearthstoneBot: https://github.com/HearthstoneBot/HearthstoneBot
HRCustomClasses: https://github.com/noHero123/HRCustomClasses
Hubot: https://github.com/sylturner/hubot-hearthstone
Hearthstone Emulator: https://github.com/HearthStone/Hearthstone
Hearthstone AI: https://github.com/sihrc/Hearthstone-AI
Hearthstone: https://github.com/ducino/hearthstone
HearthStone: https://github.com/magicdict/HearthStone
Hearthstone Deck Tracker: https://github.com/draco098/hs-deck-tracker
Hearthstone Card Repo: https://github.com/jasonHooten/hearthstone-card-repo
Hearthstone Cards: https://github.com/reflection/Hearthstone-Cards
HearthstoneJson: https://github.com/Sembiance/hearthstonejson

Of the simulators listed, none support exploratory branching. HRCustomClasses/MiniSimulator appears to try certain combinations for specific situations. Hearthstone-Simulator has a test suite. I don't see a lot of copyable GameStates either (many projects use anonymous functions to implement mechanics which capture references to objects that can't be cloned properly.) Implementation-wise, I'm surprised by how many projects treat Taunt as a boolean, rather than an Aura. No projects appear to implement cards through a DSL. The projects with DLL injections are interesting, but their AI instructions are very basic.
Image

Exalted
User avatar
Posts: 842
Joined: Tue Oct 23, 2012 7:15 am

Re: Edgy/Raffy's Official 'Focus' Thread (Hearthstone Simula

Postby raffy » Fri Aug 01, 2014 3:06 am

Card Implementation Documentation *** Under Construction ***

Core Concepts
Code: Select all
-- all actions need to be written such that they can be automatically branched
-- the "Root" card is the underlying minion/spell


Supported Types
Code: Select all
// destination player (String)
dst = You | Enemy | Both | Opposite
-- Opposite is used for events, which can trigger for Both player

// source player (String)
src = You | Enemy | Both | Opposite

// type of card (String)
cardType = Type | Race | Tag
-- Type = Spell | Minion | Hero | Power
-- Race = Beast | Pirate | Demon | Dragon | Murloc | Totem
-- Tag = Skeleton | Dream | Mekka // meta properties, will add more later

// card used when card query cannot be completed (Integer)
underflow = CardId

// integer value
IntegerValue = Integer | IntegerFunction
-- Integer = 0 | 1 | 2 | ...
-- IntegerFunction = {"fn":NameOfFunction, ... } // see below

// amount
amount = IntegerValue | Range
-- Range = [IntegerValue, IntegerValue]

// require (minimum amount)
require = Integer



Drawing brings a card into a hand.
Code: Select all
Draw            dst=You amount=1 card
DrawRandom       dst=You amount=1 cards
DrawFromDeck     dst=You amount=1 cardType=Any src=You underflow=None
DrawFromHand     dst=You amount=1 cardType=Any src=You underflow=None
DrawFromUniverse dst=You amount=1 cardType=Any

Examples:
Code: Select all
// on death, draw a random beast card from entire universe
"deathrattle":{"type":"DrawFromUniverse","cardType":"Beast"},

// on played, draw a thing for each player
(once these cards are tagged as "ETC", convert to DrawFromUniverse)
"battlecry":{"type":"DrawRandom","dst":"Both","cards":[1843,1845,1846]}

// on played, give enemy two bananas
"battlecry":{"type":"Draw","dst":"Enemy","card":1694,"amount":2}

// on turn end, draw a dream card
(like above, this should also be converted to DrawFromUniverse)
"auras":[{"type":"OnTurnEnd","do":[{"type":"Draw","cards":[217,301,340,489,808]}]}]

// on spell, draw 2 demons from deck, use 1723 if no demons
"do":[{"type":"DrawFromDeck","amount":2,"cardType":"Demon","underflow":1723}]

// on spell, draw 4 cards (sprint)
"do":[{"type":"Draw","amount":4}]


Summoning brings a minion onto the board. cardType is implicitly a minion. Action will throw if matching card is not a minion.
Code: Select all
Summon         dst=You amount=1 card
SummonRandom   dst=You amount=1 cardType? cards
SummonFromDeck dst=You amount=1 cardType? src=You underflow?
SummonFromHand dst=You amount=1 cardType? src=You underflow?

Examples:
Code: Select all
// on death, summon minion
"deathrattle":{"type":"Summon","card":1795}

// on death, summon random minion from enemy deck to enemy side
"deathrattle":{"type":"SummonFromDeck","dst":"Enemy","src":"Enemy"}

// on played, summon an invention!
"battlecry":{"type":"SummonRandom","cards":[329,146,227,52]}

 // on played, summon two whelps
"battlecry":{"type":"Summon","dst":"Enemy","card":54,"amount":2}

// on spell, summon doge for each enemy minion
"do":[{"type":"Summon","amount":{"fn":"Count","filter":"EnemyMinion"},"card":1715}]

// on spell, summon from enemy deck, use 1720 if no cards
"do":[{"type":"SummonFromDeck","src":"Enemy","underflow":1720}]


Filtering will decide which game objects should be operated on. A filter construct is a key component of various actions.
Code: Select all
// a filter is made up a single filter or a list of filters (which are logically joined via "or")
"filter" = Filter | [Filter1, Filter2, ...]

// a Filter can be specified by name (which is typically relative), by object kind, or by a full description 
Filter = Named | Kind | Description

// named filters reference nearby units of the Root unit
Named = {Root, Adj, Left, Right}

// kinds are shortcuts to a description that just specifies the corresponding kind
Kind = {AnyCharacter, EnemyCharacter, FriendlyCharacter, AnyMinion, FriendlyMinion, EnemyMinion, AnyMinion, FriendlyMinion, EnemyMinion, AnyWeapon, FriendlyWeapon, EnemyWeapon}

// a full Filter description, all fields are optional
Description = {
  "kind" = ObjectType     
  "race" = RaceType       // eg. hungry crab
  "attack-min" = Integer  // eg. shadow word: death
  "attack-max" = Integer  // eg. kodo
  "health-min" = Integer
  "health-max" = Integer  // eg. mortal strike
  "damaged = Boolean      // eg. execute
  "aura" = String         // eg. blood knight
  "except" = Filter       // eg. dream
}


Selecting will map a set of actions across any matched object. The filter argument has all of the complex behavior. require will prevent a Spell from casting if it is the top-level action. Auras that have selections will be interpreted as matching criteria rather than a one-time selection.
Code: Select all
SelectAll    filter require? do
SelectRandom filter require? do amount
SelectRoot ==> SelectAll filter=Root
SelectAdj  ==> SelectAll filter=Adj

Examples:
Code: Select all
// on played, mind control if sufficient
"battlecry":{"type":"SelectRandom","require":4,"amount":1,"filter":"EnemyMinion","do":[{"type":"Control"}]}

// on played, deathwing :p
"battlecry":[{"type":"SelectAll","filter":"AnyMinion","do":[{"type":"Destroy"}]},{"type":"Discard","amount":0}]

// on played, destroy weapon
"battlecry":{"type":"SelectAll","filter":"EnemyWeapon","do":[{"type":"Destroy"}]}

// on spell, equality
"do":[{"type":"SelectAll","filter":"AnyMinion","do":[{"type":"SetHealth","amount":1}]}]

// on spell, cone of cold
"do":[{"type":"SelectAll","filter":["Root","Adj"],"do":[{"type":"Freeze"},{"type":"Damage","amount":1}]}]

// minion aura, stormwind champion
"auras":[{"type":"SelectAll","filter":{"kind":"FriendlyMinion","except":"Root"},"do":[{"type":"AddAttackAndHealth","amount":1}]}]

// on spell, holy nova
{"type":"SelectAll","filter":"EnemyCharacter","do":[{"type":"Damage","amount":2}]},
{"type":"SelectAll","filter":"FriendlyCharacter","do":[{"type":"Heal","amount":2}]}

// on played, blood knight
"battlecry":{"type":"SelectAll","filter":{"kind":"AnyCharacter","aura":"Shield"},"do":[{"type":"Reveal"},{"type":"WithRoot","do":[{"type":"AddAttackAndHealth","amount":3}]}]}
Image

Return to Hearthstone General Discussion

Who is online

Users browsing this forum: No registered users and 2 guests