MCTS Tic Tac Toe Playground

5,129 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Goal

The goal of this playground is show how the Monte Carlo Tree Search (MCTS) algorithm works, applied to a simple two player game. It is oriented towards people who are acquainted with the theory of MCTS but experience difficulties implementing it. Below is a basic and (hopefully) easy to follow implementation demonstrating the game play of Tic Tac Toe. For ease of reading the four main steps of the algorithm are indicated as comments in the code.

Notice

The code below does not use best practices in programming or MCTS implementation. This playground is to be perceived as a proof of concept example of how the algorithm works. If you want you can contribute by making it more accessible by restructuring it or by translating the code to other languages.

Code

// {
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
class Node implements Comparable <Node> { // representing the state of the game
    
    int player; // 0 if o's turn has been played, 1 otherwise;
    Node parent;
    int [] gameState; // representing the board
    int move; //0-8
    ArrayList<Node> children;
    double numVisits, UCTValue, victories, draws, losses = 0;
    int winner = TicTacToeSimulator.GAME_CONTINUES; // indicates if node is end game node (game is won, lost or drawn)
    
    Node (int pl, Node p, int[] s, int m) {
        player = pl;
        parent = p;
        gameState = s;
        move = m;
        children = new ArrayList<Node>();
    }
    
    @Override
    public int compareTo(Node other) { // sort nodes in descending order according to their UCT value
        
        return Double.compare(other.UCTValue, UCTValue);
    }
    
    void setUCTValue() {
        
        if (numVisits == 0) UCTValue = Double.MAX_VALUE; // make sure every child is visited at least once
        else  UCTValue = ((victories+draws/2) / numVisits) + Math.sqrt(2) * Math.sqrt(Math.log(parent.numVisits) / numVisits);
    }
}
class TicTacToeSimulator {
    static final int EMPTY = -1;
    static final int O = 0;
    static final int X = 1;
    static final int DRAW = 2;
    static final int GAME_CONTINUES = -2;
    
    ArrayList<ArrayList<Integer>> winningMoves; // holds all winning moves for look-up;
    Random rand;
    
    TicTacToeSimulator() {
        

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content

Open Source Your Knowledge, Become a Contributor

Goal

Notice

Code

Smitsimax

Best-First Minimax Search with UCT

On generating opening book for Yavalath MCTS bot

PYTHON: BEGINNER QUIZ (10 Questions)