# AI 꾸러미 — 몬테카를로 트리 탐색 (UCT) — Monte Carlo tree search (MCTS)
> 고르기 → 펼치기 → 끝까지 아무렇게나 둬 보기 → 결과 올리기를 수백 번 되풀이해, 평가 함수 없이도 많이 이긴 가지를 찾고 방문 수로 수를 고른다.  
> 견본: https://ai-techstudio.web.app/#t/i347

이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요.

## 주문서

### 만들어 줘: 몬테카를로 트리 탐색 (UCT) — Monte Carlo tree search (MCTS)

#### 1. 목표
틱택토 · 헥스 · 하바나의 AI 를 몬테카를로 트리 탐색(UCT)으로 만들어 줘 — 평가 함수 없이. 분위기는 많이 이긴 가지가 굵게 자라는 설명.

#### 2. 핵심 기술 용어
- **Monte Carlo tree search (MCTS)** — 무작위로 끝까지 둬 본 결과로 자라는 탐색 나무
- **UCT (UCB1 for trees)** — 승률 + C × √(ln 부모 방문 / 내 방문) 가 큰 자식 고르기
- **Selection · expansion · simulation · backpropagation** — 고르기 · 펼치기 · 끝까지 두기 · 결과 올리기
- **Exploration constant C** — 클수록 덜 가 본 가지도 넓게 본다

#### 3. 환경
- 플랫폼: TypeScript (브라우저), 라이브러리 없이 — 화면과 떨어진 순수 함수로
- 화면: 브라우저 — PC · 폰 모두

#### 4. 조건
- W 는 「그 마디로 수를 둔 사람」 기준으로 올린다 (차례마다 관점이 바뀐다)
- 마지막 선택은 승률이 아니라 방문 수 N 이 가장 큰 수
- 반복은 횟수가 아니라 시간 예산으로 끊을 수 있게
- 탐험 상수 C 슬라이더(0.2~3) · 반복 수 표시 · 칸마다 방문 수
- 난수는 시드를 줄 수 있게 (시험 재현)

#### 5. 완성 기준 (이게 보이면 성공)
- 반복이 쌓일수록 좋은 수 쪽 가지가 굵고 깊게 자라고, 그 칸 방문 수가 가장 커진다
- C 를 크게 하면 나무가 넓게, 작게 하면 좁고 깊게 자란다
- 틱택토에서 700번 반복한 AI 가 지지 않는다

#### 6. 진행 방식
- 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘.
- 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘.
- 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘.
- 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘.
- 답변과 코드 주석은 한국어로 해 줘.

## 원리
- ① 고르기: 뿌리에서 「다 펼친 마디」를 따라 UCT 값 = W/N + C·√(ln N부모 / N) 가 가장 큰 자식으로 내려간다 (견본 C = 1.2).
- ② 펼치기: 아직 안 둬 본 수가 있는 마디에서 그 수 하나로 새 자식을 만든다.
- ③ 끝까지 아무렇게나: 새 마디 판에서 무작위로 끝까지 둬 승 · 무 · 패를 얻는다 (평가 함수가 필요 없다).
- ④ 올리기: 지나온 길의 마디마다 N + 1, 그 마디로 둔 사람이 이겼으면 W + 1 (무승부 0.5).
- 다 돌면 뿌리 자식 중 방문 수 N 이 가장 큰 수를 둔다 — 견본은 700번 반복하며 칸마다 방문 수를 보여 준다.

## 핵심 코드 — UCT 한 번 — 고르기 · 펼치기 · 끝까지 · 올리기
(발췌: demos/demosGameAI.ts I347 의 iterate() 를 정리)
```ts
interface MC { b: number[]; mover: number; move: number; kids: MC[]; untried: number[]; N: number; W: number }
let Cexp = 1.2;

function iterate(root: MC): void {
  let n = root;
  const path: MC[] = [root];
  // ① 고르기: 다 펼친 마디는 UCT 가 큰 자식으로
  while (!n.untried.length && n.kids.length) {
    let best = n.kids[0]!, bv = -Infinity;
    for (const k of n.kids) {
      const v = k.W / k.N + Cexp * Math.sqrt(Math.log(n.N) / k.N);
      if (v > bv) { bv = v; best = k; }
    }
    n = best;
    path.push(n);
  }
  // ② 펼치기: 안 둬 본 수 하나
  if (n.untried.length) {
    const m = n.untried.pop()!;
    const nb = n.b.slice();
    nb[m] = n.mover;
    const c = mkNode(nb, 3 - n.mover, m);
    n.kids.push(c);
    n = c;
    path.push(n);
  }
  // ③ 끝까지 아무렇게나
  const b = n.b.slice();
  let mover = n.mover;
  let res = win(b);                                   // 0 진행 · 1 · 2 · 3 무승부
  while (!res) {
    const em = legal(b);
    b[em[Math.floor(Math.random() * em.length)]!] = mover;
    mover = 3 - mover;
    res = win(b);
  }
  // ④ 올리기: 그 마디로 「둔 사람」 기준 승 1 · 무 0.5
  for (const p of path) {
    p.N++;
    const justMoved = 3 - p.mover;
    p.W += res === 3 ? 0.5 : res === justMoved ? 1 : 0;
  }
}
// 다 돌면: root.kids 중 N 이 가장 큰 수를 둔다
```

## 흔한 실수 · 확인 목록
- [ ] **W 를 늘 뿌리 기준으로 올리면 상대 차례에서도 내게 좋은 수를 고른다** — 마디마다 「그 마디로 둔 사람」 기준으로 올린다.
- [ ] **마지막에 승률이 가장 높은 수를 고르면 두세 번 운 좋은 수를 고른다** — 방문 수 N 이 가장 큰 수 — 많이 확인된 수.
- [ ] **반복 수가 적으면 뻔한 실수를 한다** — 틱택토도 수백 번은 필요. 바로 이기는 수 · 바로 막을 수는 먼저 검사하면 적은 반복에서도 단단하다.

## 완성 기준 체크리스트
- [ ] 반복이 쌓일수록 좋은 수 쪽 가지가 굵고 깊게 자라고, 그 칸 방문 수가 가장 커진다
- [ ] C 를 크게 하면 나무가 넓게, 작게 하면 좁고 깊게 자란다
- [ ] 틱택토에서 700번 반복한 AI 가 지지 않는다

## 이 기술 정보
- id: `i347` · 분류: 게임 시스템 · AI › 게임 AI · 공통 · 난이도 보통 · 폰 부담 보통 (폰 주의) — 반복 1번 = 고르기(깊이만큼) + 무작위 끝까지 두기. 틱택토 700번은 순식간, 헥스 11×11 은 수만 번이 필요해 워커에서 0.5~1초.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i347
- 쓰면 좋을 때: 좋은 평가 함수를 만들기 어려운 게임 (헥스 · 바둑 꼴 · 하바나) / 생각 시간(반복 수)만으로 난이도를 나눌 때
- 쓰지 말 때: 한 수 실수가 바로 지는 날카로운 전술 게임(체스) — 알파베타 + 평가가 더 정확 / 끝까지 두는 데 아주 오래 걸리는 게임 — 무작위 대국을 짧게 끊고 평가로 대신

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### I347 — `src/demos/demosGameAI.ts:1656`
```ts
const I347: DemoMap = {
  i347: {
    kind: '2d',
    caption: '고르기(금빛 길) → 새 마디 펼치기 → 끝까지 아무렇게나 둬 보기(점선) → 결과를 길 따라 올리기 — 많이 이긴 쪽 가지가 굵고 크게 자라요',
    make() {
      const st = { speed: 1 };
      let Cexp = 1.2;
      let root!: MC;
      let it = 0;
      let acc = 0;
      let r = rng(newSeed());
      let last: { path: MC[]; leaf: MC; result: number; len: number } | null = null;
      let lastT = 0;
      let holdT = 0;
      let clock = 0;
      const MAXIT = 700;
      const legalOf = (b: number[]): number[] => (tttWin(b) ? [] : b.map((v, i) => (v ? -1 : i)).filter((i) => i >= 0));
      const mkNode = (b: number[], mover: number, move: number, parent: MC | null, x0: number, x1: number): MC => {
        const legal = legalOf(b);
        return { b, mover, move, parent, kids: [], untried: shuffle(legal.slice(), r), legal, N: 0, W: 0, x0, x1, depth: parent ? parent.depth + 1 : 0, born: clock };
      };
      const reset0 = (): void => {
        r = rng(newSeed());
        const b = Array<number>(9).fill(0);
        const cells = shuffle([0, 1, 2, 3, 4, 5, 6, 7, 8], r);
        b[cells[0]!] = 1;
        b[cells[1]!] = 2;
        root = mkNode(b, 1, -1, null, 0, 1);
        it = 0;
        acc = 0;
        last = null;
        holdT = 0;
      };
      reset0();
      const iterate = (): void => {
        let n = root;
        const path: MC[] = [root];
        while (!n.untried.length && n.kids.length) {
          let best = n.kids[0]!;
          let bv = -Infinity;
          for (const k of n.kids) {
            const v = k.W / k.N + Cexp * Math.sqrt(Math.log(n.N) / k.N);
            if (v > bv) {
              bv = v;
              best = k;
            }
          }
          n = best;
          path.push(n);
        }
        if (n.untried.length) {
          const m = n.untried.pop()!;
          const nb = n.b.slice();
          nb[m] = n.mover;
          const idx = n.legal.indexOf(m);
          const span = (n.x1 - n.x0) / n.legal.length;
          const c = mkNode(nb, 3 - n.mover, m, n, n.x0 + idx * span, n.x0 + (idx + 1) * span);
          n.kids.push(c);
          n = c;
          path.push(n);
        }
        // 끝까지 아무렇게나
        const b = n.b.slice();
        let mover = n.mover;
        let len = 0;
        let res = tttWin(b);
        while (!res) {
          const em = legalOf(b);
          b[em[Math.floor(r() * em.length)]!] = mover;
          mover = 3 - mover;
          len++;
          res = tttWin(b);
        }
        for (const p of path) {
          p.N++;
          const justMoved = 3 - p.mover;
          p.W += res === 3 ? 0.5 : res === justMoved ? 1 : 0;
        }
        last = { path, leaf: n, result: res, len };
        lastT = clock;
        it++;
      };
      return {
        draw(g, w, h, _t, dt) {
          reset(g);
          const d = Math.min(dt, 0.1) * st.speed;
          clock += d;
          const ivl = Math.max(0.035, 0.75 / (1 + it * 0.16));
          if (it < MAXIT) {
            acc += d;
            let guard = 0;
            while (acc >= ivl && guard++ < 40 && it < MAXIT) {
              acc -= ivl;
              iterate();
            }
          } else {
            holdT += d;
            if (holdT > 2.5) reset0();
          }
          const u = scaleOf(w, h);
          bg(g, w, h);
          header(g, w, u, '몬테카를로 트리 탐색', C.text, `반복 ${it}`, C.gold);
          // 왼쪽: 뿌리 판 + 방문 수
          const bs = Math.min(h * 0.46, w * 0.25);
          const bx = 8 * u + bs / 2 + 2 * u;
          const by = 36 * u + bs / 2;
          const heat = Array<number>(9).fill(0);
          for (const k of root.kids) heat[k.move] = k.N;
          let bestK: MC | null = null;
          for (const k of root.kids) if (!bestK || k.N > bestK.N) bestK = k;
          miniTTT(g, root.b, bx, by, bs, { heat, frame: 'rgba(255,209,102,0.5)' });
          const c = bs / 3;
          for (const k of root.kids) {
            const px = bx - bs / 2 + (k.move % 3) * c + c / 2;
            const py = by - bs / 2 + Math.floor(k.move / 3) * c + c / 2;
            txt(g, String(k.N), px, py + 0.3 * u, Math.min(c * 0.36, 9 * u), k === bestK ? '#1a1405' : '#fff', 'center', 900);
          }
          txt(g, '칸 = 방문 수', bx, by + bs / 2 + 8 * u, 6.5 * u, C.sub, 'center', 700);
          if (bestK && it > 30) {
            const q = bestK.W / bestK.N;
            pill(g, `고를 칸 승률 ${Math.round(q * 100)}%`, bx, by + bs / 2 + 21 * u, 6.5 * u, winColor(q), '#0b1020');
          }
          txt(g, 'X 차례', bx, 27 * u, 7 * u, C.x, 'center', 800);
          // 오른쪽: 나무
          const L = bx + bs / 2 + 14 * u;
          const R = w - 6 * u;
          const top = 26 * u;
          const DMAX = 5;
          const dy = (h - top - 10 * u) / DMAX;
          const X = (n: MC): number => L + ((n.x0 + n.x1) / 2) * (R - L);
          const Y = (n: MC): number => top + n.depth * dy;
          const onPath = new Set<MC>();
          const phase = last ? clamp((clock - lastT) / Math.max(ivl, 0.0001), 0, 1) : 1;
          const slow = ivl > 0.22;
          if (last) for (const p of last.path) onPath.add(p);
          const stack: MC[] = [root];
          // 줄 먼저
          while (stack.length) {
            const n = stack.pop()!;
            if (n.depth >= DMAX) continue;
            for (const k of n.kids) {
              const lw = (0.4 + Math.sqrt(k.N) * 0.22) * u;
              const hot = onPath.has(k) && (!slow || phase < 0.9);
              g.strokeStyle = hot ? C.gold : winColor(k.W / Math.max(1, k.N), 0.55);
              g.lineWidth = hot ? Math.max(lw, 1.6 * u) : lw;
              g.beginPath();
              g.moveTo(X(n), Y(n));
              g.lineTo(X(k), Y(k));
              g.stroke();
              stack.push(k);
            }
          }
          // 마디
          stack.push(root);
          while (stack.length) {
            const n = stack.pop()!;
            if (n.depth > DMAX) continue;
            const pop = back((clock - n.born) / 0.3);
            const rad = Math.min(7.5 * u, (1.2 + Math.sqrt(n.N) * 0.42) * u) * pop;
            const x = X(n);
            const y = Y(n);
            if (onPath.has(n) && slow) glow(g, x, y, rad * 3, C.gold, 0.45 * (1 - phase * 0.5));
            g.fillStyle = n === root ? '#e8ecff' : winColor(n.W / Math.max(1, n.N));
            g.beginPath();
            g.arc(x, y, Math.max(1 * u, rad), 0, TAU);
            g.fill();
            if (n.depth < DMAX) for (const k of n.kids) stack.push(k);
          }
          // 끝까지 둬 보기 (점선)
          if (last && slow && last.leaf.depth <= DMAX) {
            const x = X(last.leaf);
            const y = Y(last.leaf);
            const k = clamp((phase - 0.3) / 0.45, 0, 1);
            const yEnd = Math.min(h - 6 * u, y + dy * Math.max(1, last.len) * 0.75);
            g.strokeStyle = 'rgba(200,210,255,0.75)';
            g.setLineDash([2 * u, 2 * u]);
            g.lineWidth = 1 * u;
            g.beginPath();
            g.moveTo(x, y);
            const steps = 8;
            for (let i = 1; i <= Math.round(steps * k); i++) g.lineTo(x + Math.sin(i * 2.1) * 4 * u, lerp(y, yEnd, i / steps));
            g.stroke();
            g.setLineDash([]);
            if (k >= 1) {
              const res = last.result;
              pill(g, res === 3 ? '무' : res === 1 ? 'X 승' : 'O 승', x, yEnd, 6 * u, res === 3 ? '#aab3d6' : res === 1 ? C.x : C.o, '#0b1020');
            }
          }
          if (it >= MAXIT) pill(g, '가장 많이 가 본 칸을 둔다', (L + R) / 2, h - 8 * u, 7 * u, C.gold);
        },
        controls: [
          speedCtl(st),
          { type: 'range', label: '탐험 상수 C (클수록 넓게)', min: 0.2, max: 3, step: 0.1, value: 1.2, on: (v) => { Cexp = v; reset0(); } },
          { type: 'button', label: '다시', on: () => reset0() },
        ] as Control[],
      };
    },
  },
};
```

## 관련 기술
- 먼저 알면 좋은 기술: [미니맥스 게임 나무](https://ai-techstudio.web.app/ai/t/i340.md) `i340`
- 다음에 해 볼 기술: [난이도 = 사람 같은 실수 (온도 소프트맥스)](https://ai-techstudio.web.app/ai/t/i358.md) `i358` · [화면 안 멈추는 계산 (Web Worker)](https://ai-techstudio.web.app/ai/t/i359.md) `i359`
- 참고 문서: [Wikipedia — Monte Carlo tree search](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search)