Monte Carlo Tree Suche nach Tic-Tac-Toe-Spiel in Java

1. Übersicht

In diesem Artikel werden wir den MCTS-Algorithmus (Monte Carlo Tree Search) und seine Anwendungen untersuchen.

Wir werden die Phasen im Detail betrachten, indem wir das Spiel Tic-Tac-Toe in Java implementieren . Wir werden eine allgemeine Lösung entwerfen, die mit minimalen Änderungen in vielen anderen praktischen Anwendungen verwendet werden kann.

2. Einführung

Einfach ausgedrückt ist die Monte-Carlo-Baumsuche ein probabilistischer Suchalgorithmus. Es ist ein einzigartiger Entscheidungsalgorithmus aufgrund seiner Effizienz in offenen Umgebungen mit einer enormen Menge an Möglichkeiten.

Wenn Sie bereits mit spieltheoretischen Algorithmen wie Minimax vertraut sind, ist eine Funktion zum Auswerten des aktuellen Status erforderlich, und es müssen viele Ebenen im Spielbaum berechnet werden, um den optimalen Zug zu finden.

Leider ist dies in einem Spiel wie Go mit einem hohen Verzweigungsfaktor nicht möglich (was mit zunehmender Höhe des Baums zu Millionen von Möglichkeiten führt), und es ist schwierig, eine gute Bewertungsfunktion zu schreiben, um zu berechnen, wie gut die ist aktueller Stand ist.

Die Monte-Carlo-Baumsuche wendet die Monte-Carlo-Methode auf die Spielbaumsuche an. Da es auf einer zufälligen Stichprobe von Spielzuständen basiert, muss es sich nicht brutal aus jeder Möglichkeit herauszwingen. Außerdem müssen wir nicht unbedingt eine Bewertung oder gute heuristische Funktionen schreiben.

Und noch eine kurze Randnotiz: Sie hat die Welt von Computer Go revolutioniert. Seit März 2016 ist es ein weit verbreitetes Forschungsthema, da Googles AlphaGo (gebaut mit MCTS und neuronalen Netzen) Lee Sedol (den Weltmeister in Go) besiegte.

3. Monte-Carlo-Baumsuchalgorithmus

Lassen Sie uns nun untersuchen, wie der Algorithmus funktioniert. Zunächst erstellen wir einen Lookahead-Baum (Spielbaum) mit einem Stammknoten und erweitern ihn dann mit zufälligen Rollouts. Dabei behalten wir die Anzahl der Besuche und die Anzahl der Gewinne für jeden Knoten bei.

Am Ende werden wir den Knoten mit den vielversprechendsten Statistiken auswählen.

Der Algorithmus besteht aus vier Phasen; Lassen Sie uns alle im Detail untersuchen.

3.1. Auswahl

In dieser Anfangsphase beginnt der Algorithmus mit einem Wurzelknoten und wählt einen untergeordneten Knoten so aus, dass er den Knoten mit der maximalen Gewinnrate auswählt. Wir möchten auch sicherstellen, dass jedem Knoten eine faire Chance gegeben wird.

Die Idee ist, weiterhin optimale untergeordnete Knoten auszuwählen, bis wir den Blattknoten des Baums erreichen. Eine gute Möglichkeit, einen solchen untergeordneten Knoten auszuwählen, ist die Verwendung der UCT-Formel (Upper Confidence Bound, angewendet auf Bäume):

In welchem

  • w i = Anzahl der Siege nach dem i- ten Zug
  • n i = Anzahl der Simulationen nach dem i- ten Zug
  • c = Explorationsparameter (theoretisch gleich √2)
  • t = Gesamtzahl der Simulationen für den übergeordneten Knoten

Die Formel stellt sicher, dass kein Staat Opfer von Hunger wird, und sie spielt auch häufiger vielversprechende Zweige als ihre Kollegen.

3.2. Erweiterung

Wenn UCT nicht mehr angewendet werden kann, um den Nachfolgeknoten zu finden, wird der Spielbaum erweitert, indem alle möglichen Zustände vom Blattknoten angehängt werden.

3.3. Simulation

Nach der Erweiterung wählt der Algorithmus einen untergeordneten Knoten willkürlich aus und simuliert ein zufälliges Spiel vom ausgewählten Knoten, bis der resultierende Status des Spiels erreicht ist. Wenn Knoten während des Ausspielens zufällig oder halb zufällig ausgewählt werden, spricht man von leichtem Ausspielen. Sie können sich auch für ein intensives Spiel entscheiden, indem Sie hochwertige Heuristiken oder Bewertungsfunktionen schreiben.

3.4. Backpropagation

Dies wird auch als Aktualisierungsphase bezeichnet. Sobald der Algorithmus das Ende des Spiels erreicht hat, wertet er den Status aus, um herauszufinden, welcher Spieler gewonnen hat. Es geht nach oben zum Stamm und erhöht die Besuchsbewertung für alle besuchten Knoten. Außerdem wird die Gewinnpunktzahl für jeden Knoten aktualisiert, wenn der Spieler für diese Position das Playout gewonnen hat.

MCTS wiederholt diese vier Phasen so lange, bis eine feste Anzahl von Iterationen oder eine feste Zeitspanne erreicht ist.

Bei diesem Ansatz schätzen wir die Gewinnpunktzahl für jeden Knoten basierend auf zufälligen Bewegungen. Je höher die Anzahl der Iterationen, desto zuverlässiger wird die Schätzung. Die Algorithmusschätzungen sind zu Beginn einer Suche weniger genau und verbessern sich nach ausreichender Zeit weiter. Auch hier kommt es nur auf die Art des Problems an.

4. Trockenlauf

Hier enthalten Knoten Statistiken als Gesamtbesuche / Gewinnpunktzahl.

5. Implementierung

Lassen Sie uns nun ein Tic-Tac-Toe-Spiel implementieren - unter Verwendung des Monte-Carlo-Baumsuchalgorithmus.

Wir werden eine allgemeine Lösung für MCTS entwickeln, die auch für viele andere Brettspiele verwendet werden kann. Wir werden uns den größten Teil des Codes im Artikel selbst ansehen.

Um die Erklärung klar zu machen, müssen wir möglicherweise einige kleinere Details überspringen (die nicht besonders mit MCTS zusammenhängen), aber die vollständige Implementierung finden Sie immer hier.

Zunächst benötigen wir eine grundlegende Implementierung für Baum- und Knotenklassen , um eine Baumsuchfunktion zu haben:

public class Node { State state; Node parent; List childArray; // setters and getters } public class Tree { Node root; }

Da jeder Knoten einen bestimmten Status des Problems hat, implementieren wir auch eine Statusklasse :

public class State { Board board; int playerNo; int visitCount; double winScore; // copy constructor, getters, and setters public List getAllPossibleStates() { // constructs a list of all possible states from current state } public void randomPlay() { /* get a list of all possible positions on the board and play a random move */ } }

Implementieren wir nun die MonteCarloTreeSearch- Klasse, die dafür verantwortlich ist, den nächstbesten Zug von der angegebenen Spielposition aus zu finden:

public class MonteCarloTreeSearch { static final int WIN_SCORE = 10; int level; int opponent; public Board findNextMove(Board board, int playerNo) { // define an end time which will act as a terminating condition opponent = 3 - playerNo; Tree tree = new Tree(); Node rootNode = tree.getRoot(); rootNode.getState().setBoard(board); rootNode.getState().setPlayerNo(opponent); while (System.currentTimeMillis()  0) { nodeToExplore = promisingNode.getRandomChildNode(); } int playoutResult = simulateRandomPlayout(nodeToExplore); backPropogation(nodeToExplore, playoutResult); } Node winnerNode = rootNode.getChildWithMaxScore(); tree.setRoot(winnerNode); return winnerNode.getState().getBoard(); } }

Hier durchlaufen wir alle vier Phasen bis zur vordefinierten Zeit und erhalten am Ende einen Baum mit zuverlässigen Statistiken, um eine kluge Entscheidung zu treffen.

Lassen Sie uns nun Methoden für alle Phasen implementieren.

Wir beginnen mit der Auswahlphase, die auch die UCT-Implementierung erfordert:

private Node selectPromisingNode(Node rootNode) { Node node = rootNode; while (node.getChildArray().size() != 0) { node = UCT.findBestNodeWithUCT(node); } return node; }
public class UCT { public static double uctValue( int totalVisit, double nodeWinScore, int nodeVisit) { if (nodeVisit == 0) { return Integer.MAX_VALUE; } return ((double) nodeWinScore / (double) nodeVisit) + 1.41 * Math.sqrt(Math.log(totalVisit) / (double) nodeVisit); } public static Node findBestNodeWithUCT(Node node) { int parentVisit = node.getState().getVisitCount(); return Collections.max( node.getChildArray(), Comparator.comparing(c -> uctValue(parentVisit, c.getState().getWinScore(), c.getState().getVisitCount()))); } }

In dieser Phase wird ein Blattknoten empfohlen, der in der Erweiterungsphase weiter ausgebaut werden sollte:

private void expandNode(Node node) { List possibleStates = node.getState().getAllPossibleStates(); possibleStates.forEach(state -> { Node newNode = new Node(state); newNode.setParent(node); newNode.getState().setPlayerNo(node.getState().getOpponent()); node.getChildArray().add(newNode); }); }

Als nächstes schreiben wir Code, um einen zufälligen Knoten auszuwählen und ein zufälliges Spiel daraus zu simulieren. Außerdem werden wir eine Aktualisierungsfunktion haben , um die Punktzahl und die Anzahl der Besuche von Blatt zu Wurzel zu verbreiten:

private void backPropogation(Node nodeToExplore, int playerNo) { Node tempNode = nodeToExplore; while (tempNode != null) { tempNode.getState().incrementVisit(); if (tempNode.getState().getPlayerNo() == playerNo) { tempNode.getState().addScore(WIN_SCORE); } tempNode = tempNode.getParent(); } } private int simulateRandomPlayout(Node node) { Node tempNode = new Node(node); State tempState = tempNode.getState(); int boardStatus = tempState.getBoard().checkStatus(); if (boardStatus == opponent) { tempNode.getParent().getState().setWinScore(Integer.MIN_VALUE); return boardStatus; } while (boardStatus == Board.IN_PROGRESS) { tempState.togglePlayer(); tempState.randomPlay(); boardStatus = tempState.getBoard().checkStatus(); } return boardStatus; }

Now we are done with the implementation of MCTS. All we need is a Tic-Tac-Toe particular Board class implementation. Notice that to play other games with our implementation; We just need to change Board class.

public class Board { int[][] boardValues; public static final int DEFAULT_BOARD_SIZE = 3; public static final int IN_PROGRESS = -1; public static final int DRAW = 0; public static final int P1 = 1; public static final int P2 = 2; // getters and setters public void performMove(int player, Position p) { this.totalMoves++; boardValues[p.getX()][p.getY()] = player; } public int checkStatus() { /* Evaluate whether the game is won and return winner. If it is draw return 0 else return -1 */ } public List getEmptyPositions() { int size = this.boardValues.length; List emptyPositions = new ArrayList(); for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (boardValues[i][j] == 0) emptyPositions.add(new Position(i, j)); } } return emptyPositions; } }

We just implemented an AI which can not be beaten in Tic-Tac-Toe. Let's write a unit case which demonstrates that AI vs. AI will always result in a draw:

@Test public void givenEmptyBoard_whenSimulateInterAIPlay_thenGameDraw() { Board board = new Board(); int player = Board.P1; int totalMoves = Board.DEFAULT_BOARD_SIZE * Board.DEFAULT_BOARD_SIZE; for (int i = 0; i < totalMoves; i++) { board = mcts.findNextMove(board, player); if (board.checkStatus() != -1) { break; } player = 3 - player; } int winStatus = board.checkStatus(); assertEquals(winStatus, Board.DRAW); }

6. Advantages

  • It does not necessarily require any tactical knowledge about the game
  • A general MCTS implementation can be reused for any number of games with little modification
  • Focuses on nodes with higher chances of winning the game
  • Suitable for problems with high branching factor as it does not waste computations on all possible branches
  • Algorithm is very straightforward to implement
  • Execution can be stopped at any given time, and it will still suggest the next best state computed so far

7. Drawback

If MCTS is used in its basic form without any improvements, it may fail to suggest reasonable moves. It may happen if nodes are not visited adequately which results in inaccurate estimates.

However, MCTS can be improved using some techniques. It involves domain specific as well as domain-independent techniques.

In domain specific techniques, simulation stage produces more realistic play outs rather than stochastic simulations. Though it requires knowledge of game specific techniques and rules.

8. Summary

Auf den ersten Blick ist es schwierig zu vertrauen, dass ein Algorithmus, der sich auf zufällige Entscheidungen stützt, zu einer intelligenten KI führen kann. Eine durchdachte Implementierung von MCTS kann uns jedoch tatsächlich eine Lösung bieten, die sowohl in vielen Spielen als auch bei Entscheidungsproblemen eingesetzt werden kann.

Wie immer finden Sie den vollständigen Code für den Algorithmus auf GitHub.