Welche allgemeinen Tipps haben Sie, um einen Bot für die Teilnahme an einer King of the Hill-Herausforderung zu erstellen? Mit welchen Strategien gehen Sie von der Überlegung der Herausforderung bis zur Erstellung Ihres Bots? Welche Datenstrukturen finden Sie am nützlichsten?

Bitte posten Sie einen Tipp pro Antwort.

Finding Nash - Gleichgewichte

Dies ist ein sehr wichtiges Konzept, wenn es sich bei der KOTH um eine relativ einfache Reihe von Entscheidungen handelt, an der nur wenige Akteure beteiligt sind (normalerweise 2) und das deterministisch ist. Ein Nash-Gleichgewicht beschreibt eine "Stau" -Position: Wenn sich die beiden Spieler für ihre beiden Strategien entschieden haben, sind die beiden Spieler effektiv an diesen Positionen gesperrt: Jeder Spieler, der seine Strategie ändert, schafft einfach zusätzliche Schwachstellen.

Beispiele für Spiele, bei denen Nash-Gleichgewichte wichtig sind, sind:

• Stein-Papier-Schere (-Eidechsen-Spock), bei der eine "unschlagbare" Strategie ein Zufallsspiel ist
• Morra , die ein "Spektrum" von Gleichgewichten hat. Peter Taylor hat in seiner Antwort hier ein gutes Beispiel geschrieben .
• Prisoner's Dilemma, ein kooperatives Spiel, bei dem jeder den Stillstand verliert

So finden Sie ein Gleichgewicht

Tatsächlich ist das Finden eines Gleichgewichts für die meisten einfachen Spiele ziemlich einfach und oftmals ziemlich intuitiv. Eine Menge Details zu den verschiedenen Methoden finden Sie im Internet. Das Grundkonzept, das normalerweise anwendbar ist, besteht darin, eine Liste möglicher Strategien zu erstellen, die die beiden Spieler verwenden können (die vom Spiel bereitgestellten Optionen). Wenn eine Strategie von einer anderen "dominiert" wird, kann diese Strategie aus der Liste entfernt und der Vorgang wiederholt werden. Mit "Beherrschung" meine ich, dass Strategie B von der Liste gestrichen werden kann, wenn Strategie A immer ein gleiches oder besseres Ergebnis liefert als Strategie B, und zwar gegen alle verbleibenden Strategien des Gegners.

Beispiel: Stein-Papier-Schere

RPS hat so etwas wie ein "gemischtes" Gleichgewicht, was bedeutet, dass es sich um eine Verteilung handelt. Anstatt den gleichen Zug wiederholt zu spielen (was zu einer schnellen Niederlage führt), besteht das Gleichgewicht darin, 1/3 Rock, 1/3 Paper und 1/3 Scissors in zufälliger Verteilung zu spielen. Wenn ich zufällig spiele, kann mein Gegner nichts tun, um mir einen Vorteil zu verschaffen. Wenn mein Gegner nicht nach dem Zufallsprinzip spielt, führt dies nur zu einer Sicherheitslücke für ihn.

Spiele mit gemischtem Gleichgewicht sind bei PPCG wahrscheinlich am verbreitetsten, da sie viele Formen annehmen können (das einzige interessante Spiel, an das ich bei einem reinen Gleichgewicht denken kann, ist das Gefangenendilemma). Ich sollte beachten, dass das gemischte Gleichgewicht nicht einheitlich zufällig sein muss , sondern einfach etwas anderes, als jedes Mal den gleichen Zug zu spielen.

Verwendung dieser Informationen

Das Nash-Gleichgewicht eines Spiels stellt häufig die "Grundlinie" dar, von der aus Sie versuchen sollten, zu operieren. Wenn Sie in RPS nach dem Zufallsprinzip spielen, ist ein Endpunkt in der Mitte des Pakets garantiert. Um an die Spitze zu gelangen, müssen Sie die Schwächen eines anderen Spielers identifizieren.

Um dies zu tun, sollten Sie sich an das Gleichgewicht halten, wenn Sie die Schwächen des Gegners nicht kennen. Sobald diese Schwächen erkannt wurden (Sie haben festgestellt, dass Ihr Gegner nicht im Gleichgewicht ist), müssen Sie das Gleichgewicht leicht verlassen, um den Vorteil Ihres Gegners zu nutzen. Diese Aktion erzeugt wiederum Schwächen auf Ihrer eigenen Seite. Sie müssen dann feststellen, wann Ihr Gegner seine Strategie ändert, damit Sie den Angriff stoppen und das zufällige Spiel fortsetzen können.

Erkennen von Abweichungen vom Gleichgewicht

Das ist ziemlich schwierig und ich bin kein Experte. Variationen können in vielen Formen auftreten:

• Bevorzugen Sie einige Optionen ohne Grund gegenüber anderen, z. B. einen RPS-Spieler, der doppelt so oft Rock spielt wie eine Schere, oder einen, der kein Papier spielt. Einige relativ einfache Statistiken können dies erkennen.
• Ausgehend von einer aktuellen Bewegung in der Vergangenheit in einem vorhersehbaren Muster. Dazu gehören Nachahmer-Bots, die Bots schlagen, die Ihre letzten Züge übertreffen, oder Bots, die mit dem Fahrrad fahren. Dies erfordert zusätzliche Logik zum Erkennen, da die gesamte Bewegungsverteilung gleichmäßig verteilt werden kann, obwohl die Bewegungen nicht zufällig sind. Sie sollten versuchen, die Aufzeichnungen von Zügen zu machen und Korrelationen zu finden wie "den Zug, den ich vor 2 Zügen gemacht habe, und den Zug, den mein Gegner jetzt gemacht hat" und "den Zug, den er vor 1 Ziehung gemacht hat, und den Zug, den er jetzt gemacht hat" usw.
• Bots, deren Zugverteilung von Ihrer abhängt. Die Sicherheitslücke in diesen Bots oft nicht erstellt (in einer messbaren Größe) bis nach Sie sich von einer zufälligen Verteilung variiert haben. Im Allgemeinen fällt Ihr eigener Bot in diese Kategorie.

Seien Sie genau über die Anforderungen, um Ihren Bot auszuführen

Bots können in einer Vielzahl von Sprachen (und Versionen dieser Sprachen) geschrieben werden. Dies hilft jedem, wenn Sie:

1. Testen Sie es in der vom OP angegebenen Umgebung (oder so nah wie möglich).
2. Testen Sie es nach Möglichkeit in einer Vielzahl anderer Umgebungen (um anderen Benutzern zu helfen, die es ausführen möchten).
3. Seien Sie genau über die Sprache und Version, die Sie verwenden, und erklären Sie, wie Sie Ihren Bot ausführen.

Als Bonus: Wenn Sie eine weniger bekannte Sprache verwenden, erstellen Sie einen Link, über den Benutzer die Binärdatei / Quelle herunterladen können, um sie auszuführen.

Arbeiten Sie im Team mit Ihrem Team zusammen

Während Sie normalerweise einen Bot schreiben können, der alleine arbeitet, um Aufgaben zu erledigen, um Ihrem Team zu helfen, gibt es einen viel größeren Vorteil, wenn Sie sowohl innerhalb als auch außerhalb des Spiels koordinieren. Ein Paradebeispiel dafür sind die Red vs. Blue - Pixel Team Battlebots .

Während der Entwicklung konnten die Teams chatten und darüber diskutieren, wie sie ihre Bots koordinieren können, um besser als alleine zu funktionieren. Obwohl SphiNotPi3000 technisch gesehen derselbe Bot ist, wurde er so geschrieben, dass er mit einem anderen von sich selbst zusammenarbeitet und sich auf eine Weise bewegt, die die Schwächen erklärt, mit denen er konfrontiert wäre, wenn er alleine wäre. Das Endergebnis war, dass sie das Schlachtfeld fast vollständig beherrschen konnten, selbst wenn es nur die beiden gegen das gesamte andere Team waren .

Planen Sie also außerhalb des Spiels und koordinieren Sie mit Ihren Teamkollegen, welche Strategien abgedeckt werden sollen. Vielleicht hat jemand einen Bot, der die Karte diagonal scannt? Lassen Sie Ihren horizontal scannen (nur ein Beispiel). Wenn die Herausforderung eine Teamkommunikation zulässt, nutzen Sie sie im Spiel. Im Battlebots-Spiel können Sie beispielsweise Ihren Teammitgliedern eine Nachricht über die Position von Bots außerhalb ihres Sichtfelds senden und sie dann ermutigen, ihre Bots auf kompatible Weise zu schreiben, um diese Signale zu nutzen.

Verwenden Sie eine Metastrategie

Für fast jede clevere Strategie gibt es eine andere Strategie, die sie übertrifft: Zum Beispiel könnte Ihr Gegner genau die gleichen Überlegungen wie Sie verwenden, um Ihren nächsten Schritt zu antizipieren und ihm dann entgegenzuwirken. Jetzt versuchen Sie vielleicht, Ihren Gegner noch einmal zu erraten, aber es ist schwer zu wissen, wann Sie aufhören müssen .

Ein weiteres Problem ist, dass eine Strategie, die gut darin ist, einen klugen Gegner zu erraten, im Vergleich zu einfacheren Gegnern alles andere als optimal ist.

Wie können Sie das lösen? Sie überlassen Ihrem Bot die Entscheidung, welche Strategie Sie anwenden möchten!

Zu diesem Zweck geben Sie Ihrem Bot zunächst ein Repertoire an verschiedenen Strategien. Dann schaut Ihr Bot vor jedem Zug auf die aufgezeichnete Geschichte des Spiels und bewertet, wie sich diese verschiedenen Strategien entwickelt hätten. Es ist dann das Bild, das am erfolgreichsten gewesen wäre.

Das Einbeziehen von Strategien, die in erster Linie stark sind, hilft Ihrem Bot, gute Optionen zur Auswahl zu geben. Aber Sie sollten auch wirklich einfache einbeziehen, da diese oft besser gegen dumme Gegner funktionieren.

Sie könnten erwägen, einige Strategien zu verzerren, um eine Überanpassung zu vermeiden (z. B. zu versuchen, ein Muster zu schlagen, bei dem der Gegner nur zufällig handelt) oder bestimmte Strategien am Anfang zu bevorzugen, wenn noch nicht viele Informationen vorliegen.

Natürlich funktioniert dieser Ansatz nur für bestimmte Arten von King-of-the-Hill-Herausforderungen. Das hat mir in einem Stein-Papier-Scheren-Eidechsen-Spock-Match sehr gut getan . In anderen Spielen kann es fast unmöglich sein, zu bewerten, wie sich eine bestimmte Strategie entwickelt hätte, wenn sie nicht tatsächlich gespielt worden wäre.

Eine extreme Form dieses Meta-Ansatzes (der an Betrug grenzt) wäre, das bekannte Verhalten aller anderen Bots in Ihren eigenen Bot einzubeziehen, sodass er deren Bewegungen perfekt vorhersehen kann.