Monte Carlo Tree Search Is Awesome

Monte Carlo Tree Search (MCTS) is a game-tree search method that picks moves by running many simulated playthroughs from a position - mostly random playouts - and using the outcomes to guide which branches to explore. It only requires the rules and a win condition, so it sidesteps the need for handcrafted evaluation functions that depth-limited minimax searches rely on. This makes it powerful for games with enormous trees or hard-to-evaluate positions: small games like tic‑tac‑toe can be solved exhaustively, but chess, Go, Ultimate Tic‑Tac‑Toe and Hex explode combinatorially, so selective search is necessary. MCTS has powered major advances (beating expert Go programs in the 2000s and forming the backbone of AlphaGo/AlphaZero) and is highly customizable for different settings.

The practical core improvement over naive random playouts is to treat move selection as a multi-armed bandit problem and bias simulations toward promising but underexplored moves. Upper Confidence Bound (UCB) scoring - Q_j + C * sqrt(ln N / n_j), where Q_j is average reward, n_j the visits, N total visits and C tunes exploration - balances exploitation and exploration. UCT (the tree-search use of UCB) remembers results between simulations and concentrates effort on moves that both look good and remain uncertain, avoiding flat Monte Carlo’s equal allocation and forgetfulness. That balance, tunable by C, is why MCTS performs well where evaluations are difficult or expensive.