How MicroStar works — a pure-Python AlphaGo Zero

MicroStar is the learning stack behind policies V5–V7 (the alphastar package, lesson_7/policies/alphastar/). It is a complete, miniature AlphaGo Zero written in dependency-free pure Python — no NumPy, no PyTorch — in the spirit of Karpathy's micrograd. The only non-Python piece is the game itself: star_engine, the Rust Star Realms engine, which supplies legal_actions(), step(), observe() and clone().

Every code block on this page is the actual source, not pseudocode.

The map: which part is what

File	What it is	The famous algorithm inside
`features.py`	Board → feature vector; actions → fixed policy slots	(translation layer)
`nn.py`	Scalar autograd, the policy/value network, Adam	Gradient descent — `Value.backward()` computes the gradients (backpropagation), `Adam.step()` takes the descent step
`mcts.py`	The search tree over the game's forward model	MCTS — PUCT selection, network-guided expansion, value backup
`train.py`	The self-play outer loop and the loss function	Where the two meet: MCTS makes the training targets, gradient descent fits the net to them
`policy.py`	The tournament-facing wrapper	Play the most-visited move of a noise-free search

The AlphaGo Zero loop in one sentence: search (MCTS, sharpened by the current network) produces move targets and game outcomes; gradient descent nudges the network toward those targets; the better network makes the next round of search stronger — a virtuous cycle with no human examples anywhere.

1. `features.py` — translating the game for the network

A neural network eats fixed-length vectors; a card game is bags of cards. This module does two translations. First, featurize turns the engine's raw observation (604 integers, already expressed from the point of view of the player to move) into a compact, sparse feature vector — lists of (index, value) pairs, zeros omitted, because a hand of cards is mostly zeros:

def featurize(obs):
    """Sparse feature vector as a list of (index, value) pairs (zeros omitted)."""
    feats = []

    def add_block(out_base, *in_bases):
        for c in range(NCARDS):
            total = 0
            for b in in_bases:
                total += obs[b + c]
            if total:
                feats.append((out_base + c, total * _CARD_SCALE))

    add_block(F_ME_OWNED, _ME_HAND, _ME_DECK, _ME_DISCARD, _ME_SHIPS)
    add_block(F_ME_BASES, _ME_BASES)
    add_block(F_THEM_OWNED, _THEM_HAND, _THEM_DECK, _THEM_DISCARD, _THEM_SHIPS)
    add_block(F_THEM_BASES, _THEM_BASES)
    add_block(F_TRADE_ROW, _TRADE_ROW)

    # Normalized scalars. Authority is the headline signal (training plays at 10).
    s = F_SCALARS
    my_auth = obs[_S_MY_AUTH]
    their_auth = obs[_S_THEIR_AUTH]
    scal = [
        (s + 0, my_auth / 10.0),
        (s + 1, their_auth / 10.0),
        (s + 2, (my_auth - their_auth) / 10.0),  # authority swing -> who's winning
        (s + 3, obs[_S_MY_TRADE] / 8.0),
        (s + 4, obs[_S_MY_COMBAT] / 8.0),
        (s + 5, obs[_S_TURN] / 50.0),
        (s + 6, obs[_S_EXPLORER] / 10.0),
        (s + 7, 1.0),  # bias-ish constant feature (always on)
    ]
    for idx, val in scal:
        if val:
            feats.append((idx, val))
    return feats

Second, action_slot maps every legal action onto a slot in a fixed policy vector. AlphaGo Zero's network emits one logit per action in a fixed action space and then masks to what is legal; Star Realms' legal set is variable, so each action is keyed by (action-kind, card-index) — e.g. "buy Battle Pod" is always the same slot, whichever turn it appears on:

def action_slot(action) -> int:
    """Fixed policy-vector slot for a LegalAction."""
    base = _KIND_BASE[action.kind]
    if action.kind in _SINGLETON_SET:
        return base
    ci = _NAME_TO_INDEX.get(action.name, 0)
    return base + ci

2. `nn.py` — the network, and gradient descent

This module is where gradient descent lives. It has three parts: an autograd engine that computes gradients, the network itself, and the Adam optimizer that uses the gradients to update the weights.

2a. The autograd engine (the "gradient" in gradient descent)

Everything is built from one class: Value, a single scalar in a computation graph. Every arithmetic operation records its inputs (children) and the local derivative of the output with respect to each input. Two examples — addition (local derivatives 1, 1) and multiplication (each input's derivative is the other input):

class Value:
    """A single scalar in the computation graph. Stores its value (`data`), the
    accumulated gradient of the loss w.r.t. it (`grad`), and -- for the backward
    pass -- its children and the local derivatives of this node w.r.t. each."""

    __slots__ = ("data", "grad", "_children", "_local_grads")

    def __init__(self, data, children=(), local_grads=()):
        self.data = data
        self.grad = 0.0
        self._children = children
        self._local_grads = local_grads

    def __add__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        return Value(self.data + other.data, (self, other), (1.0, 1.0))

    def __mul__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        return Value(self.data * other.data, (self, other), (other.data, self.data))

backward() is reverse-mode automatic differentiation — backpropagation — in eleven lines. It topologically sorts the graph, seeds the output's gradient at 1, and pushes gradients backward through every node with the chain rule (child.grad += local_derivative * parent.grad):

    def backward(self):
        """Reverse-mode autodiff: topologically order the graph, then push grads
        from this node (seeded at 1) back to every ancestor via the chain rule."""
        topo = []
        visited = set()

        def build(v):
            if id(v) not in visited:
                visited.add(id(v))
                for child in v._children:
                    build(child)
                topo.append(v)

        build(self)
        self.grad = 1.0
        for v in reversed(topo):
            for child, local in zip(v._children, v._local_grads):
                child.grad += local * v.grad

After loss.backward() runs, every weight in the network knows ∂loss/∂weight — the direction to move in.

2b. The network: f_θ(s) = (p, v)

The network is AlphaGo Zero's in miniature: one shared hidden layer (the trunk), then two heads — a policy head (a logit per action slot) and a value head (one number in [−1, 1]: how good this position is for the player to move).

class PolicyValueNet:
    """f_theta(s) = (policy_logits[A], value in [-1, 1]).

    Architecture (deliberately tiny so pure-Python self-play is tractable):
        x -> Linear(F, H) -> ReLU -> [ trunk h ]
        h -> Linear(H, A)            (policy logits)
        h -> Linear(H, 1) -> tanh    (value)

    `hidden` may be an int (one hidden layer) -- kept minimal on purpose.
    """

The one idea that makes pure-Python AlphaZero tractable at all is separating inference from training. MCTS evaluates the network hundreds of times per move but never needs gradients, so forward_infer works on plain floats and builds no graph:

    # --- fast inference path: plain floats, NO graph -----------------------
    def forward_infer(self, x, policy_idxs):
        """Return (logits_for_policy_idxs: list[float], value: float). Only the
        requested policy slots are computed -- legal actions are <=10, so this is
        cheap no matter how large the full action space is. No autograd graph.
        `x` is a list of (feature_index, value) sparse pairs."""
        H = self.hidden
        # Trunk: h = relu(W1 x + b1). Features are sparse (mostly-zero card
        # counts), so we iterate only the nonzero entries.
        h = [0.0] * H
        b1 = self.b1
        w1 = self.w1
        for o in range(H):
            row = w1[o]
            acc = b1[o].data
            for i, xi in x:
                acc += row[i].data * xi
            h[o] = acc if acc > 0.0 else 0.0
        # Only the requested policy logits.
        wp, bp = self.wp, self.bp
        logits = []
        for o in policy_idxs:
            row = wp[o]
            acc = bp[o].data
            for j in range(H):
                acc += row[j].data * h[j]
            logits.append(acc)
        # Value.
        accv = self.bv[0].data
        wv0 = self.wv[0]
        for j in range(H):
            accv += wv0[j].data * h[j]
        return logits, math.tanh(accv)

Training needs gradients, but only over a small minibatch, so forward_train is the same arithmetic done in Value objects — building the graph that backward() will walk:

    # --- training path: builds the autograd graph -------------------------
    def forward_train(self, x, policy_idxs):
        """Return (logits_for_policy_idxs: list[Value], value: Value) with a full
        autograd graph. Only the requested policy slots are built (we only need
        the legal ones for the cross-entropy). `x` is sparse (idx, val) pairs."""
        H = self.hidden
        h = []
        for o in range(H):
            row = self.w1[o]
            acc = self.b1[o]
            for i, xi in x:
                acc = acc + row[i] * xi
            h.append(acc.relu())
        logits = []
        for o in policy_idxs:
            row = self.wp[o]
            acc = self.bp[o]
            for j in range(H):
                acc = acc + row[j] * h[j]
            logits.append(acc)
        accv = self.bv[0]
        wv0 = self.wv[0]
        for j in range(H):
            accv = accv + wv0[j] * h[j]
        value = accv.tanh()
        return logits, value

Both paths read the same Value objects' .data, so the instant the optimizer updates a weight, inference sees it — a single source of truth.

2c. Adam (the "descent" in gradient descent)

Given the gradients, Adam.step() is the actual parameter update — the line p.data -= lr * m_hat / (sqrt(v_hat) + eps) is gradient descent, dressed up with Adam's per-parameter momentum (m) and scale (v) estimates:

class Adam:
    def __init__(self, params, lr=0.01, beta1=0.9, beta2=0.999, eps=1e-8, weight_decay=1e-4):
        self.params = params
        self.lr = lr
        self.beta1 = beta1
        self.beta2 = beta2
        self.eps = eps
        self.weight_decay = weight_decay
        self.m = [0.0] * len(params)
        self.v = [0.0] * len(params)
        self.t = 0

    def zero_grad(self):
        for p in self.params:
            p.grad = 0.0

    def step(self):
        self.t += 1
        b1, b2 = self.beta1, self.beta2
        for i, p in enumerate(self.params):
            g = p.grad + self.weight_decay * p.data  # decoupled-ish L2
            self.m[i] = b1 * self.m[i] + (1 - b1) * g
            self.v[i] = b2 * self.v[i] + (1 - b2) * g * g
            m_hat = self.m[i] / (1 - b1 ** self.t)
            v_hat = self.v[i] / (1 - b2 ** self.t)
            p.data -= self.lr * m_hat / (math.sqrt(v_hat) + self.eps)

3. `mcts.py` — the search (this is the MCTS)

This whole module is the Monte-Carlo tree search. Each decision runs n_sims simulations from the current position. One simulation does three things: select a path down the tree, expand one new leaf with the network, and back up the leaf's value along the path. After all simulations, the root's visit counts — not the raw network output — decide the move and become the training target.

A node stores, per legal action, the classic AlphaGo Zero statistics: prior P (from the policy head), visit count N, total value W, and mean value Q = W/N.

3a. Selection — the PUCT rule

Descending the tree, each step picks the action maximizing Q(s,a) + c_puct · P(s,a) · √ΣN / (1 + N(s,a)) — exploitation (Q, "this has been good") plus exploration (P-weighted, "the network likes this and we haven't tried it much"):

    # --- PUCT selection ---------------------------------------------------
    def _select(self, node: _Node) -> int:
        c = self.c_puct
        sqrt_total = math.sqrt(node.sum_N) if node.sum_N > 0 else 0.0
        best, best_a = -1e30, 0
        P, Q, N = node.P, node.Q, node.N
        for a in range(len(node.legal)):
            u = Q[a] + c * P[a] * sqrt_total / (1 + N[a])
            if u > best:
                best, best_a = u, a
        return best_a

3b. Expansion — the network evaluates the leaf

Where classic MCTS would run a random rollout to the end of the game, AlphaGo Zero asks the network instead: the policy head supplies the child priors P, and the value head supplies the leaf value v that will be backed up. This is the inference path (forward_infer) — called hundreds of times per move, never needing gradients:

    # --- network evaluation + node expansion ------------------------------
    def _expand(self, node: _Node) -> float:
        """Evaluate the network at `node`, install priors, and return the leaf
        value v (from `node.player`'s perspective)."""
        game = node.game
        legal = game.legal_actions()
        node.legal = legal
        node.slots = [action_slot(a) for a in legal]

        x = featurize(game.observe())
        # Compute one logit per UNIQUE legal slot, then map back per action so
        # colliding actions share a logit (=> they split the prior in softmax).
        uniq = list(dict.fromkeys(node.slots))
        logit_list, v = self.net.forward_infer(x, uniq)
        logit_of = {s: l for s, l in zip(uniq, logit_list)}
        action_logits = [logit_of[s] for s in node.slots]
        node.P = softmax_floats(action_logits)

        n = len(legal)
        node.N = [0] * n
        node.W = [0.0] * n
        node.Q = [0.0] * n
        node.children = [None] * n
        node.sum_N = 0
        node.expanded = True
        return v

3c. Simulation and backup — with a Star Realms twist

One simulation is a recursive descent: terminal nodes return their known value, unexpanded nodes get expanded (returning the network's value), and otherwise we select an action, recurse into the child, and back the child's value up into this node's N/W/Q statistics.

The twist: in Go or chess every move alternates players, so backup negates the value at every ply. In Star Realms most actions keep the same player to move — playing a card, buying, attacking are all "my" moves; only End Turn hands over control. So the sign flips only when the player-to-move actually changes between parent and child:

    # --- one simulation ---------------------------------------------------
    def _simulate(self, node: _Node) -> float:
        """Return the value of `node` from `node.player`'s perspective."""
        if node.terminal:
            return node.terminal_value
        if not node.expanded:
            return self._expand(node)
        a = self._select(node)
        child = self._child(node, a)
        v_child = self._simulate(child)
        v = v_child if child.player == node.player else -v_child
        node.N[a] += 1
        node.W[a] += v
        node.Q[a] = node.W[a] / node.N[a]
        node.sum_N += 1
        return v

Stepping an action samples card draws from the engine RNG, so the same action could lead to different children. MicroStar keeps the first sampled child per edge ("sticky first sample") to preserve the clean AlphaGo Zero tree shape:

    def _child(self, node: _Node, a: int) -> _Node:
        """Sticky child for action index `a`: clone + step on first visit, then
        reuse. Detects terminal and perspective flips."""
        if node.children[a] is not None:
            return node.children[a]
        cg = node.game.clone()
        res = cg.step(node.legal[a].index)
        if res.done:
            # `node.player` just moved; reward 1 => that player won.
            tv = 1.0 if res.reward == 1 else -1.0
            child = _Node(cg, node.player, terminal=True, terminal_value=tv)
        else:
            child = _Node(cg, res.turn_count % 2)
        node.children[a] = child
        return child

3d. The search entry point, and root noise

search clones the game (the real game is never mutated), expands the root, optionally mixes Dirichlet noise into the root priors (self-play only — it forces the search to try moves the network would dismiss, which is where new knowledge comes from), then runs the simulations and reports the visit counts:

    # --- public search ----------------------------------------------------
    def search(self, game, rng: random.Random, add_root_noise=True):
        """Run the search from `game` (not mutated). Returns a dict with:
            legal   : list[LegalAction] at the root (order == real game's)
            visits  : per-action visit counts (the basis of pi)
            slots   : per-action policy slot
            x       : root feature vector (sparse)
            player  : root player-to-move parity
        """
        root = _Node(game.clone(), game.turn_count % 2)
        self._expand(root)

        if add_root_noise and len(root.legal) > 1:
            self._add_dirichlet(root, rng)

        for _ in range(self.n_sims):
            self._simulate(root)

        return {
            "legal": root.legal,
            "visits": list(root.N),
            "slots": list(root.slots),
            "x": featurize(game.observe()),
            "player": root.player,
        }

Finally, visit counts become a move-selection distribution π(a) ∝ N(a)^1/τ — temperature τ=1 early in self-play games (explore), τ→0 (just play the most-visited move) everywhere else:

def visits_to_policy(visits, temperature):
    """Move-selection distribution pi(a) ~ N(a)^(1/tau). tau->0 means argmax
    (ties split). Returns a probability list aligned to `visits`."""
    if temperature <= 1e-6:
        m = max(visits)
        winners = [1.0 if v == m else 0.0 for v in visits]
        s = sum(winners)
        return [w / s for w in winners]
    powered = [v ** (1.0 / temperature) for v in visits]
    s = sum(powered)
    if s <= 0:  # no visits at all (shouldn't happen): fall back to uniform
        n = len(visits)
        return [1.0 / n] * n
    return [p / s for p in powered]

4. `train.py` — self-play, where search and gradient descent meet

The outer loop alternates two phases forever: play one self-play game (both seats driven by MCTS with the current network), then take a few gradient steps on minibatches sampled from a replay buffer of stored positions.

4a. Generating data: one self-play game

At every move, run the search, store (features, search policy) as a training example, then sample the move from the visit counts. When the game ends, go back and stamp every stored position with the outcome z:

    # --- self-play --------------------------------------------------------
    def self_play_game(self) -> None:
        cfg = self.cfg
        # Deterministic but distinct engine seed per game.
        g = se.Game(self.rng.randint(0, 2**63 - 1), starting_authority=cfg.starting_authority)
        samples: list[Sample] = []
        ply = 0
        winner_parity = None
        while not g.done and ply < cfg.max_moves:
            out = self.selfplay_mcts.search(g, self.rng, add_root_noise=True)
            visits = out["visits"]
            # Training target: slot-aggregated normalized visit counts.
            uniq, probs = slot_policy_target(out["slots"], visits)
            samples.append(Sample(out["x"], uniq, probs, out["player"]))
            # Move selection: tau=1 early (explore), then greedy.
            temp = 1.0 if ply < cfg.temp_moves else 0.0
            move_pi = visits_to_policy(visits, temp)
            a = self.rng.choices(range(len(move_pi)), weights=move_pi)[0]
            mover = g.turn_count % 2
            legal = g.legal_actions()
            res = g.step(legal[a].index)
            ply += 1
            if res.done:
                winner_parity = mover if res.reward == 1 else (1 - mover)
        if winner_parity is None:  # hit move cap without terminating: skip
            return
        # Outcome target z. With value_discount gamma < 1, a state's target is
        # gamma**(plies-until-game-end) * (+/-1): the final decisive move keeps
        # full credit while earlier moves are discounted, so lines that win in
        # FEWER moves are valued more highly -- exactly the aggressive, fast-kill
        # play the authority-10 regime rewards.
        gamma = self.cfg.value_discount
        T = len(samples)
        for i, s in enumerate(samples):
            base = 1.0 if s.player == winner_parity else -1.0
            s.z = base * (gamma ** (T - 1 - i)) if gamma != 1.0 else base
            self.buffer.append(s)
        self.games_played += 1

The gamma block at the end is the V6/V7 refinement: pure AlphaGo Zero (gamma = 1.0, the V5 setting) gives every position of a won game the same z = +1; with gamma < 1 earlier positions of long games get less credit, so the value head learns to prefer fast wins.

4b. Fitting the network: the gradient descent step

This is the heart of the training side. For each sample in the minibatch we run the graph-building forward pass and assemble AlphaGo Zero's loss — a value loss (z − v)² pushing the value head toward the actual outcome, plus a policy loss, the cross-entropy pushing the policy head toward the search's visit distribution. Then the three-step incantation of every deep learning framework, except here every step is code you can read above: total.backward() (compute all gradients through the graph) and self.opt.step() (move every weight downhill):

    # --- gradient training ------------------------------------------------
    def train_step(self) -> tuple[float, float]:
        cfg = self.cfg
        if len(self.buffer) < cfg.minibatch:
            return self.last_loss
        batch = [self.buffer[self.rng.randrange(len(self.buffer))] for _ in range(cfg.minibatch)]
        self.opt.zero_grad()
        total = None
        vloss_acc = 0.0
        ploss_acc = 0.0
        for s in batch:
            logits, v = self.net.forward_train(s.x, s.slots)
            # Value loss: (z - v)^2.
            vloss = (s.z - v) ** 2
            # Policy loss: cross-entropy of target over the legal slots.
            # softmax over the slot logits, then -sum target * log(p).
            maxl = max(l.data for l in logits)
            exps = [(l - maxl).exp() for l in logits]
            denom = exps[0]
            for e in exps[1:]:
                denom = denom + e
            ploss = None
            for p_target, e in zip(s.probs, exps):
                if p_target <= 0.0:
                    continue
                logp = (e / denom).log()
                term = (-p_target) * logp
                ploss = term if ploss is None else ploss + term
            sample_loss = vloss if ploss is None else vloss + ploss
            total = sample_loss if total is None else total + sample_loss
            vloss_acc += vloss.data
            ploss_acc += (ploss.data if ploss is not None else 0.0)
        total = total * (1.0 / len(batch))
        total.backward()
        self.opt.step()
        n = len(batch)
        self.last_loss = (vloss_acc / n, ploss_acc / n)
        return self.last_loss

4c. The driver

The whole AlphaGo Zero algorithm is then four lines of control flow — a game, then a few gradient steps, forever:

    # --- driver -----------------------------------------------------------
    def run_games(self, n: int, *, print_loss_every: int = 0) -> None:
        """Play `n` self-play games, interleaving gradient steps."""
        for _ in range(n):
            self.self_play_game()
            if self.games_played > self.cfg.warmup_games:
                for _ in range(self.cfg.train_steps_per_game):
                    vl, pl = self.train_step()

All hyperparameters live in one Config object, so a policy version (V5, V6, V7) is nothing but a Config pin — see the policy pages for the exact settings.

5. `policy.py` — playing a tournament move

At play time there is no noise and no temperature: run a search, play the most-visited action. The search budget (eval_sims) is independent of the self-play budget — V7's headline trick is simply turning this knob up to 128:

    def get_action_probabilities(
        self, game: se.Game, actions: Actions, rng: Random
    ) -> list[float]:
        """Visit-count distribution from a noise-free search, aligned to
        `actions`. Doubles as the AlphaZero policy output."""
        out = self.mcts.search(game, rng, add_root_noise=False)
        visits = out["visits"]
        total = sum(visits)
        if total == 0:  # degenerate (1 sim / forced): uniform
            n = len(actions)
            return [1.0 / n] * n
        return [v / total for v in visits]

    def get_action(self, game: se.Game, actions: Actions, rng: Random) -> se.LegalAction:
        """Play the most-visited action (greedy, tau->0). Ties broken by `rng`."""
        probs = self.get_action_probabilities(game, actions, rng)
        best = max(probs)
        winners = [i for i, p in enumerate(probs) if p >= best - 1e-12]
        return actions[rng.choice(winners)]

Recap: so which part is which?

Gradient descent is the training path:

Trainer.train_step (train.py) assembles the loss (z − v)² − Σ π(a) log p(a) over a minibatch;
Value.backward (nn.py) backpropagates it — reverse-mode autodiff computes ∂loss/∂θ for every weight;
Adam.step (nn.py) performs the descent: p.data -= lr * m_hat / (sqrt(v_hat) + eps).

MCTS is everything in mcts.py:

MCTS._select — the PUCT rule chooses which branch to explore;
MCTS._expand — the network (via the gradient-free forward_infer) supplies priors and a leaf value instead of a random rollout;
MCTS._simulate — recursion plus the N/W/Q backup (negating the value only when the player to move actually flips — the Star Realms twist);
MCTS.search / visits_to_policy — visit counts become both the move and the next training target.

And the reason it works is the loop between them: MCTS is a policy improvement operator (search output beats the raw network), gradient descent distills that improvement back into the network, and the improved network makes the next search stronger. That loop, run for thousands of self-play games, is what turns 900 lines of pure Python from random flailing into the policy that tops the leaderboard.

← Policies · Home