Monte Carlo Tree Search (MCTS) - Entrenar - Training & Optimization Library
Description: A comprehensive guide to building neural network training systems with autograd, optimizers, LoRA/QLoRA, and quantization using EXTREME TDD methodology

# Monte Carlo Tree Search (MCTS)

MCTS is a best-first search algorithm that uses random simulations to evaluate positions.

## Algorithm Overview

MCTS proceeds in four phases:

1. Selection: Traverse tree using UCB1/PUCT to select promising nodes
2. Expansion: Add new child nodes for unexplored actions
3. Simulation: Random rollout to terminal state
4. Backpropagation: Update statistics along the path

## Core Types

    #![allow(unused)]
    fn main() {
    use entrenar::search::{
        State, Action, StateSpace, ActionSpace,
        MctsSearch, MctsConfig, SearchTree,
    };

    // Define your state and action types
    struct CodeState { /* partial AST */ }
    struct CodeAction { /* transformation rule */ }

    // Implement required traits
    impl State for CodeState {
        fn is_terminal(&self) -> bool { /* check if complete */ }
    }

    impl Action for CodeAction {
        fn apply(&self, state: &CodeState) -> CodeState { /* apply transform */ }
    }
    }

## Configuration

    #![allow(unused)]
    fn main() {
    let config = MctsConfig {
        exploration_constant: 1.414,  // UCB1 exploration term
        max_iterations: 1000,         // Search budget
        max_depth: 50,                // Maximum tree depth
        use_puct: true,               // Use PUCT instead of UCB1
        seed: Some(42),               // Reproducible search
    };
    }

## Selection Policies

### UCB1 (Upper Confidence Bound)

    UCB1(n) = Q(n) / N(n) + c * sqrt(ln(N_parent) / N(n))

- `Q(n)`: Total reward through node
- `N(n)`: Visit count
- `c`: Exploration constant

### PUCT (Predictor + UCT)

    PUCT(n) = Q(n) / N(n) + c * P(n) * sqrt(N_parent) / (1 + N(n))

- `P(n)`: Prior probability from policy network