পাঠ ২৫ · ৩২-এর মধ্যে · মডিউল ৪

Home / AI Courses / রিইনফোর্সমেন্ট লার্নিং / MCTS ও AlphaZero

MCTS ও AlphaZero — tree search + neural net

MCTS & AlphaZero: search meets deep learning

১০ মিনিট পড়া মাঝারি · Intermediate MCTS pseudocode

এক নজরে · TL;DR

MCTS চারটি ধাপে কাজ করে: selection → expansion → simulation (rollout) → backup। প্রতিটি iteration tree-এর knowledge উন্নত করে।
UCB1 / PUCT selection rule — exploration ও exploitation-এর গাণিতিক ভারসাম্য। AlphaZero-তে neural prior $P$ যোগ হয়।
AlphaGo (২০১৬): human game + self-play। AlphaZero (২০১৭): শূন্য থেকে self-play। MuZero (২০২০): rules ছাড়াই latent dynamics শিখে।
Search + Learning = চমকপ্রদ jolt — Go-তে ৪০০০ বছরের মানব চিন্তাকে ৪০ দিনে অতিক্রম।

এই পাঠে যা শিখবেন

MCTS-এর ৪টি ধাপ — selection, expansion, simulation, backup
UCB1 ও PUCT formula কীভাবে exploration/exploitation balance করে
AlphaGo → AlphaZero → MuZero — তিন প্রজন্মের architecture পার্থক্য
Self-play থেকে কীভাবে superhuman policy emerge করে

১ · কেন tree search?

Go-তে প্রতিটি move-এ ~২৫০টি বিকল্প, গড়ে ১৫০ move/গেম। মোট possible game $> 10^{170}$ — মহাবিশ্বের পরমাণুর চেয়ে বেশি। Brute-force minimax অসম্ভব। Chess-এর জন্য Deep Blue (১৯৯৭)-এ কাজ করেছিল alpha-beta pruning + heuristic। কিন্তু Go-তে heuristic বানানো প্রায় অসম্ভব ছিল — মানুষেরা "intuition" বলে ব্যাখ্যা করত।

২০০৬-এ Coulom ও Kocsis-Szepesvári MCTSMonte Carlo Tree Searchএকটি anytime tree search algorithm — প্রতিটি simulation tree-এ একটি promising path explore করে। Compute যত বেশি, ফলাফল তত ভালো। Game AI, planning, theorem proving সব জায়গায় ব্যবহৃত। প্রস্তাব করেন — heuristic-হীন, statistically-driven search। ২০১৬-তে DeepMind AlphaGo-তে এর সাথে deep neural network যোগ করে — Lee Sedol-কে ৪-১ এ হারায়।

মূল ধারণা — search + learning

Search একা: deep but slow। Learning একা: fast but shallow। দু'টোর সমন্বয় — neural network move suggest করে, search সেই suggestion-কে refine করে। AlphaZero-র শক্তি এখানেই।

২ · MCTS-এর ৪টি ধাপ

প্রতিটি simulation চারটি ধাপে চলে:

Selection: root থেকে শুরু করে leaf পর্যন্ত নামুন — প্রতিটি node-এ UCB1/PUCT rule দিয়ে best child বাছুন।
Expansion: leaf-এ পৌঁছে — যদি terminal না হয়, একটি বা সব child node তৈরি করুন।
Simulation (Rollout): নতুন node থেকে random/heuristic playout করে গেম শেষ করুন। Outcome (win/loss) পান। AlphaZero-তে rollout-এর বদলে neural value $V_\theta$ ব্যবহার।
Backup: visited path-এর প্রতিটি node-এ visit count $N$ ও total value $W$ update করুন।

৩ · UCB1 ও PUCT — selection-এর গণিত

Classical MCTS-এ UCB1 formula: $$\text{UCB}(s, a) = \underbrace{\frac{W(s,a)}{N(s,a)}}_{\text{exploitation: avg value}} + \underbrace{c\sqrt{\frac{\ln N(s)}{N(s,a)}}}_{\text{exploration: rare actions}}$$

$W$ = total accumulated reward, $N$ = visit count, $c$ = exploration constant (সাধারণত $\sqrt{2}$)। কম-visited move-এর উপর exploration bonus বড় হয়; বেশি-visited move-এ exploitation নিয়ে চলে।

AlphaZero-তে neural prior $P(s,a)$ যোগ হয় — PUCT: $$\text{PUCT}(s,a) = Q(s,a) + c_{\text{puct}} \cdot P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)}$$

$P(s,a)$ = neural net-এর policy prior — কোন move প্রাথমিকভাবে promising। Network পরামর্শ + tree statistics — দু'টো একসাথে।

ভাবুন আপনি ঢাকা শহরে নতুন রেস্টুরেন্ট খুঁজছেন। Exploitation: পরিচিত ভালো জায়গায় যান। Exploration: নতুন জায়গা try করুন। UCB1 বলে — যেখানে কম গেছেন কিন্তু rating-ও খারাপ না, সেখানে যান। PUCT-এ Google review (prior) যোগ — শুরু থেকে কোন direction দেখা উচিত তার hint।

৪ · AlphaGo → AlphaZero → MuZero progression

AlphaGo (২০১৬): দু'টি network — policy network (KGS-এর ৩০M human move দিয়ে supervised pretrain, তারপর self-play RL) ও value network। Rollout-এ fast policy + value network mix। Lee Sedol-কে হারায়।

AlphaGo Zero (২০১৭): human data ফেলে দাও। শুধু self-play, একটি unified network যা policy + value দু'টোই দেয়। ৩ দিনে original AlphaGo-কে ১০০-০ হারায়। ৪০ দিনে সব previous version পার।

AlphaZero (২০১৭): Go-specific knowledge সরাও। একই algorithm Chess + Shogi + Go-তে কাজ করে। Stockfish-কে ১০০০-গেম-এ ১৫৫ জিত, ৬ হার, বাকি draw — Stockfish ২০ বছরের engineering, AlphaZero ২৪ ঘণ্টায়।

MuZero (২০২০): game rules-ও দরকার নেই। Latent dynamics network রাখা হয় — input থেকে hidden state $h_t$ predict, action দিলে $h_{t+1}$ predict, reward + value-ও। Atari (model-free benchmark) + Go/Chess/Shogi সব জিতেছে — একই algorithm।

MCTS-এর চারটি ধাপ। প্রতিটি simulation tree-কে refine করে; AlphaZero-তে rollout-এর বদলে neural value $V_\theta$।

৫ · AlphaZero training loop

একটি unified network $f_\theta(s) \to (\mathbf{p}, v)$ — policy ও value একসাথে। Training cycle:

Self-play: বর্তমান $f_\theta$ + MCTS দিয়ে গেম খেলো। প্রতিটি position-এ MCTS-এর visit distribution $\boldsymbol{\pi}$ store।
Data: $(s_t, \boldsymbol{\pi}_t, z)$ — $z$ গেমের শেষ ফল ($+1$ জিত, $-1$ হার)।
Loss: $\mathcal{L} = (z - v)^2 - \boldsymbol{\pi}^T \log \mathbf{p} + c \|\theta\|^2$ — value MSE + policy cross-entropy + L2।
Update: gradient descent। Periodically — old vs new compare, winner হয় new champion।

৬ · MCTS Python pseudocode

Python · MCTS skeleton

import math, random
from collections import defaultdict

class Node:
    __slots__ = ("parent", "state", "children", "N", "W", "P", "to_move")
    def __init__(self, state, parent=None, prior=0.0):
        self.parent, self.state = parent, state
        self.children = {}        # action -> Node
        self.N, self.W, self.P = 0, 0.0, prior
        self.to_move = state.player

    def Q(self):
        return self.W / self.N if self.N else 0.0

C_PUCT = 1.4

def select(node):
    """Walk down the tree using PUCT."""
    while node.children:
        N_total = sum(c.N for c in node.children.values()) or 1
        node = max(
            node.children.values(),
            key=lambda c: c.Q() + C_PUCT * c.P * math.sqrt(N_total) / (1 + c.N),
        )
    return node

def expand(node, net):
    """Use neural net to get prior policy + value."""
    legal = node.state.legal_actions()
    p_logits, v = net(node.state.encode())
    probs = softmax([p_logits[a] for a in legal])
    for a, prior in zip(legal, probs):
        node.children[a] = Node(node.state.apply(a), node, prior)
    return float(v)

def backup(node, value):
    """Propagate value up the tree, flipping sign per ply."""
    while node:
        node.N += 1
        node.W += value
        value = -value
        node = node.parent

def mcts(root, net, n_sim=800):
    for _ in range(n_sim):
        leaf = select(root)
        if leaf.state.is_terminal():
            v = leaf.state.terminal_value()
        else:
            v = expand(leaf, net)
        backup(leaf, v)
    # MCTS policy = visit-count distribution
    visits = {a: c.N for a, c in root.children.items()}
    total = sum(visits.values())
    return {a: n / total for a, n in visits.items()}

def softmax(xs):
    m = max(xs); ex = [math.exp(x - m) for x in xs]; s = sum(ex)
    return [e/s for e in ex]

এটি MCTS-এর হাড়। প্রতিটি move-এ ৮০০ simulation, প্রতিটি simulation চারটি ধাপ। Production-এ — batch parallel rollout, virtual loss, Dirichlet noise on root prior (exploration), temperature scheduling।

৭ · Self-play এ Dirichlet noise — কেন?

Pure greedy MCTS — root policy prior $P$ deterministic হলে — কয়েকটি opening repeat হবে। AlphaZero প্রতিটি গেমের root-এ Dirichlet noise যোগ করে: $$P(s_0, a) = (1 - \epsilon) p_a + \epsilon \eta_a, \quad \eta \sim \text{Dir}(\alpha)$$

$\alpha$ depends on game: Go ০.০৩, Chess ০.৩, Shogi ০.১৫ — branching factor অনুযায়ী। এই noise অজানা lines explore করতে বাধ্য করে — overfit এড়ায়।

৮ · Training scale ও lessons

AlphaZero (Chess) — ~৫০০০ TPU-day, $44$ million games। MuZero — comparable। কিন্তু সেই সঙ্গে ছোট-স্কেলে recreate করা সম্ভব — minigo, OpenSpiel, Leela Zero। বাড়িতে GPU-এ ৪×৪ tic-tac-toe বা Connect-4 train কয়েক ঘণ্টা।

Search compute matters: AlphaZero-র power-law — search budget দ্বিগুণ = Elo +১০০-ই বেশি।
Self-play creates curriculum: opponent always at agent's level → smooth difficulty ramp।
Neural prior > random prior: ১০০ simulation + good prior > ১০,০০০ + uniform। AlphaGo Zero-র key insight।

MCTS শুধু perfect-information, deterministic, two-player zero-sum game-এ classic form-এ কাজ করে। Imperfect info (poker), continuous action (robotics), single-agent — সব আলাদা variants লাগে। MuZero stochastic অনেক ভালো হ্যান্ডল করে latent model দিয়ে।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ AlphaZero Stockfish-কে হারিয়েছে মাত্র ২৪ ঘণ্টায়, যেখানে Stockfish ২০ বছরের engineering। কিন্তু ২০২৪-এও দ্রুত chess engine বানাতে neural net standard হয়নি — কেন?

চমৎকার প্রশ্ন — research victory ≠ deployment dominance।

(১) Compute requirement: AlphaZero ১০০০ গেমে ১০০০+ TPU ব্যবহার করত, প্রতি move-এ ~৪০০ simulations + neural net forward। Stockfish-এর efficient alpha-beta — কয়েক million NPS (nodes/sec) সহজ CPU-তে। Phone, embedded — Stockfish ভালো।

(২) NNUE — sneaky synthesis: ২০২০ থেকে Stockfish "NNUE" (Efficiently Updatable Neural Networks) যোগ করেছে — small evaluation NN চালায় classical search-এর সাথে। আজকের Stockfish আসলে hybrid: alpha-beta + tiny NN। AlphaZero-র insight ফিরে এসেছে কিন্তু search-engineering-এ গেঁথে।

(৩) Reproducibility cost: AlphaZero বানাতে DeepMind-এর infra চাই। Open-source variants (Leela Chess Zero) আছে কিন্তু training-এ এক বছর volunteer GPU। Stockfish — clone, compile, চালাও।

(৪) Style differences: AlphaZero "human-like" intuition, positional pressure। Stockfish tactical precision। Mixed match-এ AlphaZero জেতে কিন্তু prepared opening + endgame tablebases-এ Stockfish closer। Top engine TCEC tournament-এ Lc0 (Leela) ও Stockfish nearly equal।

(৫) Game complexity scaling: Chess-এর জন্য — alpha-beta প্রায় optimal। Go-তে branching ২৫০ — alpha-beta অসহায়। Method-এর choice game-নির্ভর।

(৬) Energy efficiency: Mobile chess app — battery-conscious। NN inference ১০০× বেশি energy classical search-এর তুলনায়।

মূল উপলব্ধি: AI breakthrough mostly আসে paradigm convergence-এ — pure approach win করে rare ক্ষেত্রে। Search + neural — দু'টোই দরকার।

প্র ০২ MuZero rules ছাড়াই game শেখে — Atari-তেও কাজ করে। কীভাবে latent dynamics শেখা সম্ভব হলো? এটা কি "World Models"-এর সাথে একই?

MuZero ২০২০-এর সবচেয়ে elegant RL paper-গুলোর একটি। তিনটি network জোড়া দেওয়া:

(১) Architecture:

Representation $h_\theta$: observation → hidden state $s^0$।
Dynamics $g_\theta$: $(s^k, a^{k+1}) \to (r^{k+1}, s^{k+1})$ — abstract state-এ transition।
Prediction $f_\theta$: $s^k \to (\mathbf{p}^k, v^k)$ — policy + value।

(২) Training trick: latent state-এ কোনো reconstruction loss নেই! শুধু policy + value + reward target — actual outcomes-এর সাথে। অর্থাৎ — latent space যা চায় হোক, যতক্ষণ correct prediction দেয়।

(৩) Key insight — task-relevant abstraction: World Models (Ha) reconstructs observation — pixel exact। MuZero বলে — "যা matter করে, শুধু সেটা শিখো।" Atari-তে background pixel ignore। ফলে latent very compact, search efficient।

(৪) MCTS in latent space: Tree-এর প্রতিটি node = abstract $s^k$, real game state নয়। Search হয় learned dynamics-এ — যা actual rules-এর সাথে exact match হওয়ার প্রয়োজন নেই, শুধু "outcome consistency" রাখলেই হলো।

World Models-এর সাথে পার্থক্য:

WM: reconstruction-driven (VAE)। Observation → latent → reconstruct।
MuZero: prediction-driven। Observation → latent → predict reward/policy/value, কিন্তু observation ফেরত আসে না।
WM controller তৈরি হয় dream-এ — ছোট policy। MuZero MCTS-নির্ভর — search-এর শক্তি।
WM continuous (CarRacing)। MuZero discrete + continuous সব।

EfficientZero (২০২১): MuZero-র এক step further — sample efficiency-এ আরও — Atari-100K (এক ঘন্টা মানুষের অভিজ্ঞতা) human-level। SSL auxiliary tasks (consistency loss) যোগ করে। ছোট-data RL-এর state-of-art।

মূল উপলব্ধি: "Game-rules জানা না থাকলেও chess-Go-Atari সব নিজে শিখে" — RL-এর holy grail। MuZero সেটা practical করেছে।

প্র ০৩ Self-play কেন একটি curriculum-এর মতো কাজ করে — opponent কখনো খুব সহজ বা খুব কঠিন না? স্থিতাবস্থা কীভাবে আসে?

Self-play-র মূল আকর্ষণ — automatic difficulty adjustment।

(১) "Always at your level": Player A (current network) বনাম Player A — opponent ঠিক যেখানে আমি। Win-rate ~৫০%। শেখার ideal regime — সহজ ম্যাচ থেকে কিছুই শিখি না; অসম্ভব ম্যাচ থেকেও না। Just-out-of-reach challenge সবচেয়ে educational।

(২) Co-evolution: Network improve হলে — opponent (একই network) -ও improve। তাই challenge constant থাকে। Biological arms race-এর সাথে similarity — predator-prey।

(৩) Tabula rasa থেকে শুরু: Random network — random play। Win-rate exactly ৫০%। তারপর small advantage gain → opponent (next iteration) সেটা match করে → আরও fine signal।

(৪) Population-based variants: AlphaStar self-play নয় — League। Multiple agents (Main, Exploiter, League Exploiter) একসাথে train। কারণ pure self-play "rock-paper-scissors" cycle তৈরি করতে পারে — A beats B, B beats C, C beats A। League rotational diversity রাখে।

(৫) Stationarity issue: Self-play আসলে non-stationary opponent। Last week-এর policy-এর বিরুদ্ধে এ সপ্তাহের policy খারাপ হতে পারে। Solution: best-response training — "best historical version" রাখা archive-এ। AlphaStar এই trick ব্যবহার করত।

(৬) Equilibrium concept: Two-player zero-sum game-এ — minimax equilibrium-এ converge। Mixed strategies (poker) — Nash equilibrium। Pure self-play সবসময় Nash পৌঁছায় না, কিন্তু কাছে।

(৭) Open problems:

General-sum game (negotiation, traffic)। Self-play unclear — কোন equilibrium?
Cooperative — partner শূন্য থেকে hand-of-god convention শেখে যা মানুষের সাথে কাজ করে না (Hanabi research)।
Compute scaling — AlphaStar-এ ৪৪ দিন ১৬ TPU per agent।

মূল কথা: Self-play = automatic curriculum + reward signal generator + diversity engine। Modern RL-এর engine।

প্র ০৪ আপনি বাংলায় একটি Sixteen-soldier (ষোলগুটি / Bagh-Bandi) AI বানাচ্ছেন। AlphaZero recipe কীভাবে adapt করবেন? কী challenge?

চমৎকার applied scenario। দু'টি প্রধান বাংলা game — Bagh-Bandi (এক বাঘ vs অনেক ছাগল) ও Solah (ষোলগুটি)। দু'টোই asymmetric, regional।

Step 1 — Game formalization:

State: board position, who-to-move, captured pieces।
Action space: source square + destination + capture flag।
Terminal: একপক্ষ blocked / pieces depleted।
Reward: $+1/-1/0$।

Step 2 — Asymmetry handling: Bagh-Bandi-তে বাঘ ও ছাগলের লক্ষ্য আলাদা। Two নিউরাল head — একটি বাঘের জন্য, একটি ছাগলের জন্য — অথবা single network with player-token input।

Step 3 — Network architecture:

Board encoding: ৫×৫ grid, প্রতি cell-এ 4-channel one-hot (empty/tiger/goat/blocked)।
Conv backbone: ResNet 8 blocks, ৬৪ channels।
Two heads: policy (move logits, max ~৫০ legal) + value scalar।

Step 4 — MCTS settings:

Simulation budget: ১০০-৪০০ per move (game-specific tuning)।
Dirichlet $\alpha = 0.5$ (small branching factor)।
Temperature: প্রথম ১০ move-এ $\tau=1$, এরপর greedy।

Step 5 — Training loop: ~১০০K self-play games, single GPU-এ ১-২ সপ্তাহ। Checkpoint vs previous — Elo track।

Challenge ও সমাধান:

Asymmetric data: বাঘ rare wins early — value network biased। Solution: balance dataset, mirror augmentation।
Small branching factor: tree easily exhausted। Endgame-এ explicit lookup table।
Cultural validation: "Strong move" এর মাপকাঠি — local masters-দের সাথে প্লে। Bangladesh-এ village-level players আছেন।
Compute budget: AlphaZero-এর ১/১০০০। কিন্তু game ছোট, তাই realistic।

Bonus value-add:

Mobile app — Bengali UI, voice narration।
Move explanation: "এই গুটি কেন এখানে?" — value heatmap show।
Cultural preservation — খেলাটি কম জনপ্রিয় হচ্ছে; AI partner থাকলে নতুন প্রজন্ম শিখবে।

মূল কথা: AlphaZero-র recipe উপাদানীয় (lego brick)। Small-game adaptation কয়েক সপ্তাহের কাজ — ABCL TECH-এর মতো team-এর জন্য realistic project।

অনুশীলন

UCB1 হিসাব: root-এ ৩ child। $A: N=10, W=7$; $B: N=5, W=4$; $C: N=1, W=1$। $c=\sqrt{2}$, $N(s)=16$। কোন child select?
UCB = Q + $c\sqrt{\ln 16 / N}$, $\ln 16 \approx 2.77$।
- A: $0.7 + \sqrt{2}\sqrt{2.77/10} = 0.7 + 0.745 = 1.45$
- B: $0.8 + \sqrt{2}\sqrt{2.77/5} = 0.8 + 1.053 = 1.85$
- C: $1.0 + \sqrt{2}\sqrt{2.77/1} = 1.0 + 2.354 = 3.35$
C select — কারণ visit কম, exploration bonus বিশাল।
PUCT vs UCB1: AlphaZero PUCT-এ neural prior $P$ যোগ। $P$ uniform হলে কি UCB1-এর তুল্য? কেন বা কেন না?

না। PUCT-এ exploration term — $P\sqrt{N(s)}/(1+N(s,a))$, UCB1 — $\sqrt{\ln N(s)/N(s,a)}$। Math আলাদা: PUCT $\sqrt{N}$, UCB1 $\sqrt{\ln N}$ — PUCT exploration বেশি push করে। তাছাড়া $1+N$ denominator-এ — first visit-এ PUCT-এ infinite নয়, UCB1-এ undefined।
Rollout vs neural value: Classical MCTS-এ random rollout, AlphaZero-এ neural $v$। Neural value কেন এত বড় উন্নতি?

Random rollout high variance — Go-তে ১৫০ random move কোনো meaningful signal দেয় না। Neural $v$ trained — single shot-এ accurate estimate। Variance ১০-১০০× কম, ফলে fewer simulations দরকার একই accuracy পেতে। AlphaGo Zero rollout পুরোপুরি ছেড়ে দিয়েছে।