risk game ai agent
1.0.0
Risiko ist ein Strategie -Brettspiel der Diplomatie, Konflikte und Eroberung für zwei bis sechs Spieler. Drehung dreht sich zwischen Spielern, die Armeen von Spielstücken kontrollieren, mit denen sie versuchen, Gebiete von anderen Spielern zu erfassen, wobei die Ergebnisse durch Würfelrollen bestimmt werden. Das Ziel des Spiels ist es, jedes Territorium auf dem Brett zu besetzen und dabei die anderen Spieler zu beseitigen. Jede Runde besteht aus zwei Aktionen:
Der Zweck dieses Projekts war es, das Risikospiel mit einigen Änderungen in den Regeln zu implementieren und einen künstlich intelligenten Agenten zu entwerfen, der das Spiel richtig spielen kann und eine sehr hohe Chance hat, sich anderen Gegnern zu stellen, einschließlich beiden tatsächlichen Menschen Spieler oder andere Agent -Spieler.
Das Spiel wird mit Java -Programmiersprache implementiert. Kontrollieren von Kurven, Spieleranforschungsaktionen, Aktualisierung der Spielkarte, Überprüfung, ob alles nach den Regeln usw. passiert, sind die Dinge, die dieser Teil des Codes tut. Die Game UI ist auch über .fxml -Dateien entworfen, die die Karte zeichnen und die Plattform mit dem Spieler mit der Logik des Spiels verbinden.
Dieser Abschnitt konzentriert sich auf die Implementierung und Bewertung von Heuristiken, die zu einer starken KI für das Spielrisiko führen.
Die Implementierung basiert auf dem Minimax Alpha-Beta-Schnittalgorithmus. Der Spieler erstellt einen Vorhersagebaum basierend auf dem DFS -Algorithmus.
Immer wenn es in der Reihe des Agenten zum Spielen ist, wird ein Baum gemacht. Die Baumknoten sind die Staaten des Spiels (Karte des Spiels in diesem Zustand), und jede Kante ist ein möglicher Angriff aus dem aktuellen Zustand, um den Ergebnis der Karte des Angriffs zu erstellen. Eine Angriffsaktion besteht aus den Koordinaten von Start und Target Territories und der Anzahl der Einheiten, die sich für die angreifende Armee ausgewählt haben. Der Stammknoten ist der aktuelle Status der Karte, von dem ein Spieler auswählen muss, aus dem sich bewegt. Der Baum kann zwar erst im Endzustand des Spiels vorhersagen, da ein Spieler in jedem Zustand, in dem sich die Speicher- und Zeitbeschränkungen nicht ermöglichen, eine große Anzahl möglicher Bewegungen haben kann. Daher kann der Spieler den Baum nur bis zu einer bestimmten Tiefe konstruieren, die wir im Code definiert haben. Es gibt auch einige Vereinfachungen, die auf bestimmte Teile der Gaming -Strategie des Agenten angewendet werden, die alle in den folgenden Abschnitten erläutert werden. Um die bestmögliche Entscheidung zu treffen, werden Heuristiken für die tiefstmöglichen Knoten (Baumblätter) definiert, die bewerten, wie viel Erreichen dieses Zustands für den Spieler von Vorteil sein kann. Die Heuristiken werden im Bericht weiter erläutert. Wenn die Werte der Blätter bestimmt werden, wird der Baum an das Minimax Alpha-Beta-Beschneidung weitergegeben, und dieser bekannte Algorithmus wird die beste Reihe von Aktionen finden, die der Spieler haben kann.
Die Versorgung von Einheiten an Gebiete kann eine schwierige Aufgabe sein. In dem Sinne, dass wir unsere Angriffskraft verbessern wollen, aber auch sicherstellen möchten, dass sie ausreichende Verteidigungsmacht in Territorien haben, die in Gefahr sind, angegriffen zu werden. Ein Einsatz von Einheiten in Ländern, die an feindliche Gebiete nebeneinander liegen, könnte eine kluge Möglichkeit sein, das Gleichgewicht zwischen diesen beiden Zielen zu halten.
Einfachheit der Entwurfs:
Die Vorhersage und Einbeziehung aller möglichen Entwurfsszenarien im Vorhersagebaum führt zu einem komplexen Baum, der den zuvor genannten Problemen konfrontiert ist. Eine der vereinfachten Vereinfachungen ist daher, dass wir eine entworfene Heuristik verwenden, die sich als immer das bestmögliche Ergebnis erwiesen und voraussetzt, dass die Gegner diesen Ansatz auch bei der Ausarbeitung verfolgen. Mit anderen Worten, wir entfernen die Entwurfsergebnisse, wenn Möglichkeiten den Vorhersagebaum bilden und sie in definitive Entwurfsszenarien ändern.
Um dies zu tun, machen wir die folgenden Schritte:
Entwurf der Heuristik:
Schritt 1:
Die Zusammenfassung aller Einheiten in feindlichen Ländern y neben Land X wird eine Maßnahme geben, die wir als Grenzsicherheitsbedrohung (BST) in x bezeichnen.
Schritt 2:
Das Teilen dieses BST durch die in x gelegenen Einheiten ergibt ein Grenzsicherheitsverhältnis (BSR), das zwischen allen Grenzländern verglichen werden kann.
Länder mit einem hohen BSR werden von einem feindlichen Spieler eher erobert, da die Zahl der feindlichen Einheiten in angrenzenden feindlichen Ländern relativ höher ist als die Anzahl der Einheiten im Land selbst. Die Auswahl von Ländern mit einem hohen BSR, um ihre Verteidigungsfestigkeit zu erhöhen, indem die BSR gesenkt wird. Die Versorgung von Einheiten in Ländern mit einer niedrigeren BSR, was bedeutet, dass sie bereits eine bessere defensive Haltung haben, wird ihre offensive Stärke erhöhen und die Chancen eines erfolgreichen Angriffs dieser Länder erhöhen.
Schritt 3:
Die Normalisierung der BSR durch Teilen durch die Summe aller BSRs von Ländern, ein Spieler, wird eine direkte Messung angeben, an der jemand Einheiten arrangieren könnte. Das normalisierte Grenzsicherheitsverhältnis (NBSR) wird berechnet durch:
Es gibt ein direktes Verhältnis darüber, wie die Einheiten in Ländern verteilt werden können. Zu diesem Zeitpunkt können wir sehen, dass es ein Problem mit diesen Verhältnissen gibt, da einige Daten irrelevant sind und wir nicht allen unseren Territorien Einheiten hinzufügen möchten, sodass wir einen Schwellenwert zwischen den Schritten zwei und drei festlegen, indem wir die BSRX -Daten in den Sortieren der BSRX -Daten in den Eine absteigende Reihenfolge (wir konzentrieren uns mehr darauf, die Verteidigungskraft stärker zu machen), die Daten aus der Mitte zu teilen und die Zahlen in die untere Hälfte auf Null zu setzen.
Schritt 4:
Schritt 4 wird fortgesetzt, bis keine verfügbaren Einheiten mehr verfügbar sind.
In der Angriffsphase werden einige Vereinfachungen angewendet, um den Baum weniger kompliziert zu machen, damit wir in tiefere Ebenen davon vorhersagen können. Dies kann durch Überprüfen der Angriffsszenarien erfolgen, die eine höhere Chance haben, den Kampf zu gewinnen, und sie nur in den Baum aufzunehmen.
Um zu bewerten, wie vorteilhaft ein Baumblatt für diesen bestimmten Spieler ist; Wir haben vier heuristische Merkmale definiert, die ihre bestmöglichen Gewichte beim Erlernen der Heuristik finden, die später erklärt werden. Alle Merkmale geben ein Ergebnis zwischen Null und eins zurück, da die Merkmale in enger Verhältnis zueinander bewertet werden, das Lernen und die Zuweisung von Gewicht wäre genauer.
Die Funktionen sind:
Wenn Sie jeder der Heuristiken im vorherigen Teil Gewicht geben, bewerten Sie, wie wichtig und einflussreich jeder von ihnen ist, dass ein Agent das Spiel gewinnt. Der Prozess des Findens dieser Gewichte ist durch Genetik und Lernen. Jedes Gen ist ein Satz von vier Gewichten für diese vier Merkmale. Wir beginnen damit, 100 zufällige Gewichte im Bereich zu erzeugen [0,10]. Danach werden 10 Turniere stattfinden. Für jedes Turnier werden 10 Gene aus der Primärpopulation zufällig ausgewählt. Alle möglichen Genepaare spielen gegeneinander und das Ergebnis jedes Spiels in jedem Turnier wird dokumentiert. Die Fitnessfunktion ist definiert als (Anzahl der Siege / Anzahl der Spiele) für jedes Gen. Die drei Top -Gene in jedem Turnier (basierend auf der Fitnessfunktion) werden ausgewählt, sodass wir jetzt über 30 ausgewählte Top -Gene verfügen. Unter diesen wählen wir 12 zufällige Paare aus und führen für jedes Paar ein Crossover durch, das ein neues Gen erzeugt, indem das durchschnittliche Gewicht des Genespaars berechnet wird. Daher haben wir jetzt 12 neue Gene aus diesem Crossover. Andererseits werden 3 Gene innerhalb der 30 Gene, die wir hatten, zufällig ausgewählt und sie durch Ändern eines zufälligen Gewichts eines jeden zu einem anderen zufälligen Gewicht im Bereich [0,10]. Nach all dem haben wir jetzt 15 brandneue Gene, die in die Primärpopulation gesetzt werden, und ersetzen die 15 am wenigsten guten, die wir bereits dort hatten. Zu diesem Zeitpunkt wird die zweite Generation von Genen erzeugt. Dieser Vorgang wiederholt sich weiter, bis die Generation 4 der Gene erzeugt wird. Das Top -Gen in dieser Population wird als beste Gewichte für die Merkmale unserer Heuristik ausgewählt, mit der der Agent spielen wird.
