# Lab 10: the wider RL landscape

Two short labs that go with Chapter 10 (`/rl/learn/10-landscape/`). numpy and the
standard library only; everything runs in seconds.

1. **Monte Carlo tree search (UCT) for tic-tac-toe** (`mcts.py`, Tasks 1–4).
   The game logic is in `tictactoe.py` (complete). You write the four phases of
   a simulation and check that the result never loses to a random player and
   solves three puzzles.
2. **The KL-regularized optimum** (`gibbs.py`, Task 5). You compute
   π*(a) ∝ π0(a)·exp(r(a)/β) and the objective J(π) = E_π[r] − β·KL(π‖π0),
   and the tests verify numerically that nothing beats π* (the Gibbs
   variational principle, which Chapters 11 and 13 build on).

## How to run

```bash
cd 10-landscape
python -m pytest -q                    # your code: fails until you fill in the TODOs
python -m pytest -q test_mcts.py -k uct   # just one task's tests
RL_SOLUTIONS=1 python -m pytest -q     # reference solutions: all 28 pass
python run.py                          # plots -> landscape.png (about 5-30 s)
```

## Tasks, in order

**Cell numbering.** The lab numbers cells 0–8 (row-major, as in `tictactoe.py`);
the chapter's interactive demo labels them 1–9. So the lab's cell 8 is the
demo's cell 9.

**The value convention (read this first).** Each `Node` stores `N` (visits)
and `W` (total result) *from the point of view of the player who made the move
into that node* (`node.player_just_moved`). Then, when a parent chooses among
its children, a child's `W / N` is directly "how good has this move been for
me, the chooser". Results of finished games are always from X's point of view
(+1 X wins, −1 O wins, 0 draw), so in the backup you multiply by
`player_just_moved` to flip the sign for O.

| Task | File | Function | What it is |
|---|---|---|---|
| 1 | `mcts.py` | `uct_score` | Q + c·sqrt(ln N_parent / N); +∞ if unvisited |
| 2 | `mcts.py` | `rollout` | random play to the end; return the result |
| 3 | `mcts.py` | `backup` | N += 1, W += result × player_just_moved along the path |
| 4 | `mcts.py` | `run_simulation` | selection → expansion → rollout → backup |
| 5a | `gibbs.py` | `gibbs_policy` | π0·exp(r/β)/Z, computed stably in log space |
| 5b | `gibbs.py` | `kl_objective` | E_π[r] − β·KL(π‖π0), with 0·log 0 = 0 |

`search`, `best_move` and `mcts_player` in `mcts.py` are provided: they call
your `run_simulation`.

## What you should see

- `pytest`: 28 tests pass. The MCTS tests take about a second.
- `run.py` saves `landscape.png` with three panels:
  1. **MCTS vs a random player.** With 1 simulation per move MCTS is basically
     random and loses a lot; by ~30 simulations it almost never loses.
  2. **The fork trap.** In the position `X . . / . O . / . . X` with O to move,
     only an edge move (1, 3, 5, 7) is safe. MCTS finds this reliably once it
     has a few hundred simulations. *Flat* Monte Carlo (random rollouts from
     each move, no tree) gets **worse** with more rollouts and mostly picks a
     losing corner. Random rollouts assume a random opponent, and a random X
     rarely finds the fork; the tree is what lets MCTS model an opponent who
     plays well. Chapter 10 discusses why.
  3. **The KL-regularized optimum vs β.** As β → 0, E[r] approaches the best
     reward (1.0) and KL approaches −log π0(best) = −log 0.03 ≈ 3.5; as β grows,
     π* returns to π0 (KL → 0, E[r] → E_π0[r] = 0.333). The grey dotted line
     marks the best reward (1.0), the grey dashed line E_π0[r]. J(π*) = β log Z
     always lies below E[r] (the gap is β·KL).

## Going further (optional)

- Replace random rollouts with a smarter rollout policy ("win if you can, block
  if you must, else random") and measure how many fewer simulations the fork
  trap needs. This is a hand-written version of what AlphaGo's rollout policy
  network and AlphaZero's value network do.
- Add a prior to selection (PUCT, the AlphaZero rule
  Q + c·P(a)·sqrt(N_parent)/(1 + N)) with P uniform, then with P from
  `optimal_moves`, and compare.
- Reuse the subtree between moves instead of starting a fresh search.