Monte Carlo Tree Search pour le jeu Tic-Tac-Toe en Java

1. Vue d'ensemble

Dans cet article, nous allons explorer l' algorithme de Monte Carlo Tree Search (MCTS) et ses applications.

Nous allons regarder ses phases en détail en implémentant le jeu de Tic-Tac-Toe en Java . Nous allons concevoir une solution générale qui pourrait être utilisée dans de nombreuses autres applications pratiques, avec des changements minimes.

2. Présentation

En termes simples, la recherche arborescente de Monte Carlo est un algorithme de recherche probabiliste. C'est un algorithme de prise de décision unique en raison de son efficacité dans des environnements ouverts avec une énorme quantité de possibilités.

Si vous êtes déjà familiarisé avec les algorithmes de théorie des jeux comme Minimax, il nécessite une fonction pour évaluer l'état actuel et il doit calculer de nombreux niveaux dans l'arborescence du jeu pour trouver le mouvement optimal.

Malheureusement, il n'est pas possible de le faire dans un jeu comme Go dans lequel le facteur de ramification est élevé (ce qui entraîne des millions de possibilités lorsque la hauteur de l'arbre augmente), et il est difficile d'écrire une bonne fonction d'évaluation pour calculer la qualité du l'état actuel est.

La recherche arborescente Monte Carlo applique la méthode Monte Carlo à la recherche arborescente du jeu. Comme il est basé sur un échantillonnage aléatoire des états du jeu, il n'a pas besoin de forcer brutalement pour sortir de chaque possibilité. De plus, cela ne nous oblige pas nécessairement à écrire une évaluation ou de bonnes fonctions heuristiques.

Et, une remarque rapide - il a révolutionné le monde de l'ordinateur Go. Depuis mars 2016, il est devenu un sujet de recherche répandu alors que l'AlphaGo de Google (construit avec les SCTM et le réseau de neurones) a battu Lee Sedol (le champion du monde de Go).

3. Algorithme de recherche arborescente de Monte Carlo

Voyons maintenant comment fonctionne l'algorithme. Au départ, nous allons créer un arbre de recherche (arbre de jeu) avec un nœud racine, puis nous continuerons de l'étendre avec des déploiements aléatoires. Dans le processus, nous maintiendrons le nombre de visites et le nombre de victoires pour chaque nœud.

En fin de compte, nous allons sélectionner le nœud avec les statistiques les plus prometteuses.

L'algorithme se compose de quatre phases; explorons-les tous en détail.

3.1. Sélection

Dans cette phase initiale, l'algorithme démarre avec un nœud racine et sélectionne un nœud enfant de telle sorte qu'il sélectionne le nœud avec un taux de victoire maximal. Nous voulons également nous assurer que chaque nœud a une chance équitable.

L'idée est de continuer à sélectionner les nœuds enfants optimaux jusqu'à ce que nous atteignions le nœud feuille de l'arbre. Un bon moyen de sélectionner un tel nœud enfant est d'utiliser la formule UCT (Upper Confidence Bound appliquée aux arbres):

Dans lequel

  • w i = nombre de victoires après le i- ème coup
  • n i = nombre de simulations après le i- ème coup
  • c = paramètre d'exploration (théoriquement égal à √2)
  • t = nombre total de simulations pour le nœud parent

La formule garantit qu'aucun État ne sera victime de la famine et elle joue également plus souvent les branches prometteuses que leurs homologues.

3.2. Expansion

Lorsqu'il ne peut plus appliquer UCT pour trouver le nœud successeur, il étend l'arborescence du jeu en ajoutant tous les états possibles à partir du nœud feuille.

3.3. Simulation

Après l'expansion, l'algorithme choisit arbitrairement un nœud enfant et simule un jeu aléatoire à partir du nœud sélectionné jusqu'à ce qu'il atteigne l'état résultant du jeu. Si les nœuds sont choisis aléatoirement ou semi-aléatoirement pendant la lecture, on parle de lecture légère. Vous pouvez également opter pour une lecture intensive en écrivant des heuristiques de qualité ou des fonctions d'évaluation.

3.4. Rétropropagation

Ceci est également connu sous le nom de phase de mise à jour. Une fois que l'algorithme atteint la fin du jeu, il évalue l'état pour déterminer quel joueur a gagné. Il parcourt vers le haut jusqu'à la racine et incrémente le score de visite pour tous les nœuds visités. Il met également à jour le score de victoire pour chaque nœud si le joueur pour cette position a remporté le playout.

Les SCTM continuent de répéter ces quatre phases jusqu'à un certain nombre fixe d'itérations ou une durée fixe.

Dans cette approche, nous estimons le score gagnant pour chaque nœud en fonction de mouvements aléatoires. Donc, plus le nombre d'itérations est élevé, plus l'estimation devient fiable. Les estimations de l'algorithme seront moins précises au début d'une recherche et continueront de s'améliorer après un laps de temps suffisant. Encore une fois, cela dépend uniquement du type de problème.

4. Exécution à sec

Ici, les nœuds contiennent des statistiques en tant que nombre total de visites / score de victoire.

5. Mise en œuvre

Maintenant, implémentons un jeu de Tic-Tac-Toe - en utilisant l'algorithme de recherche d'arbre de Monte Carlo.

Nous allons concevoir une solution généralisée pour les SCTM qui peut également être utilisée pour de nombreux autres jeux de société. Nous examinerons la plupart du code dans l'article lui-même.

Bien que pour rendre l'explication claire, nous devrons peut-être ignorer quelques détails mineurs (pas particulièrement liés aux SCTM), mais vous pouvez toujours trouver l'implémentation complète ici.

Tout d'abord, nous avons besoin d'une implémentation de base pour les classes Tree et Node pour avoir une fonctionnalité de recherche dans l'arborescence:

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

Comme chaque nœud aura un état particulier du problème, implémentons également une 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

À première vue, il est difficile de croire qu'un algorithme reposant sur des choix aléatoires puisse conduire à une IA intelligente. Cependant, une mise en œuvre réfléchie des SCTM peut en effet nous fournir une solution qui peut être utilisée dans de nombreux jeux ainsi que dans des problèmes de prise de décision.

Comme toujours, le code complet de l'algorithme peut être trouvé sur GitHub.