Register

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

Anything and everything about Cardcraft...err, Hearthstone.
Exalted
User avatar
Posts: 833
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: 833
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: 833
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: 272
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: 833
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: 272
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: 247
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: 833
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: 833
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: 833
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: 833
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: 833
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: 833
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

Return to Hearthstone General Discussion

Who is online

Users browsing this forum: No registered users and 1 guest