Während es in der (Daten-)Wissenschaft grundsätzlich darum geht, eine Lösung für ein Problem zu finden, ertappe ich mich manchmal dabei, dass ich nach einem Problem suche, das zu einer bestimmten Lösung passt. Dieser Beitrag resultiert aus einer solchen Situation: Ich war auf der Suche nach einem interessanten Problem, auf das ich einen genetischen Algorithmus anwenden wollte. Ich hatte noch nie einen evolutionären Algorithmus verwendet und wollte mit einem solchen herumspielen. Als Vincent beschloss, Monopoly unter die Lupe zu nehmen, wurde mir klar, dass sich (Brett-)Spiele hervorragend dazu eignen, einige Algorithmen auszuprobieren. Hier sind wir also... genetische Algorithmen für Risiko!
Das Spiel Risiko
Wie Sie vielleicht wissen, ist Risiko ein strategisches Brettspiel für 2 bis 6 Spieler
, bei dem es
um die Eroberung (einer Tischversion) der Welt geht. Es wurde
Das Spiel dreht sich um den Spielplan, der unten abgebildet ist. Der Spielplan ähnelt einer Weltkarte, die in 42 Gebiete unterteilt ist, die sich auf sechs Kontinente verteilen und jeweils eine andere Farbe haben. Gebiete gelten als benachbart, wenn sich ihre Grenzen berühren oder wenn sie durch eine gepunktete Linie verbunden sind.
Zu Beginn des Spiels werden die Gebiete zufällig unter den Spielern verteilt . Jeder Spieler erhält eine bestimmte Anzahl von Armeen, die er auf seinen Gebieten aufstellen kann. Außerdem erhält jeder Spieler eine Mission, die er erfüllen muss, um das Spiel zu gewinnen. Die Missionen reichen von der Eroberung bestimmter Kontinente über die Eroberung einer bestimmten Anzahl von Gebieten bis hin zur Eliminierung eines anderen Spielers.
Dann spielen die Spieler nacheinander ihre Züge aus, bis ein Spieler seine Mission erreicht hat. Ein Zug besteht aus drei Phasen:
- Verstärkung, bei der der Spieler zusätzliche Armeen aufstellt. Die Anzahl der Armeen hängt von den Territorien ab, die er kontrolliert.
- Kämpfe, bei denen der Spieler versuchen kann, andere Gebiete zu erobern.
- Festung, während der der Spieler Armeen bewegen kann.
Die Chancen im Kampf werden mit Würfeln entschieden, wobei die verteidigende Partei die besseren Chancen hat, es sei denn, der Angreifer hat viel mehr Armeen.
Im Allgemeinen ist es eine gute Strategie, ganze Kontinente zu erobern, denn ein Spieler , der zu Beginn seines Zuges einen oder mehrere ganze Kontinente kontrolliert, erhält zusätzliche Verstärkung. Aber natürlich ist das Spiel nicht so einfach und man kann viele Strategien verfolgen.
Ein genetischer Risikospieler
Das Prinzip eines genetischen Algorithmus (GA) basiert auf der natürlichen Selektion und der Evolution: Aus einer Anzahl von Lösungen wählt man eine Anzahl der besten Lösungen aus und verändert (mutiert) und kombiniert diese, um eine neue Generation von Lösungen zu bilden.
Die Implementierung eines GA erfordert eine genetische Darstellung einer Lösung sowie eine Fitnessfunktion zur Bewertung der Qualität der Lösungen. Keine dieser beiden Anforderungen ist im Fall von Risk trivial.
Genetische Darstellung
Unsere Lösungen, die Risikospieler, müssen so gestaltet sein, dass wir die grundlegenden genetischen Operationen an ihnen durchführen können: Wir müssen in der Lage sein, die mutieren und kombinieren sie. Der einfachste Weg, dies zu ermöglichen, ist, eine Vektor-Darstellung des Spielers zu finden. Eine Mutation ist dann einfach eine Veränderung in einem oder mehreren Elementen (Genen) des Vektors (Genoms). Die Kombination kann erfolgen, indem ein Genom nimmt und einige der Gene durch die eines anderen Genoms ersetzt.
Eine einfache Python-Implementierung eines solchen Genoms könnte wie folgt aussehen:
class Genome(object):
def __init__(self, genes):
self.genes = genes
def combine(self, other):
return Genome([
mine if random.choice([True, False]) else theirs
for mine, theirs in zip(self.genes, other.genes)
])
def mutate(self):
return Genome([random.gauss() + val for val in self.genes])Der Spieler muss natürlich Entscheidungen auf der Grundlage des Genoms treffen.
Zum Beispiel muss er entscheiden, wo er seine Armeen in der
Verstärkungsphase platziert. Dies können wir
Für jede Armee, die ein Spieler in der Verstärkungsphase aufstellen kann, berechnen wir
einen Verstärkungsrang R_r für jedes Territorium, auf das er
die Armee stellen kann. Dieser Rang basiert auf verschiedenen Merkmalen der Territorien,
gewichtet mit den Genen des Spielers:
R_r = sum_i (f_i * w_i),wobei f_i ein Merkmal des Gebiets ist und w_i das Gewicht ist, das der Spieler
diesem Merkmal zuweist. Dann wird die Armee auf das Gebiet
mit dem höchsten Rang gestellt.
Merkmale eines Gebiets können zum Beispiel sein:
- Heeresvorsprung: das Verhältnis der feindlichen Armeen auf benachbarten Territorien zur Anzahl der Armeen auf dem betreffenden Territorium,
- Gebietsvorsprung: der Anteil der benachbarten Gebiete, die feindlich sind,
- Missionswert: ob das Gebiet für die Mission des Spielers wertvoll ist oder nicht. Dies hängt natürlich von der Mission ab.
Wir können ein Player-Objekt auf der Grundlage der obigen Implementierung von
der Klasse Genome implementieren:
class Player(Genome):
def place_reinforcement(self, board):
return max(board.my_territories(), key=lambda t: self.reinforcement_rank(t))
def reinforcement_rank(self, territory):
return army_vantage(territory) * self.genes[0] +
territory_vantage(territory) * self.genes[1] +
mission_value(territory) * self.genes[2]In ähnlicher Weise können wir einen Angriffsrang und einen Festungsrang konstruieren. Viele der Merkmale werden von den Rängen gemeinsam genutzt: Wenn zum Beispiel die Mission wichtig ist, um zu bestimmen, wo Armeen platziert werden sollen, ist sie wahrscheinlich auch wichtig für die Entscheidung, welches Gebiet angegriffen werden soll. Die Gewichte sollten jedoch nicht geteilt werden, da die Motivationen für die Aktionen in jeder Phase unterschiedlich sind: Beim Angriff versucht man, neue Gebiete zu erobern oder einen Spieler zu vernichten, während man bei der Befestigung vielleicht sein wertvollstes Gebiet befestigen möchte.
In der Angriffsphase müssen wir nicht nur entscheiden, welches Gebiet wir angreifen, sondern auch, ob wir überhaupt angreifen. Dazu können wir die Angriffsränge für alle Angriffsoptionen berechnen und nur angreifen, wenn der höchste Angriffsrang über einer bestimmten Schwelle liegt. Die ideale Höhe dieser "Angriffsschwelle" kann ebenfalls vom GA bestimmt werden, indem er sie zu einem der Gene macht.
Schließlich müssen wir noch über den Bereich der Gewichte nachdenken: Wenn wir alle
Gewichte w_i unbeschränkt lassen, besteht die Gefahr, dass sie
ins Unendliche laufen. Es ist nicht so sehr der Wert der einzelnen Gewichte, sondern das Verhältnis
zwischen ihnen, das die endgültige Entscheidung beeinflusst. Daher müssen wir
eine absolute Skala festlegen. Das können wir tun, indem wir eines der Gewichte
auf die Werte -1 und 1 beschränken. Solange dieses Gewicht nicht zu
konvergiert, wird eine Skala für die anderen Gewichte festgelegt.
Fitness-Funktion
Jetzt, wo wir eine genetische Repräsentation eines Spielers haben, müssen wir in der Lage sein , diese zu bewerten. Natürlich kann die 'Qualität' eines einzelnen Spielers nicht bewertet werden; und ist wahrscheinlich sogar unmöglich zu definieren. Andererseits ist es nicht so schwierig, herauszufinden, ob ein Spieler besser ist als ein anderer: Wir könnten sie einfach ein Spiel spielen lassen und sehen, wer als Sieger hervorgeht. Da Risiko nicht wirklich für zwei Spieler geeignet ist, können wir mehrere (zum Beispiel vier) Spieler in einem Spiel gegeneinander antreten lassen, was den Vorteil hat, dass wir mehrere Spieler in einem einzigen Spiel bewerten können. Natürlich gibt es einen Zufallsfaktor, aber wir können die Spieler mehrere Partien spielen lassen, um richtig zu bewerten, wer der bessere Spieler ist (sind).
Das funktioniert gut, wenn wir nur ein paar (bis zu sechs) Spieler haben. Wenn wir mehr Spieler bewerten wollen, läuft es schnell aus dem Ruder, wenn jeder Spieler gegen jeden anderen Spieler antritt. Bei hundert Spielern würde das viele hundert Millionen Spiele erfordern.
Glücklicherweise wurde das Problem der Rangfolge von Spielern in einem Spiel bereits gelöst . Microsoft entwickelte ein Ranglistensystem namens TrueSkill, um Spieler auf Xbox Live zu bewerten. Während die genaue Implementierung, die Microsoft verwendet, nicht veröffentlicht wurde, ist eine Python-Implementierung, die das Verhalten nachahmt, öffentlich verfügbar. Eine interaktive Erklärung der Funktionsweise von TrueSkill finden Sie unter hier.
Mit TrueSkill können wir also die Spieler mehrere Spiele in
zufällig ausgewählten Gruppen spielen lassen, bis wir mit den sigmas von
der TrueSkill Überzeugungen zufrieden sind und dann die Spieler auf der Grundlage ihrer mus auswählen.
Ergebnisse
Funktioniert dieser Ansatz also tatsächlich? Ja, er funktioniert! Sehen Sie unten die
Verteilungen der Gewichte (w) für das oben beschriebene Gebietsaussichtsmerkmal
. Ursprünglich war es gleichmäßig über den Bereich verteilt
[-25, 25], aber schon nach einer einzigen Iteration des GA sehen wir
es die positive Seite bevorzugt, was bedeutet, dass es besser ist, Armeen
auf Territorien zu platzieren, die viele feindliche Nachbarn haben. Nach zehn
Iterationen gibt es kaum noch Spieler, die ein negatives Gewicht
für das Merkmal Gebietsvorteil haben, und nach vierzig Iterationen sehen wir
es bei einem Gewicht von knapp unter zwanzig seinen Höhepunkt erreichen.
Ich könnte Ihnen jetzt alle anderen Funktionen vorstellen, aber ich glaube, das würde ziemlich schnell langweilig werden. Wenn Sie mit dem genetischen Player oder Risiko im Allgemeinen herumspielen möchten, finden Sie die von mir verwendete Implementierung hier. Wenn Sie weitere Informationen wünschen, bevor Sie einen Blick auf den Code werfen, finden Sie unter den Vortrag , den ich bei Europython gehalten habe.
Allerdings läuft es nicht immer so reibungslos, wie die obige Zahl
Sie glauben machen möchte. Zum Beispiel gibt es in der anfänglichen (zufälligen) Population
Natürlich ist der "beste" Spieler, der aus dem Algorithmus hervorging, keineswegs der beste Spieler, der existieren könnte. Zunächst einmal war der Algorithmus nach 40 Iterationen (etwa 12 Stunden) noch nicht wirklich konvergiert, so dass , wenn er etwas länger läuft, (viel) bessere Ergebnisse liefern könnte. Außerdem gibt es höchstwahrscheinlich einige Merkmale, die viel besser sind als die , die ich konstruiert habe. Und letztendlich ist dieser Algorithmus in jedem Fall begrenzt, da er nur lineare Kombinationen einiger konstruierter Eigenschaften vornimmt und er keinen internen Zustand hat, um das Verhalten anderer Spieler zu verfolgen.
Nichtsdestotrotz macht es Spaß, mit genetischen Algorithmen zu experimentieren!
Mike Izbicki setzte die Risikoanalyse in seinen Vorlesungen am Claremont McKenna College ein. "GoDataDriven hat mir geholfen, innovative Datenanalysekurse für zu entwickeln, die von den Studenten am Claremont McKenna College besucht werden", teilte uns Izbicki mit,
Verfasst von
Rogier van der Geer
Unsere Ideen
Weitere Blogs
Contact