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.

Weiterlesen

7 people like this post.

Like

Unlike

Heute geht es um präzise tickende Maschienen und ein Projekt, das nun doch ziemlich komplex geworden ist. Ein Stämme Bot!

Doch zunächst etwas in eigener Sache: Vielleicht bist Du hier, weil Du mehr oder weniger freiwillig von Keller-Elite auf diese Seite weitergeleitet wurdest. Hoschi111 war so nett, nach der Schließung von Keller-Elite die User hier her zu leiten. Ist eine große Ehre für mich und ich hoffe es gibt hier den ein oder anderen Artikel der Dich interessiert.

Ich weis nicht, ob Du schon Erfahrung im Browsergame “Die Stämme” gemacht hast. Wenn nein, hier eine kurze Einführung: Um ein anderes Dorf zu erobern (im Stämmejargon auch “adeln”) muss man zwischen 3 und 5 erfolgreiche Angriffe mit einem Adelsgeschlecht auf das Dorf führen. Jedes Adelsgeschlecht (kurz AG) senkt die Zustimmung der Bevölkerung um 20-35 Prozent. Nach und nach sind die Dorfbewohner gewillt zum Angreifer überzulaufen. Dies möchte der Verteidiger natürlich verhindern und schickt allerei Defensive Einheiten in den Kampf um das Dorf zu verteidigen. Manchmal ist die Übermacht aber so groß, dass die eigene Verteidigung nicht standhält. Und dann tritt Plan B in der Kraft: Das “raustimen”. Da die große Offensive vor den AGs angreifen muss, um das Dorf von jeglicher Verteidigung zu befreien, laufen verschiedene Angriffswellen auf ein Dorf. Zumeist sind das ein bis zwei große Offensiven und direkt dahinter die AGs. Die AGs greifen meist mit nur geringem “Begleitschutz” an, denn eigentlich ist das Dorf ja leer. Und meist werden alle verfügbaren Einheiten bei der großen Offensive gebraucht.

Der Clou ist nun das “Timen” dieser Angriffe. Man möchte dem Verteidiger möglichst wenig Chancen geben, zwischen den beiden Angriffswellen (Offensive und AGs) Unterstützung im Dorf zu plazieren. Also folgen die Angriffe im Optimalfall wenige Zehntelsekunden aufeinander. Da man 4 Angriffe für die AGs möglichst Zeitnahe aufeinander losschicken muss, wird die Sache spannend. Es gibt extra Tools im Internet zum üben des “Timens” dieser Angriffe. Doch in was in der Computer uns weit vorraus? Richtig, Timing!

Aus einem Tool, das lediglich Planngszwecke erfüllen sollte, ist so ein mehr oder weniger komplexer Bot geworden. Ein paar Bilder sagen wie immer mehr als Worte:

Weiterlesen

8 people like this post.

Like

Unlike

Eines meiner ersten Programme, damals noch mit C++.CLI, war ein Stämme Cracker. Als Grünschnabel habe ich mir damals Sourcecode zusammengesucht und so 10 Webbrowser-Controls gleichzeitig kontrolliert. Aus Nostalgiegründen, aber auch um zu zeigen dass sich in der Browsergame-Welt nicht vieles geändert hat, wurde nun ein neuer Cracker geschrieben. Um diesen wird sich der heutige Artikel drehen.

Fangen wir chronologisch an. Das Browsergame Die Stämme gibt es seid 2003 und hat seitdem massiven Zuwachs erfahren. Inzwischen wurde die 112te Welt gestartet mit mehreren Millionen aktiven Spielern auf allen Servern zusammen. In einem Thread auf Free-Hack ist damals ein Username-Grabber und Cracker erschienen, welcher mein Interesse geweckt hat. Stämme hatte damals, wohl mehr aus Debugzwecken, eine Liste von allen Usernamen auf der aktiven Welt in einer Liste gespeichert, welche per WebAccess zugänglich war. Dieser besagte User von Free-Hack stieß wohl auf diese Liste und schrieb prompt einen Cracker dafür, höchstwarscheinlich den ersten Stämme-Cracker überhaupt. Wie komme ich zu dieser Vermutung? Nunja, die Stämme Server waren auf solche massiven Zugangsanfragen nicht vorbereitet: Anstatt nach ein paar Versuchen die IP zu bannen, konnte man munter fröhlich so viele Username-Kombinationen ausprobieren wie man wollte. Und nachdem einige User von Free-Hack dieses Tool massiv nutzten, waren die Stämme Server komplett down-ge”DDosed”. Das Tool selbst war simple: Es grabbte die Username Liste und probierte dann pro Username ein paar Standartpasswörter wie “qwertz” und “passwort” durch. Die Erfolgsquote damals war erschreckend hoch. Bei 1000 Usernamen fand man locker 50 Accounts die man für seine Zwecke nutzen konnte. Mein damaliges Tool war natürlich weit unperformanter wie der Cracker von Free-Hack, aber das Erfolgserlebtnis dass man wirklich einen Account durch ein eigenes Tool gebrutet hatte wird mir immer in Erinnerung bleiben.

Ca. 7 Jahre später ist sowohl Stämme, als auch meine Programmierkentnisse weiter gereift. Aus Spass fing ich mit ein paar Leuten an wieder Stämme zu spielen. Und da kommen solche alten Gedanken wieder hoch “Wird es immernoch möglich sein, auf diesem Wege an Accounts zu kommen?”. Prompt wurde programmiert und prompt war auch schon das erste Problem vorhanden: Wie kam man an die Usernamen? Stämme bietet glücklicherweise eine Rangliste an, in der 25 Accounts pro Seite aufgelistet sind. Also wurde ein Login sowie ein Grabber geschrieben, um an die besagten Benutzernamen zu kommen. Da ich nur an Spielern interessiert war, welche besser wie ich sind, wurden die obersten 15000 Plazierungen ausgelesen.

Weiterlesen

13 people like this post.

Like

Unlike

Hallo zusammen! Der Ausdruck “Pwned” findet in meinem Vokabular eigentlich keine Verwendung, doch hier ist er wirklich angebracht. Heute geht es um eine (noch) relativ unbekannte App “Stadt Land Fluss Multiplayer“, welche mit ca. 25000 Downloads nicht so bekannt wie Quizduell ist. Das Prinzip des Spiels ist einfach: Man hat 60 Sekunden Zeit, in den verschiedesten Kategorien Begriffe mit dem gleichen Anfangsbuchstaben einzutragen. Wer also die meisten Wörter weis und dabei auch noch ohne Schreibfehler tippt, schlägt den Gegner.

Eine normale Modifikation könnte uns die Zeit zum Eintippen der Begriffe auf unendlich hochsetzen. Ein solcher Hack ist innerhalb von 3 Minuten geschrieben, denn die GameActivity bekommt als Parameter 60 ( = Sekunden) übergeben. Ein kleiner Smali-Patch schafft hier Abhilfe. Doch das ist kein Pwn, bei Begriffen die wir nicht wissen hilft uns auch keine längere Zeit zum überlegen. Ein anderer Ansatz muss her!

Diesen Ansatz finden wir in der API, die glücklicherweiße die Daten unverschlüsselt und per JSon überträgt. Zum Abrufen von Spieldaten senden wir folgende Request an den Server:

postData={"auth":{"password":"PASSWORDMD5Hashed","userId":"66XXX"},"clientInfo":{"appVersion":"1.0","bundleId":"de.lochmann.stadtlandfluss","os":"android"},"requests":{"getGameData":{"gameId":"1945415","userId":"X61XX","type":"getGameData"}}}

Die Antwort, welche zu Lang zum pasten ist, liefert uns diverse Strukturen mit Daten zum Spiel, dem Spieler, seiner Punktezahl und natürlich den bisher eingegeben Antworten. Ihr ahnt, worauf es hinausläuft? Daten aller Spiele grabben, eine riesige Datenbank aufbauen und pwnen! Das wäre ein Ansatz, doch bei bisher 1945415 gespielten Spielen wäre das komplette Grabben sinnlos. Zwar habe ich hier nun eine 2 GB Datenbank mit den ersten paar tausend Einträgen rumliegen, doch das filtern von richtigen Antworten macht auch nicht wirklich Spass. Man könnte daraus eine informative Statistik über Antworten und Punktezahlen erstellen, doch das nur als Randgedanke.

Weiterlesen

9 people like this post.

Like

Unlike

Manchmal hat man keine Lust auf Anti-Cheats, welche permanent (und aus manch unerfindlichem Grund) Kicks verteilen. Daher beginnen wir mit dem spassigen Teil: Die LithTech Engine und der Draw Hook.

Zunächst ein paar Worte zu der Engine: Die LithTech Engine ist das Herzstück von Spielen wie FEAR, ein paar Medal of Honor Titeln, Combat Arms und Crossfire. Inzwischen ist ein SDK veröffentlicht, das für uns sowohl ein Segen als auch ein Fluch ist. Denn so lässt sich zwar die Basis-Struktur von Klassen nachvollziehen, aber es gibt keine Garantie dass diese Klassen nicht geändert wurden. So kann man sich ein SDK als grobe Orientierung vorstellen, aber nicht als Basis der Programmierung.

Am Anfang war der DirectX Hook. Man hooked dazu (wie schon von Siedler bekannt) die Funktionen EndScene und Reset, um eigene Sachen zu zeichnen. Funktioniert hat das überraschend gut, aber nur bis das Device Resettet wurde. Ein Reset passiert z.B, wenn das Fenster in den Hintergrund geschoben wird und dann wieder Fokus erlangt. Oder auch, wenn man vom der Ingame-GUI ein Match Startet. Aus unerfindlichen Gründen wurde die Font, die ich zum Zeichnen erzeuge, nicht freigegeben. Eigentlich sollte das mit Aufrufen von OnLostDevice() und OnResetDevice() die Font Freigeben bzw wieder neu allokieren. Irgendwas lief schief, so dass ich diesen Ansatz nach ein paar Stunden des Debuggens wieder aufgab.


Lassen wir also die Engine das ganze Font verwalten und Strings zeichnen übernehmen. Dazu hooken wir uns in End2DOptimized, was dank diverser Strings in der Binary leicht möglich ist. Interessanter wird es, das Rendern vorzubereiten und wieder zu beenden. Dazu bedienen wir uns das Klasse ILTDrawPrim, welche ebenfalls über Strings schnell gefunden wird. Ein Blick in das SDK liefert auch schöne Klassenmember und virtuelle Funktionen, die wir uns zu nutze machen können.

Weiterlesen

6 people like this post.

Like

Unlike