In diesem Post werde ich etwas über mein aktuelles Freizeitprojekt “HearthstoneCalc” berichten. Ich werde fortsetzende Posts über das Tool danach richten, wie interessiert Ihr Leser an den Artikeln seid. Schauen wir mal

Ich interessiere mich schon länger für Spiele KIs und bin der Überzeugung, dass Computer bei der Planung von Spielzügen weit effektiver sind als ein menschliches Gehirn. Dabei geht es nicht um die Kreativität die ein menschlicher Spieler an den Tag legt, sondern die reine rationale Beurteilung der Spielsituation. Schachcomputer sind inzwischen ungeschlagen, weil sie einfach Unmengen an Situationen vorraussehen und bewerten können. Seid einiger Zeit fasziniert mich das Spiel “Hearthstone“, ein Rundenbasiertes Kartenspiel ähnlich Magic oder Yu-Gi-Oh. Man kann Diener oder Zauber spielen, die eigenen Heldenfähigkeiten nutzen oder mit Waffen die Kontrolle über das Board behalten. Der Spielverlauf wird später nochmal genauer erklärt, jetzt geht es erstmal um das Programm “HearthstoneCalc”.

Ziel des Programms ist es, alle möglichen Züge zu eruieren und den besten auszuwählen. Dabei sollte das Programm den aktuellen Spielstatus auslesen, die Berechnungen durchführen und den Spielzug selbstständig ausführen. Im Gegensatz zu Spielen mit perfekten Informationen wie Schach oder Vier-Gewinnt haben wir bei Hearthstone drei große Probleme:

1. Die gegnerischen Karten sind unbekannt. Zwar werden von den Spielern meist ähnliche und als effektiv geltende Decks gespielt, allerdings varieren auch hier die Karten. Die Karten des Gegners die er auf der Hand hat sind verdeckt und bieten daher keine perfekten Informationen über zukünftige Spielzüge
2. “Hearthstone braucht keinen Skill, sondern nur Glück“. An diesem Zitat ist leider viel wahres dran. Viele Zauber wirken auf alle Einheiten verteilt und viel Schaden (z.B. von explodierenden Bomben) ist variabel. Glück gehört einfach zum Spiel dazu, daher kann man den Ausgang eines Zuges nicht effektiv berechnen. Man muss mit Wahrscheinlichkeiten rechnen, und davon nicht wenige. Später gibt es ein Beispiel, wie komplex ein solcher Zug sein kann.
3. Manche Decks verfolgen eine spezielle Strategie und sammeln daher Karten, um einen großen Zug zu machen. Solch eine “Strategie” bringt man dem Computer schlecht bei, vorallem da er nebenher darauf achten muss, nicht gegen den Gegner zu verlieren.

Ihr merkt, das Projekt wird komplex. Und ein solches Projekt fängt man am besten an, indem man abstrahiert und vereinfacht. Ein solch einfaches Modell kann dann später erweitert werden. Effektiv heißt das auf die beiden oberen Punkte bezogen: Wir schauen zunächst nur den aktuellen Zug unseres Spielers an und lassen die mögliche gegnerische Reaktion außer Acht. Zudem berechnen wir nur die Züge ohne Wahrscheinlichkeiten bzw Rechnen mit dem schlimmsten Ausgang für uns.

Soweit zu Theorie. Es folgt eine kleine Einführung in den Spielablauf von Hearthstone, dann abstrahieren wir das Ganze und schauen wie der Computer damit klarkommt. Fangen wir mit den Grundelementen an, erklärt anhand eines Screenshots. Ich werde dabei vorallem die englischen Begriffe verwenden, da viele Tuniere auf Englisch ausgetragen werden und es sich einfach besser anhört.

Ziel des Spiels ist es, das Leben des gegnerischen Helden auf 0 zu bringen. Der Held des Spielers ist der untere, bei welchem auch die Karten sichbar sind. Das Spielfeld ist mit 2 gegnerischen Minions (Dienern) und einem Minion von uns gefüllt. Jedes Minion hat folgende Eigenschaften: Manakosten, Angriff und Leben. Das Ausspielen einer Karte kostet Mana, daher können wir nicht alle Karten auf einmal ausspielen und manche Karten erst nach einigen Zügen. Denn nach jedem Zug wird unser Mana wieder aufgefüllt und ein Manapunkt bis max. 10 addiert.

Im Spiel gibt es neun Helden, die jeweils eine einzigartige Hero-Power besitzen. Diese kostet 2 Mana und kann jeden Zug einmal verwendet werden. Da wir ein Jäger (Hunter) sind, können wir dem Gegner jeden Zug für 2 Mana 2 Schaden zufügen. Der Gegner wiederrum (Magier) kann je einem Ziel (unser Held oder ein Minion) einen Punkt Schaden zufügen. Ausgespielte Minions brauchen in der Regel einen Zug, damit sie angreifen können. Dabei können sie endweder andere Minions angreifen oder direkt die Lebenspunkte des Gegners attackieren. Bei Angriff auf ein gegnerischen Minion wird dem eigenen Minion die Anzahl Lebenspunkte abgezogen, die das gegnerische Minion als Angriff hat. Andersrum natürlich genau so.

Damit haben wir schonmal mögliche Spielzüge aufgelistet:

• Wir können Minions ausspielen
• Wir können die Hero-Power verwenden
• Wir können eine andere Karte (Zauber, Waffe, Geheimnis) ausspielen
• Wir können mit einem Minion angreifen (Gegnerischen Helden oder Minion)

Leider ist die Sache mit den Minions nicht so einfach. Denn auf der einen Seite können sie bestimmte Abilities haben, auf der anderen Seite haben viele Minions “Battlecries” und “Deathrattles“. Fangen wir mit den (meistgesehen) Abilities an:

• Taunt (Spott): Wenn ein Minion mit Taunt auf dem Spielfeld ist, muss dieses Angegriffen werden. Angriffe auf andere Minions ohne Taunt oder auf den Gegner sind nicht möglich
• Stealth: Minions mit Stealth können nicht attackiert werden, bis sie selbst zum ersten mal Angreifen und dabei den Stealth verlieren
• Devine Shield: Minions mit Devine Shield verlieren beim ersten mal Schaden einstecken kein Leben, sondern nur das Devine Shield
• Windfury: Minions mit Windfury können zweimal pro Zug angreifen

Ziemlich viele? Es gibt insgesammt 20 davon! Für uns ist das natürlich in der Berechnung des entstehenden Spielfelds wichtig. Deathrattle und Battlecry sind allerdings leicht erklärt: Der Battlecry wird ausgeführt wenn das Minion ausgespielt wird, der Deathratte geschieht wenn das Minion stirbt. Im oberen Beispiel wird der “Haunted Creeper” beim Sterben zwei Spinnen spawnen, die jeweils 1 Attacke und 1 Leben haben. Andere Minions haben z.B. als Battlecry, dass sie dem gegnerischen Helden Schaden zufügen.

Auf spezielle Karten wie Secrets oder Waffen werde ich hier nicht eingehen, da das nur für bestimmte Heldenklassen interessant ist.

Nachdem wir wissen was wir alles in einem Hearthstone-Zug anfangen können, machen wir uns jetzt an die Abstraktion. Schließlich wollen wir ein Modell von Hearthstone haben und das muss mit dem Spiel identisch sein. Dazu habe ich mir folgende Klassen überlegt:

• GameState: Die wahrscheinlich wichtigste Struktur bisher, denn sie repräsentiert einen möglichen oder aktuellen Spielstatus. Dieser enthält neben den beiden Helden und ihren Lebenspunkten die aktuellen Karten des Spielers auch alle Minions die auf dem Feld sind.
• GameTurn: Wenn man sich die GameStates als Knoten vorstellt, so sind die GameTurns die Kanten zwischen verschiedenen Game-States. Ein GameTurn steht für eine Spieleraktion, z.B. das Ausspielen einer Karte, das verwenden der Heropower oder das Angreifen mit einem Minion.
• Minion: Enthält neben dem Leben, den Manakosten und den Angriffspunkten Funktionszeiger auf Deathrattle und Battlecries. Die Flags des Minions sind hier gelistet und auch mögliche Buffs gespeichert.
• Weapon, Secret und Spell, die hier nicht weiter besprochen werden.

Schlüssel der ganzen KI ist die Bewertung der entstehenden Spielstati. Natürlich bekommt der Zug das höchste Ranking, wenn der Gegner auf 0 oder weniger Lebenspunkte gebracht werden kann. Bewertet werden die ausgespielten Minions auf dem Feld, die eigenen und generischen Lebenspunkte sowie die Anzahl der Karten auf der Hand. Diese Funktion ist in ihren bisherigen 15 Zeilen noch sehr am Anfang und wird wahrscheinlich komplexer als die ganze andere Logik des Programms werden.

Damit haben wir den etwas trockenen aber nötigen Einführungsteil abgeschlossen. Ab nächstes mal können wir (hoffentlich bis dahin visualisert) verschiedene Züge anschaun und die Bewertung optimieren. Zudem haben wir noch ein paar Probleme zu lösen, die Hearthstone uns in den Weg schmeißt: die Plazierung von Minions auf dem Spielfeld spielt eine taktische Rolle, manche Minions lösen eine Aktion nach einem bestimmten Trigger aus und manche Minions haben noch eine Klassenzuhgehörigkeit (Mech, Beast, Dragon).