Wie erstelle ich eine gute Bewertungsfunktion für ein Spiel?

https://stackoverflow.com/questions/1291377

18-09-2019
|

Frage

Ich schreibe manchmal Programme, um Brettspielvarianten zu spielen. Die grundlegende Strategie ist das Standard-Alpha-Beta-Schnitt oder ähnliche Suchvorgänge, die manchmal durch die üblichen Ansätze für Endspiele oder Öffnungen verstärkt werden. Ich habe meistens mit Schachvarianten herumgespielt. Wenn es also an der Zeit ist, meine Bewertungsfunktion auszuwählen, verwende ich eine grundlegende Schachbewertungsfunktion.

Jetzt schreibe ich jedoch ein Programm, um ein völlig neues Brettspiel zu spielen. Wie wähle ich eine gute oder sogar anständige Bewertungsfunktion?

Die Hauptherausforderungen besteht darin, dass die gleichen Teile immer auf der Tafel sind Nun noch, um Einblicke zu geben. (Ps. Ich habe einen Mogo -Ansatz betrachtet, aber zufällige Spiele werden wahrscheinlich nicht enden.)

Spieldetails: Das Spiel wird auf einem 10-mal-10-Brett mit festen sechs Teilen pro Seite gespielt. Die Stücke haben bestimmte Bewegungsregeln und interagieren auf bestimmte Weise, aber kein Stück wird jemals erfasst. Das Ziel des Spiels ist es, in bestimmten speziellen Quadraten auf dem Brett genug von Ihren Stücken zu haben. Ziel des Computerprogramms ist es, einem Spieler zu bieten, der mit oder besser als aktuelle menschliche Spieler wettbewerbsfähig ist.

Lösung

Finden Sie einige Kandidaten für Ihre Bewertungsfunktion, wie die Mobilität (Anzahl der möglichen Bewegungen) abzüglich der Mobilität des Gegners und versuchen Sie dann, das optimale Gewicht für jede Metrik zu finden. Genetische Algorithmen scheinen ziemlich gut zu funktionieren, um Gewichte in einer Bewertungsfunktion zu optimieren.

Erstellen Sie eine Bevölkerung mit zufälligen Gewichten, bekämpfen Sie sie mit begrenzter Tiefe gegeneinander, ersetzen Sie die Verlierer durch zufällige Kombinationen aus den Gewinnern, mischen und wiederholen Sie, wodurch die Bevölkerung nach jeder Generation ausgedruckt wird. Lassen Sie es laufen, bis Sie mit dem Ergebnis zufrieden sind oder bis Sie sehen müssen, dass der Bereich für einige der Metriken anpassen muss, und versuchen Sie es erneut, wenn der optimale Wert für eine Metrik außerhalb Ihres Anfangsbereichs liegt.

Späte Bearbeitung: Ein akzeptierterer, studierter, verstandener Ansatz, von dem ich zu dieser Zeit nicht wusste, dass es "Differential Evolution" ist. Nachkommen werden von 3 Eltern anstelle von 2 erstellt, so dass das Problem der vorzeitigen Konvergenz gegenüber dem Durchschnitt vermieden wird.

Andere Tipps

Ich werde mit ein paar Grundlagen beginnen und später zu härteren Sachen wechseln.

Basic Agent und ein Testframework

Egal welchen Ansatz Sie ergreifen, Sie müssen mit etwas wirklich Einfachem und Dummem beginnen. Der beste Ansatz für einen dummen Agenten ist zufällig (generieren Sie alle möglichen Bewegungen, wählen Sie zufällig eine). Dies dient als Ausgangspunkt, um alle anderen Agenten zu vergleichen. Sie benötigen einen starken Rahmen für den Vergleich. Etwas, das verschiedene Agenten nimmt, es ermöglicht, eine Reihe von Spielen zwischen ihnen zu spielen und die Matrix der Leistung zurückzugeben. Basierend auf den Ergebnissen berechnen Sie die Fitness für jeden Agenten. Zum Beispiel Ihre Funktion tournament(agent1, agent2, agent3, 500) Spielt 500 Spiele zwischen jedem Agentpaar (das erste/zweite) und gibt Ihnen so etwas zurück wie:

  x         -0.01       -1.484   |  -1.485
0.01          x         -1.29    |  -1.483
1.484       1.29          x      |  2.774

Hier verwende ich zum Beispiel 2 Punkte für einen Sieg für einen Sieg, 1 Punkt für die Bewertungsfunktion der Ziehung und am Ende einfach alles, um die Fitness zu finden. Dieser Tisch sagt mir das sofort aus agent3 ist das Beste und agent1 ist nicht wirklich anders als agent2.

Sobald diese beiden wichtigen Dinge eingerichtet sind, sind Sie bereit, mit Ihren Bewertungsfunktionen zu experimentieren.

Beginnen wir mit der Auswahl von Funktionen

Zunächst müssen Sie erstellen not a terrible Bewertungsfunktion. Damit meine ich, dass diese Funktion 3 wichtige Aspekte korrekt identifizieren sollte (Win/Draw/Loss). Das klingt offensichtlich, aber ich habe eine erhebliche Menge an Bots gesehen, bei denen die Macher diese drei Aspekte nicht richtig einrichten konnten.
Dann nutzen Sie Ihren menschlichen Einfallsreichtum, um einige Funktionen des Spielstatus zu finden. Das erste, was Sie tun müssen, ist, mit einem Spielexperten zu sprechen und ihn zu fragen, wie er auf die Position zugänglich ist.
Wenn Sie den Experten nicht haben oder vor 5 Minuten nur die Regeln Ihres Spiels erstellt haben, unterschätzen Sie nicht die Fähigkeit des Menschen, nach Patters zu suchen. Selbst nach ein paar Spielen kann eine kluge Person Ihnen Ideen geben, wie er hätte spielen sollen (es bedeutet nicht, dass er die Ideen implementieren kann). Verwenden Sie diese Ideen als Funktionen.
An diesem Punkt müssen Sie nicht wirklich wissen, wie sich diese Funktionen auf das Spiel auswirken. Beispiel für Merkmale: Wert der Teile, Mobilität der Stücke, Kontrolle wichtiger Positionen, Sicherheit, Gesamtzahl möglicher Bewegungen, Nähe zu einem Finish.
Nachdem Sie diese Funktionen codiert und separat verwendet haben, um zu sehen, was am besten funktioniert (beeilen Sie sich nicht, um Funktionen zu entsorgen, die nicht für sich selbst angemessen funktionieren, sie könnten in Verbindung mit anderen hilfreich sein), können Sie mit Kombinationen experimentieren.

Bessere Bewertungen durch Kombination und Gewichtung einfacher Merkmale aufbauen. Es gibt ein paar Standardansätze.

Erstellen Sie eine Uber -Funktion basierend auf verschiedenen Kombinationen Ihrer Funktionen. Es kann linear sein eval = f_1 * a_1 + ... f_n * a_n (f_i Merkmale, a_i Koeffizienten), aber es kann alles sein. Dann instanziieren Sie viele Mittel mit absolut zufälligen Gewichten für diese Bewertungsfunktion und verwenden Sie den genetischen Algorithmus, um sie erneut zu spielen. Vergleichen Sie die Ergebnisse mit dem Test -Framework, verwerfen Sie ein paar klare Verlierer und mutieren Sie ein paar Gewinner. Setzen Sie den gleichen Prozess fort. (Dies ist eine grobe Übersicht, lesen Sie mehr über GA)
Verwenden Sie die Idee der Back-Propagation von einem neuronalen Netzwerk, um den Fehler vom Ende des Spiels zu erweitern, um die Gewichte Ihres Netzwerks zu aktualisieren. Sie können mehr lesen, wie es gemacht wurde mit Backgammon (Ich habe nichts Ähnliches geschrieben, also entschuldige mich für die Kürze.)

Sie können ohne Bewertungsfunktion arbeiten! Dies mag für eine Person, die nur von Minimax/Alpha-Beta gehört hat, verrückt klingen, aber es gibt Methoden, die überhaupt keine Bewertung erfordern. Einer von ihnen heißt Monte Carlo Tree Search Und wie ein Monte -Carlo in einem Namen darauf hindeutet, dass es viel zufällig verwendet (es sollte nicht zufällig sein, können Sie Ihre vorherigen guten Agenten verwenden), um einen Baum zu generieren. Dies ist ein großes Thema für sich, also werde ich Ihnen meine sehr hochrangige Erklärung geben. Sie beginnen mit einer Wurzel, erstellen Ihre Grenze, die Sie erweitern möchten. Sobald Sie etwas erweitert haben, gehen Sie zufällig ins Blatt. Wenn Sie das Ergebnis aus dem Blatt erhalten, starten Sie das Ergebnis. Tun Sie dies viele Male und sammeln Sie die Statistiken über jedes Kind der aktuellen Grenze. Wählen Sie die beste aus. Es gibt dort eine bedeutende Theorie, die sich darauf bezieht, wie Sie zwischen Erkundung und Ausbeutung und einer guten Sache dort ausbalancieren.

Ich würde mir einen überwachten Algorithmus für maschinelles Lernen wie Verstärkungslernen ansehen. Kasse Verstärkungslernen in Brettspielen. Ich denke, das gibt Ihnen einige gute Anweisungen, die Sie untersuchen können.

Schauen Sie sich auch an Strategieakquisition für das Spiel Othello basierend auf Verstärkungslernen (PDF -Link) Wenn die Spielregeln angegeben werden, kann eine gute "Auszahlungsfunktion" gelernt werden. Dies ist eng mit dem verwandt mit TD-Gammon ...

Während des Trainings wird das neuronale Netzwerk selbst verwendet, um Bewegungen für beide Seiten auszuwählen ... die ziemlich überraschende Erkenntnis war, dass tatsächlich eine beträchtliche Menge an Lernen tatsächlich stattgefunden hat, selbst in den Null -Erstwissenexperimenten, bei denen eine Rohboard -Kodierung verwendet wurde.

Wenn noch niemand das Spiel versteht, gibt es keine Möglichkeit, eine anständige Bewertungsfunktion zu erhalten. Sagen Sie mir nicht, dass Standard-Alpha-Beta mit Materialzahl gut oder sogar anständig für Schach oder seine Varianten ist (vielleicht ist das Schach von Verlierern eine Ausnahme).

Sie könnten neuronale Netzwerke mit Feedback oder ähnlichen Algorithmen für maschinelles Lernen ausprobieren, aber sie saugen normalerweise bis sie unzählige Schulungen haben, was in diesem Fall wahrscheinlich nicht verfügbar ist. Und selbst dann, wenn sie nicht saugen, können Sie nicht Wissen von ihnen erlangen.

Ich denke, es gibt keine Möglichkeit, das Spiel so gut wie möglich zu verstehen, und lassen Sie die Unbekannten für die Bewertungsfunktion als zufällig (oder nur aus dem Bild, bis die Unbekannten besser bekannt werden).

Wenn Sie weitere Informationen über das Spiel teilen würden, können Sie natürlich bessere Ideen von der Community bekommen.

Soweit ich es verstehe, möchten Sie eine gute statische Bewertungsfunktion an den Blättern Ihres Min-Max-Baumes verwenden. In diesem Fall ist es am besten, sich daran zu erinnern, dass der Zweck dieser statischen Bewertungsfunktion darin besteht, eine Bewertung dafür zu liefern, wie gut das Board für den Computerspieler ist. Auch

f (board1)> f (board2)

Dann muss es wahr sein, dass Board1 für den Computer besser ist (es wird eher gewinnt) als in Board2. Natürlich ist für alle Boards keine statische Funktion jemals vollständig korrekt.

Sie sagen also, dass "das Ziel des Spiels es ist, in bestimmten speziellen Quadraten genug von Ihren Teilen auf dem Brett zu haben", daher würde ein erstes Stich bei F (Board) einfach die Anzahl der Teile, die der Computer auf diesen hat Spezielle Quadrate. Sie können es dann mehr finanzieren.

Ohne die Besonderheiten des Spiels zu kennen, ist es unmöglich, bessere Vermutungen zu geben. Wenn Sie uns die Spielregeln gegeben haben, können die Stackoverflow -Benutzer mit Tonnen von Originalideen für solche Funktionen geliefert werden.

Während Sie verschiedene Methoden für maschinelles Lernen verwenden könnten, um eine Bewertungsfunktion zu entwickeln (TD-Lernen, die in solchen Projekten wie Gnubackgammon verwendet werden, ist ein solches Beispiel), sind die Ergebnisse definitiv vom Spiel selbst abhängig. Für Backgammon funktioniert es wirklich gut, denn die stochastische Natur des Spiels (Rolling Dice) zwingt den Lernenden, das Gebiet zu erkunden, das es möglicherweise nicht tun möchte. Ohne eine so entscheidende Komponente werden Sie wahrscheinlich eine Bewertungsfunktion haben, die gegen sich selbst gut ist, aber nicht gegen andere.

Da der materielle Unterschied möglicherweise nicht anwendbar ist, ist das Konzept der Mobilität wichtig - dh wie viele mögliche Bewegungen, die Sie zur Verfügung haben? Ist die Kontrolle eines bestimmten Bereichs des Boards normalerweise besser als nicht? Sprechen Sie mit den Leuten, die das Spiel spielen, um einige Hinweise zu finden.

Während es vorzuziehen ist, eine so gute Bewertungsfunktion wie möglich zu haben, müssen Sie auch Ihren Suchalgorithmus stimmen, damit Sie nach suchen können tief wie möglich. Manchmal ist dies tatsächlich eher ein Problem, da ein tiefen Sucher mit einer Evaluierungsfunktion von Medicore mit einer guten Bewertungsfunktion flache Suchanfragen übertreffen kann. Es hängt alles von der Domäne ab. (Gnubackgammon spielt beispielsweise ein Expertenspiel mit einer 1-lagigen Suche)

Es gibt noch andere Techniken, mit denen Sie die Qualität Ihrer Suche verbessern können, vor allem eine Transpositionstabelle, um Suchergebnisse zu cache zu erhalten, um ein solides Stürmer zu erhalten.

Ich empfehle dringend, umzuschauen Diese Folien.

Sie müssen auch Ihre Wahl vorsichtig sein. Wenn Ihr Algorithmus keine bekannte Beziehung zum tatsächlichen Wert hat, funktioniert die Standard -AI -Funktionen nicht ordnungsgemäß. Um gültig zu sein, muss Ihre Bewertungsfunktion oder Heuristik gleich oder unter dem tatsächlichen Wert konsequent sein oder Ihre Entscheidungen auf seltsame Weise leiten (was man für Schach argumentieren könnte, obwohl ich denke ).

Was ich normalerweise tue, ist herauszufinden, was fähig ist und was erforderlich ist. Für einige Spiele wie Sokoban habe ich die minimale Anzahl von Boxbewegungen verwendet, die erforderlich sind, um eine Box (isoliert) von seinem aktuellen Ort zu einem der Zielorte zu erhalten. Dies ist keine genaue Antwort auf die Anzahl der erforderlichen Bewegungen, aber ich denke, es ist eine ziemlich gute Heuristik, da es nie überschätzen kann und für das gesamte Board vorbereitet werden kann. Beim Summieren der Punktzahl für eine Platine ist es nur die Summe der Werte für jeden aktuellen Feldstandort.

In einer künstlichen Lebenssimulation, die ich an die Evolve Pack -Jagd und die Packverteidigung schrieb, bestand das von mir verwendete Bewertungssystem darin, die Evolution zu leiten und kein Beschneidung durchzuführen. Ich gab jeder Kreatur einen Punkt, um geboren zu werden. Für jeden Energiepunkt, den sie in ihrem Leben verbrauchten, gab ich ihnen einen zusätzlichen Punkt. Ich habe dann die Summe der Punkte ihrer Generation verwendet, um festzustellen, wie wahrscheinlich jeder sich reproduzieren sollte. In meinem Fall habe ich einfach den Anteil der Gesamtpunkte ihrer Generation verwendet, die sie erworben hatten. Wenn ich Kreaturen entwickeln wollte, die sich hervorragend ausweichen sollten, hätte ich mich dafür gesetzt, dass ich von ihnen Punkte gefressen hätte.

Sie sollten auch darauf achten, dass Ihre Funktion kein zu schweres Ziel ist, zu treffen. Wenn Sie versuchen, etwas zu entwickeln, möchten Sie sicherstellen, dass der Lösungsraum einen anständigen Hang hat. Sie möchten die Entwicklung in eine Richtung leiten und nicht nur einen Sieg erklären, wenn er zufällig getroffen wird.

Ohne mehr über Ihr Spiel zu wissen, wäre ich schwer zu sagen, wie Sie eine Funktion aufbauen können. Gibt es klare Werte von etwas, das einen Sieg oder einen Verlust anzeigt? Haben Sie die Möglichkeit, Mindestkosten zu schätzen, um die Lücke zu schließen?

Wenn Sie weitere Informationen bereitstellen, würde ich gerne versuchen, mehr Einblicke zu geben. Es gibt auch viele ausgezeichnete Bücher zu diesem Thema.

Jacob

Beachten Sie, dass es nicht wahr ist, dass eine anständige Bewertungsfunktion überhaupt existiert. Für diese Aussage gehe ich davon aus, dass eine Bewertungsfunktion von geringer Komplexität (P) sein muss.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow