# JSMCTS

JSMCTS is a JavaScript implementation of Monte Carlo Tree Search (MCTS) that enables the creation of game-playing AIs running entirely in web browsers or on Node.js. The library uses the Upper Confidence Bounds for Trees (UCT) algorithm to guide exploration of game trees and random playout to evaluate moves, requiring no game-specific strategies—only the rules of the game.

The library provides a complete framework for implementing two-player games with both deterministic and nondeterministic (chance-based) mechanics. It includes base classes for defining game states, actions, and players, along with built-in RandomPlayer and MCTSPlayer implementations. JSMCTS supports both synchronous operation (for command-line simulations) and asynchronous operation (for responsive web interfaces), with determinization support for handling randomness in games like Backgammon through a seedable pseudo-random number generator (xorshift128+).

## Core Classes

### mcts.Game - Base Game State Class

The base class for implementing game state. Subclass this to define your game's board representation, win conditions, and legal moves. The constructor accepts configuration options for the number of players and whether the game is nondeterministic.

```javascript
const mcts = require('mcts');

// Define a custom game by extending mcts.Game
exports.Game = function(o) {
    if (o instanceof exports.Game) {
        // Copy constructor - clone game state
        mcts.Game.call(this, o);
        this.board = o.board.slice();
    } else {
        // Initialize new game
        mcts.Game.call(this, { nPlayers: 2 });
        this.board = [0, 0, 0,
                      0, 0, 0,
                      0, 0, 0];
    }
};

exports.Game.prototype = Object.create(mcts.Game.prototype);

// Must implement copyGame() for MCTS simulations
exports.Game.prototype.copyGame = function() {
    return new exports.Game(this);
};

// Example: Create and query game state
var g = new exports.Game();
console.log(g.currentPlayer);  // 1
console.log(g.currentTurn);    // 1
console.log(g.isGameOver());   // false
console.log(g.winner);         // -1 (game in progress)
```

### mcts.Action - Base Action Class

The base class for representing game moves. Subclass this to define the data needed to describe a move in your game.

```javascript
const mcts = require('mcts');

// Define actions for Tic-Tac-Toe (position 1-9)
exports.Action = function(p) {
    mcts.Action.call(this);
    this.pos = p;  // Board position (1-9)
};

exports.Action.prototype = Object.create(mcts.Action.prototype);

// Implement toString() for debugging and display
exports.Action.prototype.toString = function() {
    return "" + this.pos;
};

// Example: Create and display action
var action = new exports.Action(5);  // Center position
console.log(action.toString());  // "5"
```

### Game.prototype.allActions() - Generate Legal Moves

Implement this method to return all legal actions for the current player given the current game state. MCTS uses this to explore possible moves.

```javascript
// Tic-Tac-Toe: Return action for each empty cell
exports.Game.prototype.allActions = function() {
    var as = [];
    for (var i = 0; i < this.board.length; i++) {
        if (this.board[i] == 0) {
            as.push(new exports.Action(1 + i));
        }
    }
    return as;
};

// Example usage
var g = new exports.Game();
var actions = g.allActions();
console.log(actions.length);  // 9 (all cells empty initially)
console.log(actions.map(a => a.pos));  // [1, 2, 3, 4, 5, 6, 7, 8, 9]
```

### Game.prototype.doAction(action) - Apply Move

Implement this method to apply an action to the game state, updating the board, checking for win conditions, and advancing to the next player's turn.

```javascript
exports.Game.prototype.doAction = function(a) {
    mcts.Game.prototype.doAction.call(this, a);

    // Mark the cell with current player's token
    this.board[a.pos - 1] = this.currentPlayer;

    // Check for winning lines
    var lines = [[0,1,2], [3,4,5], [6,7,8],  // rows
                 [0,3,6], [1,4,7], [2,5,8],  // columns
                 [0,4,8], [2,4,6]];          // diagonals

    var hasEmpty = false;
    for (var i = 0; i < lines.length; i++) {
        var line = lines[i];
        var n1 = 0, n2 = 0;
        for (var j = 0; j < line.length; j++) {
            if (this.board[line[j]] == 1) n1++;
            else if (this.board[line[j]] == 2) n2++;
            else hasEmpty = true;
        }
        if (n1 == 3) { this.winner = 1; return; }
        if (n2 == 3) { this.winner = 2; return; }
    }

    // Check for draw or continue
    if (!hasEmpty) {
        this.winner = 0;  // Draw
    } else {
        this.currentTurn++;
        this.currentPlayer = (this.currentPlayer % 2) + 1;
    }
};

// Example: Play a move
var g = new exports.Game();
g.doAction(new exports.Action(5));  // Player 1 marks center
console.log(g.currentPlayer);  // 2 (now player 2's turn)
console.log(g.board[4]);  // 1 (center marked by player 1)
```

## Players

### mcts.MCTSPlayer - Monte Carlo Tree Search AI

The main AI player class that uses MCTS to select moves. Configure with the number of trials (simulations) to run and optional parameters for exploration and determinization.

```javascript
const mcts = require('mcts');
const game = require('tictactoe');

// Create MCTS player with configuration
var player = new mcts.MCTSPlayer({
    nTrials: 1000,        // Number of simulations to run
    c: 1.0,               // Exploration constant (default: 1.0)
    nTrialsPerSeed: 100,  // For nondeterministic games: trials per random seed
    rewardsFunc: function(g) {  // Custom reward function (optional)
        if (g.winner > 0) {
            var rewards = new Array(g.nPlayers).fill(0.0);
            rewards[g.winner - 1] = 1.0;
            return rewards;
        }
        return new Array(g.nPlayers).fill(0.5);  // Draw
    }
});

// Synchronous usage (for command-line)
var g = new game.Game();
var action = player.getAction(g);
console.log("Best move: " + action.toString());

// Apply the move
g.doAction(action);
```

### MCTSPlayer Asynchronous Interface

For web applications, use the asynchronous interface to avoid blocking the UI while the AI thinks. This allows displaying progress and stopping early if needed.

```javascript
const mcts = require('mcts');
const game = require('tictactoe');

var g = new game.Game();
var player = new mcts.MCTSPlayer({ nTrials: 10000 });
var maxTime = 5000;  // 5 seconds max thinking time

// Set up search callback for progress updates
player.searchCallback = function(state) {
    console.log("[" + state.root.count + " trials; " + state.time + " ms]");
    console.log("Avg search depth: " + state.avgSearchDepth.toFixed(2));
    console.log("Avg game depth: " + state.avgGameDepth.toFixed(2));

    if (state.best) {
        console.log("Current best: " + state.best.toString());
    }
};

// Start thinking
var state = player.startThinking(g);
var startTime = Date.now();

// Continue in chunks (call from timer/animation frame)
function thinkingLoop() {
    var elapsed = Date.now() - startTime;
    if (elapsed < maxTime && player.continueThinking(state, 1000)) {
        setTimeout(thinkingLoop, 0);  // Continue after yielding
    } else {
        // Done thinking - get best action
        var action = player.stopThinking(state);
        console.log("Final move: " + action.toString());
        g.doAction(action);
    }
}

thinkingLoop();
```

### mcts.RandomPlayer - Random Move Selector

A simple player that selects moves uniformly at random. Useful for testing and as a baseline opponent.

```javascript
const mcts = require('mcts');
const game = require('tictactoe');

var randomPlayer = new mcts.RandomPlayer();
var g = new game.Game();

// Get a random legal move
var action = randomPlayer.getAction(g);
console.log("Random move: " + action.toString());
```

### Custom Heuristic Players

Implement custom players by subclassing mcts.Player and implementing getAction(). This example shows a perfect Tic-Tac-Toe player using rule-based strategy.

```javascript
const mcts = require('mcts');

exports.PerfectPlayer = function() {
    mcts.Player.call(this);
};

exports.PerfectPlayer.prototype = Object.create(mcts.Player.prototype);

exports.PerfectPlayer.prototype.getAction = function(g) {
    // Priority 1: Win if possible
    var winMoves = this.findWinMoves(g, g.currentPlayer);
    if (winMoves.length > 0) {
        return new exports.Action(1 + winMoves[0]);
    }

    // Priority 2: Block opponent's win
    var blockMoves = this.findWinMoves(g, 3 - g.currentPlayer);
    if (blockMoves.length > 0) {
        return new exports.Action(1 + blockMoves[0]);
    }

    // Priority 3: Take center if available
    if (g.board[4] == 0) {
        return new exports.Action(5);
    }

    // Priority 4: Take any corner
    var corners = [0, 2, 6, 8];
    for (var c of corners) {
        if (g.board[c] == 0) return new exports.Action(1 + c);
    }

    // Fallback: Take any available cell
    var actions = g.allActions();
    return actions[0];
};

// Usage
var perfectPlayer = new exports.PerfectPlayer();
var g = new exports.Game();
var action = perfectPlayer.getAction(g);
```

## Nondeterministic Games

### Implementing Games with Chance Elements

For games with dice, card draws, or other random elements, pass `nondeterministic: true` and use `this.rng.random()` for all random decisions. MCTS will use determinization with consistent random seeds during simulations.

```javascript
const mcts = require('mcts');

exports.Game = function(o, rng) {
    if (o instanceof exports.Game) {
        // Copy game state
        mcts.Game.call(this, o, rng);
        this.track1 = o.track1.slice();
        this.track2 = o.track2.slice();
        this.roll = o.roll.slice();
        this.moves = o.moves.slice();
    } else {
        // Initialize new game with nondeterministic flag
        mcts.Game.call(this, { nondeterministic: true, nPlayers: 2 });

        // Initial board setup (Backgammon example)
        this.track1 = [0, 0,0,0,0,0,5, 0,3,0,0,0,0, 5,0,0,0,0,0, 0,0,0,0,0,2, 0];
        this.track2 = [0, 0,0,0,0,0,5, 0,3,0,0,0,0, 5,0,0,0,0,0, 0,0,0,0,0,2, 0];

        // Roll dice using seedable PRNG
        while (true) {
            this.roll = [
                Math.ceil(6 * this.rng.random()),
                Math.ceil(6 * this.rng.random())
            ];
            if (this.roll[0] != this.roll[1]) break;  // No doubles on first roll
        }
        this.moves = this.roll.slice();

        // Higher roll goes first
        this.currentPlayer = (this.roll[0] > this.roll[1]) ? 1 : 2;
    }
};

exports.Game.prototype = Object.create(mcts.Game.prototype);

// MCTS player with determinization for nondeterministic games
var player = new mcts.MCTSPlayer({
    nTrials: 5000,
    nTrialsPerSeed: 50  // Run 50 trials with same random seed before changing
});
```

## Seedable PRNG

### mcts.PRNG and mcts.PRNGSeed - Deterministic Random Numbers

JSMCTS includes a seedable xorshift128+ pseudo-random number generator for reproducible simulations in nondeterministic games.

```javascript
const mcts = require('mcts');

// Create a seed (captures random state)
var seed = new mcts.PRNGSeed();
console.log("Seed state:", seed.seed0U, seed.seed0L, seed.seed1U, seed.seed1L);

// Create PRNG with specific seed for reproducibility
var rng1 = new mcts.PRNG(seed);
var rng2 = new mcts.PRNG(seed);

// Both produce identical sequences
console.log(rng1.random());  // e.g., 0.7234...
console.log(rng2.random());  // Same: 0.7234...
console.log(rng1.random());  // e.g., 0.1892...
console.log(rng2.random());  // Same: 0.1892...

// Dice roll example
function rollDice(rng) {
    return Math.ceil(6 * rng.random());
}
console.log("Roll:", rollDice(rng1), rollDice(rng1));
```

## Running Simulations

### Command-Line Game Simulations

Run simulations from the command line to test AI players against each other or against heuristic players.

```bash
# Install dependencies
npm install optparse

# Run Tic-Tac-Toe simulation: MCTS (1000 trials) vs Perfect player
./run.sh simtictactoe.js -p mcts1000 -p perfect -n 10

# Output shows each game with move evaluations:
# run 1
# currentTurn 1 currentPlayer 1
# [1000 trials; 15 msecs]
#   1 0.51 (23/45)
#   2 0.57 (33.5/59)
# * 5 0.77 (286.5/373)   <- Best move marked with *
# ...
# draw
# draw,mcts1000,perfect
# 10,0,0
# 1.00,0.00,0.00  <- Win rates
```

```javascript
// simtictactoe.js - Simulation runner structure
const mcts = require("mcts");
const game = require("tictactoe");

var availablePlayers = {
    "random": function() { return new mcts.RandomPlayer(); },
    "mcts10": function() { return new mcts.MCTSPlayer({ nTrials: 10 }); },
    "mcts100": function() { return new mcts.MCTSPlayer({ nTrials: 100 }); },
    "mcts1000": function() { return new mcts.MCTSPlayer({ nTrials: 1000 }); },
    "mcts10000": function() { return new mcts.MCTSPlayer({ nTrials: 10000 }); },
    "perfect": function() { return new game.PerfectPlayer(); }
};

// Run a game
var g = new game.Game();
var players = [
    new mcts.MCTSPlayer({ nTrials: 1000 }),
    new game.PerfectPlayer()
];

// Enable search logging
players[0].searchCallback = mcts.searchCallback;

// Play the game
mcts.playgame(g, players);
// Output: Shows board states and moves until game over
```

## Web UI Integration

### Browser-Based Game Interface

Create interactive web games by using the asynchronous MCTS interface with DOM manipulation for the game board.

```html
<!DOCTYPE html>
<html>
<head>
    <title>Tic-Tac-Toe</title>
    <script src="js/nodehack.js"></script>
    <script src="js/mcts.js"></script>
    <script src="js/tictactoe.js"></script>
</head>
<body>
    <div id="board"></div>
    <div id="status"></div>
    <div id="searchdata"></div>
    <button id="newgame">New Game</button>

    <script>
    const mcts = require('mcts');
    const game = require('tictactoe');

    var g, player;
    var maxTrials = 1000;
    var maxTime = 2000;

    function newGame() {
        g = new game.Game();
        player = new mcts.MCTSPlayer({ nTrials: maxTrials });

        // Display search progress
        player.searchCallback = function(state) {
            var info = "[" + state.root.count + " trials]\n";
            state.root.children.forEach(function(n) {
                var marker = (n === state.best) ? "*" : " ";
                info += marker + " " + n.toString() + "\n";
            });
            document.getElementById("searchdata").innerHTML = "<pre>" + info + "</pre>";
        };

        renderBoard();
        updateStatus();
    }

    function computerMove() {
        document.getElementById("status").textContent = "Thinking...";

        var state = player.startThinking(g);
        var startTime = Date.now();

        function think() {
            if (Date.now() - startTime < maxTime && player.continueThinking(state, 500)) {
                setTimeout(think, 0);
            } else {
                var action = player.stopThinking(state);
                g.doAction(action);
                renderBoard();
                updateStatus();
            }
        }

        setTimeout(think, 0);
    }

    function humanMove(pos) {
        var actions = g.allActions();
        for (var a of actions) {
            if (a.pos === pos) {
                g.doAction(a);
                renderBoard();
                if (!g.isGameOver()) {
                    computerMove();
                } else {
                    updateStatus();
                }
                return;
            }
        }
    }

    function updateStatus() {
        if (g.isGameOver()) {
            var msg = g.winner === 0 ? "Draw!" : "Player " + g.winner + " wins!";
            document.getElementById("status").textContent = msg;
        } else {
            document.getElementById("status").textContent = "Your turn";
        }
    }

    document.getElementById("newgame").onclick = newGame;
    newGame();
    </script>
</body>
</html>
```

## Summary

JSMCTS is designed for building game-playing AIs that can run in any JavaScript environment, from web browsers to Node.js command-line applications. The primary use cases include creating browser-based games where players compete against an AI opponent, running automated simulations to compare AI strategies and tune parameters, and implementing AI for both deterministic games (Tic-Tac-Toe, Connect Four, Checkers) and nondeterministic games with chance elements (Backgammon, card games).

The library follows a clean inheritance pattern where developers extend the base Game and Action classes to define their game's rules, then use the built-in MCTSPlayer or RandomPlayer classes for AI opponents. The asynchronous thinking interface enables responsive UIs that show real-time search progress, while the synchronous interface simplifies command-line batch simulations. For games with randomness, the determinization approach using seedable PRNGs allows MCTS to effectively evaluate moves despite hidden information or chance elements. Integration is straightforward: define your game state, implement allActions() and doAction(), create an MCTSPlayer with your desired trial count, and let the UCT algorithm handle move selection.