Maschineller Lernalgorithmus zum Spielen von Connect Four

14

Ich lese gerade über maschinelles Lernen und überlege, wie ich es auf das Spielen von Connect Four anwenden kann .

Mein aktueller Versuch ist ein einfacher Klassifikator für mehrere Klassen, der ein Sigmoid-Funktionsmodell und die Ein-gegen-Alles-Methode verwendet.

Meiner Meinung nach müssen die Eingabemerkmale der Status (CD von Player 1, CD von Player 2, leer) der 7x6 = 42-Rasterfelder sein.

Die Ausgabe wäre die Nummer der Zeile, in die die Disc eingelegt werden soll. Da dies eine diskrete Zahl zwischen 1 und 7 ist, kann dies vermutlich als ein Problem der Klassifizierung mehrerer Klassen behandelt werden.

Aber wie erstelle ich Trainingsbeispiele, die für betreutes Lernen geeignet sind?

Das Hauptziel ist es, das Spiel zu gewinnen, aber das Ergebnis ist offensichtlich nicht bekannt, wenn man bis zur letzten Runde spielt. Wenn ich nur zwei Spieler, die nach dem Zufallsprinzip entscheiden, was zu tun ist, tausende Male gegeneinander spielen lasse, reicht es dann aus, einfach alle Spielzüge, die der Gewinner einer Spielrunde gemacht hat, als Trainingsbeispiele zu nehmen? Oder muss ich das ganz anders machen?

Bearbeiten: Wie in den Kommentaren vorgeschlagen, habe ich ein wenig über das Lernen von Bestärkungen gelesen. Soweit ich weiß, sollte Q-Learning den Trick machen, dh ich muss eine Funktion Q des aktuellen Zustands und die zu ergreifende Aktion approximieren, um die maximale kumulative Belohnung zu sein, die in diesem Zustand beginnt. Dann müsste in jedem Schritt die Aktion ausgewählt werden, die den Maximalwert von Q ergibt. Dieses Spiel hat jedoch viel zu viele Zustände, um dies z. B. als Nachschlagetabelle durchzuführen. Was ist also ein effektiver Weg, um diese Q-Funktion zu modellieren?

Tom
quelle
2
Google "Reinforcement Learning"
George
Okay, ich denke, das trifft wirklich genau auf dieses Problem zu. Es scheint, dass noch viel zu lesen ist. Gibt es spezifischere Hinweise oder Empfehlungen?
Tom
1
Wenn ich mehr wüsste, würde ich es als Antwort posten :) Leider habe ich keine Erfahrung mit dem Erlernen von Verstärkung. Ich würde aus dem Buch "Machine Learning" von Tom Mitchell beginnen. Es ist ein sehr gutes Einführungsbuch und enthält auch ein Kapitel über Reinforcement Learning.
George
1
Letzteres, ich bin nur neugierig auf maschinelles Lernen und versuche es kennenzulernen.
Tom
1
@ Tom, es gibt bessere Möglichkeiten, maschinelles Lernen kennenzulernen. Ich beginne mit grundlegenderen Klassifizierungs- und Regressionstechniken und gehe von dort aus weiter. Sie können Datensätze aus dem UCI-Datenrepository für maschinelles Lernen abrufen, die Notizen zum maschinellen Lernen von Andrew Ng (Stanford) lesen und sich implementieren lassen. Es scheint ziemlich umständlich und übermäßig kompliziert, direkt in den Versuch einzusteigen, Connect 4 mithilfe von Verstärkung zu lösen.
Nick

Antworten:

8

Um eine einfachere Alternative zum Verstärken des Lernens zu bieten, können Sie den grundlegenden Minimax-Algorithmus verwenden, um nach guten Zügen zu suchen, und maschinelles Lernen verwenden, um die Brettpositionen zu bewerten.

Zur Verdeutlichung erstellt Minimax einen Spielbaum, in dem jeder Knoten mit dem Ergebnis der Blätter beschriftet ist (1 = Spieler A gewinnt, 0 = Spieler B gewinnt), vorausgesetzt, A wählt die Züge, die diese Zahl maximieren, und B wählt die Züge das minimiert es.

Wenn das Spiel nicht sehr einfach ist, können Sie nicht den gesamten Spielbaum bis zu den Terminals erstellen. Sie müssen stattdessen an unfertigen Brettpositionen anhalten und die Blätter mit einer Heuristik bewerten (im Wesentlichen die Wahrscheinlichkeit, dass Spieler A von der angegebenen Position gewinnt). Sie können einen Algorithmus für maschinelles Lernen wie ein neuronales Netzwerk versuchen lassen, diese Wahrscheinlichkeit aus der Verbindung von vier Positionen mit bekannten Ergebnissen zu lernen.

Um Trainingsbeispiele zu generieren, können Sie Ihren Minimax-Player mit einer einfachen Heuristik erstellen, ihn tausendmal spielen lassen, diese Spiele zum Trainieren Ihres ersten neuronalen Netzwerks verwenden und sich dann tausendmal auszahlen lassen und so weiter. Mit etwas Glück verbessert sich Ihr System mit jeder Generation.

Peter
quelle
2

Ich habe vor einiger Zeit einen Blogpost über die Verwendung von Minimax zum Spielen von Connect Four geschrieben. Sie können den Code hier in Aktion sehen . Wenn Sie Ihre Modelle trainieren müssen, können Sie es vielleicht ein paar tausend Spiele gegen meine Minimax-Implementierung spielen lassen.

Lukas Vermeer
quelle
Fühlen Sie sich frei, meinen Code auf Github zu verbreiten. github.com/lukasvermeer/minimax
Lukas Vermeer
Willkommen bei Stack Exchange. Dies ist eine Frage- und Antwortseite . Bitte lesen Sie unsere FAQ , insbesondere wie man antwortet . Insbesondere möchten wir keine Posts, die nur aus einem Link zu einer Antwort bestehen. Vielen Dank für Ihren Beitrag, aber können Sie bitte die wichtigsten Punkte Ihres Blog-Beitrags in Ihrem Beitrag hier zusammenfassen?
Gilles 'SO- hör auf, böse zu sein'
Es tut mir leid, aber die ursprüngliche Frage lautete: "Wie erstelle ich Trainingsbeispiele, die für betreutes Lernen geeignet sind?" Ich habe Links zu Arbeitscode bereitgestellt, mit denen diese generiert werden können. Ich verstehe nicht, wie das Schreiben von mehr Text helfen würde, das ursprüngliche Bedürfnis zu befriedigen.
Lukas Vermeer,
"Ein Link zu einer möglichen Lösung ist immer willkommen, aber fügen Sie bitte einen Kontext um den Link hinzu, damit Ihre Mitbenutzer eine Vorstellung davon haben, was es ist und warum es dort ist. Geben Sie immer den relevantesten Teil eines wichtigen Links an, falls es sich um die Zielwebsite handelt ist nicht erreichbar oder geht permanent offline. " Ich glaube, ich habe das erstere gemacht. Letzteres wäre irrelevant. Die ursprüngliche Frage benötigt Beispielspiele und keine Erklärung für die Implementierung einer Lösung.
Lukas Vermeer,