Monte Carlo Tree Search for Tic-Tac-Toe Game in Java

1. Panoramica

In questo articolo, esploreremo l' algoritmo di Monte Carlo Tree Search (MCTS) e le sue applicazioni.

Vedremo le sue fasi in dettaglio implementando il gioco del Tic-Tac-Toe in Java . Progetteremo una soluzione generale che potrebbe essere utilizzata in molte altre applicazioni pratiche, con modifiche minime.

2. Introduzione

In poche parole, la ricerca ad albero Monte Carlo è un algoritmo di ricerca probabilistica. È un algoritmo decisionale unico per la sua efficienza in ambienti aperti con un'enorme quantità di possibilità.

Se hai già familiarità con algoritmi di teoria dei giochi come Minimax, richiede una funzione per valutare lo stato corrente e deve calcolare molti livelli nell'albero del gioco per trovare la mossa ottimale.

Sfortunatamente, non è possibile farlo in un gioco come Go in cui c'è un alto fattore di ramificazione (che si traduce in milioni di possibilità all'aumentare dell'altezza dell'albero), ed è difficile scrivere una buona funzione di valutazione per calcolare quanto è buono il lo stato attuale è.

La ricerca dell'albero Monte Carlo applica il metodo Monte Carlo alla ricerca dell'albero del gioco. Poiché si basa su un campionamento casuale degli stati del gioco, non è necessario che la forza bruta venga fuori da ogni possibilità. Inoltre, non richiede necessariamente di scrivere una valutazione o buone funzioni euristiche.

E, una breve nota a margine: ha rivoluzionato il mondo del computer Go. Da marzo 2016, è diventato un argomento di ricerca prevalente poiché AlphaGo di Google (costruito con MCTS e rete neurale) ha battuto Lee Sedol (il campione del mondo in Go).

3. Algoritmo di ricerca ad albero Monte Carlo

Ora, esploriamo come funziona l'algoritmo. Inizialmente, costruiremo un albero lookahead (albero del gioco) con un nodo radice, e poi continueremo ad espanderlo con implementazioni casuali. Nel processo, manterremo il conteggio delle visite e il conteggio delle vittorie per ogni nodo.

Alla fine, selezioneremo il nodo con le statistiche più promettenti.

L'algoritmo è costituito da quattro fasi; esploriamoli tutti in dettaglio.

3.1. Selezione

In questa fase iniziale, l'algoritmo inizia con un nodo radice e seleziona un nodo figlio in modo tale da scegliere il nodo con la percentuale di vincita massima. Vogliamo anche assicurarci che ogni nodo abbia una giusta possibilità.

L'idea è di continuare a selezionare i nodi figlio ottimali fino a raggiungere il nodo foglia dell'albero. Un buon modo per selezionare un nodo figlio di questo tipo è usare la formula UCT (Upper Confidence Bound applicato agli alberi):

In quale

  • w i = numero di vittorie dopo l' i -esima mossa
  • n i = numero di simulazioni dopo l' i -esima mossa
  • c = parametro di esplorazione (teoricamente uguale a √2)
  • t = numero totale di simulazioni per il nodo padre

La formula garantisce che nessuno stato sarà vittima della fame e gioca anche rami promettenti più spesso delle loro controparti.

3.2. Espansione

Quando non può più applicare UCT per trovare il nodo successore, espande l'albero del gioco aggiungendo tutti gli stati possibili dal nodo foglia.

3.3. Simulazione

Dopo l'espansione, l'algoritmo sceglie arbitrariamente un nodo figlio e simula un gioco randomizzato dal nodo selezionato fino a raggiungere lo stato del gioco risultante. Se i nodi vengono selezionati in modo casuale o semi-casuale durante il play out, si parla di light play out. Puoi anche optare per un gioco pesante scrivendo euristiche di qualità o funzioni di valutazione.

3.4. Backpropagation

Questa è anche nota come fase di aggiornamento. Una volta che l'algoritmo raggiunge la fine del gioco, valuta lo stato per capire quale giocatore ha vinto. Si sposta verso l'alto fino alla radice e aumenta il punteggio della visita per tutti i nodi visitati. Aggiorna anche il punteggio di vittoria per ogni nodo se il giocatore per quella posizione ha vinto il playout.

MCTS continua a ripetere queste quattro fasi fino a un determinato numero di iterazioni o fino a un determinato periodo di tempo.

In questo approccio, stimiamo il punteggio vincente per ogni nodo in base a mosse casuali. Quindi più alto è il numero di iterazioni, più affidabile diventa la stima. Le stime dell'algoritmo saranno meno accurate all'inizio di una ricerca e continueranno a migliorare dopo un periodo di tempo sufficiente. Anche in questo caso dipende esclusivamente dal tipo di problema.

4. Funzionamento a secco

Qui, i nodi contengono statistiche come visite totali / punteggio di vittoria.

5. Attuazione

Ora, implementiamo un gioco di Tic-Tac-Toe, utilizzando l'algoritmo di ricerca dell'albero Monte Carlo.

Progetteremo una soluzione generalizzata per MCTS che può essere utilizzata anche per molti altri giochi da tavolo. Daremo uno sguardo alla maggior parte del codice nell'articolo stesso.

Anche se per rendere la spiegazione chiara, potremmo dover saltare alcuni dettagli minori (non particolarmente relativi a MCTS), ma puoi sempre trovare l'implementazione completa qui.

Prima di tutto, abbiamo bisogno di un'implementazione di base per le classi Tree e Node per avere una funzionalità di ricerca ad albero:

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

Poiché ogni nodo avrà uno stato particolare del problema, implementiamo anche una classe State :

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 */ } }

Now, let's implement MonteCarloTreeSearch class, which will be responsible for finding the next best move from the given game position:

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(); } }

Here, we keep iterating over all of the four phases until the predefined time, and at the end, we get a tree with reliable statistics to make a smart decision.

Now, let's implement methods for all the phases.

We will start with the selection phase which requires UCT implementation as well:

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()))); } }

This phase recommends a leaf node which should be expanded further in the expansion phase:

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); }); }

Next, we write code to pick a random node and simulate a random play out from it. Also, we will have an update function to propagate score and visit count starting from leaf to root:

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

A prima vista, è difficile credere che un algoritmo basato su scelte casuali possa portare a un'intelligenza artificiale intelligente. Tuttavia, un'attenta implementazione di MCTS può effettivamente fornirci una soluzione che può essere utilizzata in molti giochi così come nei problemi decisionali.

Come sempre, il codice completo per l'algoritmo può essere trovato su GitHub.