Einige Zweifel an der Anwendung des Verstärkungslernens auf Spiele wie Schach

9

Ich habe ein schachähnliches Brettspiel erfunden. Ich habe einen Motor gebaut, damit er autonom spielen kann. Der Motor ist im Grunde ein Entscheidungsbaum. Es besteht aus:

  1. Eine Suchfunktion, die an jedem Knoten alle möglichen legalen Bewegungen findet
  2. Eine Bewertungsfunktion, die der Brettposition einen numerischen Wert zuweist (positiv bedeutet, dass der erste Spieler die Oberhand gewinnt, negativ bedeutet, dass der zweite Spieler stattdessen gewinnt)
  3. Ein Alphabeta-Pruning-Negamax-Algorithmus

Das Hauptproblem bei dieser Engine ist, dass die Optimierung der Auswertungsfunktion sehr schwierig ist. Ich weiß nicht, welche Faktoren ich berücksichtigen und welche Gewichte ich setzen soll. Die einzige Möglichkeit, die Engine zu verbessern, besteht darin, Spiele zu wiederholen und jedes Mal verschiedene Kombinationen von Faktoren und Gewichten auszuprobieren. Es scheint jedoch rechnerisch eine sehr schwierige Aufgabe zu sein (Kann ich ohne Verwendung von Deeplearning rückpropagieren?).

Ich möchte das Verstärkungslernen nutzen, um den Motor zu verbessern, indem ich gegen mich selbst spiele. Ich habe über das Thema gelesen, bin aber immer noch ziemlich verwirrt.

Welche andere Belohnung gibt es in einem Spiel als Teil der Gewinn- oder Verlustausgabe (1 oder 0)? Wie kann ich andere Belohnungen implementieren, z. B. die Ausgabe der Bewertungsfunktion in jeder Runde? Wie ändere ich die Bewertungsfunktion, um eine bessere Iteration nach der anderen zu erzielen?

Pigna
quelle

Antworten:

6

Ich möchte das Verstärkungslernen nutzen, um den Motor zu verbessern, indem ich gegen mich selbst spiele. Ich habe über das Thema gelesen, bin aber immer noch ziemlich verwirrt.

Seien Sie gewarnt: Reinforcement Learning ist ein großes komplexes Thema. Obwohl Sie möglicherweise einen Umweg von spielerischen Bots machen, möchten Sie vielleicht die RL-Grundlagen lernen. Ein guter Anfang ist Sutton & Barto Reinforcement Learning: Eine Einführung

Welche andere Belohnung gibt es in einem Spiel als Teil der Gewinn- oder Verlustausgabe (1 oder 0)?

Abhängig von Ihrem Spiel ist das normalerweise so. Tatsächlich ist für ein Gewinn / Unentschieden / Verlieren-Spiel wie Schach die Belohnung für jede Aktion 0, außer für das Gewinnen (+1) oder Verlieren (-1) am Ende. In einem Nullsummenspiel passt dies gut zu Minimax, Alphabetbeschneiden usw.

Reinforcement Learning soll Umgebungen mit verzögerten Belohnungen ansprechen. Das Hinzufügen von "Helfer" -Prämien für vorläufige Nichtziele ist normalerweise kontraproduktiv.

Wie kann ich andere Belohnungen implementieren, z. B. die Ausgabe der Bewertungsfunktion in jeder Runde?

Normalerweise nicht. Wenn Sie selbstspielendes RL anwenden, lernen Sie eine Rückgabefunktion (manchmal auch als Dienstprogramm bezeichnet ), die die Erwartung Ihrer gesamten + 1/0 / -1-Belohnung bis zum Ende des Spiels vorhersagt. Sie würden dies anstelle Ihrer aktuellen Heuristik für die Minimax-Suche verwenden. Oder Sie würden möglicherweise Ihre aktuelle heuristische Funktion so anpassen, dass sie im gleichen Bereich ausgegeben wird, und RL verwenden, um ihre Gewichte zu optimieren, um die beste Annäherung an die wirklich optimale Wiedergabefunktion zu erzielen (die wahrscheinlich zu komplex ist, um genau zu berechnen).

Wie ändere ich die Bewertungsfunktion, um eine bessere Iteration nach der anderen zu erzielen?

Das ist es, was die verschiedenen RL-Ansätze alle versuchen, es gibt eine Vielzahl verschiedener Löser. Es gibt keinen kurzen Weg, es zu erklären. Sie könnten mit einer einfachen Methode wie Q-Learning beginnen . Q-Learning lernt Schätzungen von Q (s, a) (als Aktionswert bezeichnet), die die erwartete Rendite sind, wenn sie sich im Zustand s befinden und Maßnahmen a ergreifen, und danach einer optimalen Richtlinie folgen. Es macht zunächst eine willkürliche Vermutung und verfeinert sie mit jedem Schritt in der Lernumgebung näher an den wahren Wert. Einfache tabellarische Q-Learners führen diese Verfeinerung einfach durch, indem sie eine große Tabelle aller Zustände und Aktionen mit der bisher besten Schätzung des wahren Werts speichern und in jeder neuen Schätzung einen Durchschnitt bilden, wie er erlebt wird.

Es ist auch möglich, eine RL-Methode für Heuristiken mit einer Vorausschau-Minimax-Suche zu kombinieren - genau das hat das ursprüngliche AlphaGo getan und AlphaGo Zero während des Trainings. Dies ist ein leistungsstarker Ansatz, da die Minimax-Suche die RL-generierten Heuristiken überprüft. Obwohl RL für ausreichend einfache Spiele perfekte Heuristiken lernen kann und Sie nur eine lokale Suche benötigen würden (was der nächste Schritt sein sollte).

Sofern Ihr Spiel nicht sehr einfach ist (alle möglichen Zustände würden in den Speicher passen), benötigen Sie eine Art Funktionsapproximator innerhalb des RL-Algorithmus. Neuronale Netze sind eine Standardwahl. Es ist unvermeidlich, etwas für diesen Teil zu haben - obwohl eine andere gute Wahl darin besteht, eine Reihe von Proxy-Features zu definieren (mit denen Sie möglicherweise eine Heuristik von Hand erstellen) und einen linearen Approximator zu verwenden - nur eine gewichtete Summe aller Features. Dies kann gut genug funktionieren und wurde beispielsweise bei Dame-Spielern (Drafts) verwendet, die mit RL trainiert wurden.

Vorausgesetzt, Ihre eigene heuristische Funktion ist nicht zu ungewöhnlich, können Sie sie wahrscheinlich wie einen linearen Approximator behandeln und RL verwenden, um die besten Gewichte dafür zu lernen.

Neil Slater
quelle
"Reinforcement Learning soll Umgebungen mit verzögerten Belohnungen ansprechen. Das Hinzufügen von" Helfer "-Lohnungen für vorläufige Nichtziele ist normalerweise kontraproduktiv." Ich möchte darauf hinweisen, dass es ein Papier gibt, das versucht, das Problem der spärlichen Belohnungen durch die Einführung von Zwischenzielen " Hindsight Experience Replay " zu lösen .
nbro
1
@nbro: Es gibt viele Versuche, spärliche Belohnungen zu lösen. Es ist eine große offene Frage in RL. Eine Möglichkeit, die Herausforderung eines Problems zu erhöhen, besteht darin, Belohnungen spärlicher zu machen. Berechtigungsspuren sind ein weiterer Versuch, Hierarchical RL ist ein weiterer vielversprechender Bereich. . . Ich glaube nicht, dass ich diese Techniken hier zur Antwort hinzufügen möchte, da es mehr um die Machbarkeit des OP-Problems und eine Einführung in das Thema geht
Neil Slater,