# AI 꾸러미 — 미니맥스 게임 나무 — Minimax (game tree search)
> 게임을 끝까지 다 둬 본 결과(승 +1 · 무 0 · 패 −1)를 내 차례엔 가장 큰 값, 상대 차례엔 가장 작은 값으로 위로 올려 최선의 수를 고른다.  
> 견본: https://ai-techstudio.web.app/#t/i340

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

## 주문서

### 만들어 줘: 미니맥스 게임 나무 — Minimax (game tree search)

#### 1. 목표
틱택토 끝판의 컴퓨터 상대를 미니맥스로 만들어 줘. 탐색 과정은 나무 그림으로 한 마디씩 보여 주는 설명.

#### 2. 핵심 기술 용어
- **Minimax (game tree search)** — 내 차례 최댓값 · 상대 차례 최솟값으로 올리기
- **Game tree** — 판 하나 = 마디, 둘 수 하나 = 가지
- **Terminal evaluation (+1 / 0 / −1)** — 끝난 판의 점수 — 내 승 · 무승부 · 내 패
- **Depth-first recursion** — 한 가지를 끝까지 내려갔다 올라오며 값 정하기

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

#### 4. 조건
- 게임 규칙(수 목록 · 두기 · 끝 판정 · 점수)과 탐색 함수를 나눈다
- 점수는 늘 한쪽(AI) 기준으로 — 차례마다 기준이 바뀌지 않게
- 판은 복사해서 두거나 두고 되돌리기 — 원래 판을 망가뜨리지 않게
- 설명 화면은 「들어감 · 잎 값 · 올림」 사건을 차례로 재생, 빈칸 수(나무 깊이) 3~4 조절

#### 5. 완성 기준 (이게 보이면 성공)
- 나무의 잎에 +1 · 0 · −1 이 붙고, 마디 값이 차례(최대 · 최소)에 맞게 위로 올라간다
- 뿌리에서 고른 수가 실제로 지지 않는 수다 (무작위 판 100개로 확인)
- 「다른 판」을 누르면 새 끝판으로 다시 펼친다

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

## 원리
- 지금 판에서 둘 수 있는 수마다 판을 하나씩 만들고, 그 판에서 또 상대의 수마다 … 끝날 때까지 펼친다.
- 끝난 판(잎)은 내 승 +1 · 무 0 · 내 패 −1.
- 위로 올라오며: 내 차례 마디 = 자식 값 중 가장 큰 값, 상대 차례 마디 = 가장 작은 값 (상대도 최선을 둔다고 가정).
- 뿌리에서 가장 큰 값을 준 자식이 고를 수 — 견본은 빈칸 3~4개 틱택토 끝판으로 나무 전체를 그린다.

## 핵심 코드 — 틱택토 미니맥스 — 끝까지 펼치고 최대 · 최소로 올리기
(발췌: demos/demosGameAI.ts buildMinimax() 의 mk() 를 정리)
```ts
// b: 9칸 (0 빈칸 · 1 X · 2 O), win(b): 0 진행 중 · 1 · 2 이긴 쪽 · 3 무승부
function minimax(b: number[], mover: number, me: number): number {
  const term = win(b);
  if (term) return term === 3 ? 0 : term === me ? 1 : -1;     // 잎: 승 +1 · 무 0 · 패 -1
  const vals: number[] = [];
  for (let i = 0; i < 9; i++) {
    if (b[i]) continue;
    const nb = b.slice();                                     // 판 복사
    nb[i] = mover;
    vals.push(minimax(nb, 3 - mover, me));
  }
  return mover === me ? Math.max(...vals) : Math.min(...vals); // 내 차례 최대 · 상대 차례 최소
}

function bestMove(b: number[], me: number): number {
  let best = -1, bv = -Infinity;
  for (let i = 0; i < 9; i++) {
    if (b[i]) continue;
    const nb = b.slice();
    nb[i] = me;
    const v = minimax(nb, 3 - me, me);
    if (v > bv) { bv = v; best = i; }
  }
  return best;
}
```

## 흔한 실수 · 확인 목록
- [ ] **점수를 「지금 둔 사람」 기준으로 주면 최대 · 최소가 뒤섞인다** — 점수는 늘 AI(뿌리) 기준, 차례에 따라 최대 · 최소만 바꾼다.
- [ ] **빈 판부터 매번 다 펼치면 첫 수가 느리다** — 틱택토는 괜찮지만 큰 게임은 깊이 제한 · 알파베타 · 같은 판 기억(i344)이 필요하다.
- [ ] **같은 값 수가 여럿이면 늘 첫 칸만 둔다** — 같은 값 중 무작위로 고르거나, 빨리 이기는 수를 조금 더 높게(+1 대신 +10 − 깊이).

## 완성 기준 체크리스트
- [ ] 나무의 잎에 +1 · 0 · −1 이 붙고, 마디 값이 차례(최대 · 최소)에 맞게 위로 올라간다
- [ ] 뿌리에서 고른 수가 실제로 지지 않는 수다 (무작위 판 100개로 확인)
- [ ] 「다른 판」을 누르면 새 끝판으로 다시 펼친다

## 이 기술 정보
- id: `i340` · 분류: 게임 시스템 · AI › 게임 AI · 공통 · 난이도 쉬움 · 폰 부담 가벼움 (폰 OK) — 틱택토 빈 판부터 끝까지 = 약 55만 잎. 빈칸 3개 끝판은 잎 몇 개 ~ 십여 개라 설명용으로 딱. 깊이마다 지수로 늘어난다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i340
- 쓰면 좋을 때: 틱택토 · 님처럼 끝까지 다 볼 수 있는 작은 게임 / 「컴퓨터는 이렇게 생각한다」 수학 설명
- 쓰지 말 때: 경우의 수가 큰 게임(체스 · 오목) — 알파베타(i341) + 깊이 제한 + 평가 함수(i346) / 주사위 · 카드처럼 운이 있는 게임 — 기대값 탐색(i348)

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### buildMinimax — `src/demos/demosGameAI.ts:334`
```ts
function buildMinimax(empties: number, seed: number): MPos {
  const r = rng(seed);
  for (let tries = 0; tries < 4000; tries++) {
    const b = Array<number>(9).fill(0);
    const pcs = 9 - empties;
    const nx = Math.ceil(pcs / 2);
    const cells = shuffle([0, 1, 2, 3, 4, 5, 6, 7, 8], r);
    for (let i = 0; i < pcs; i++) b[cells[i]!] = i < nx ? 1 : 2;
    if (tttWin(b)) continue;
    const R = nx === pcs - nx ? 1 : 2;
    const nodes: MNode[] = [];
    const mk = (bb: number[], mover: number, move: number, depth: number): MNode => {
      const n: MNode = { id: nodes.length, b: bb, mover, move, val: 0, term: tttWin(bb), kids: [], depth, x: 0, y: 0, leaves: 1 };
      nodes.push(n);
      if (n.term) n.val = n.term === 3 ? 0 : n.term === R ? 1 : -1;
      else {
        for (let i = 0; i < 9; i++)
          if (!bb[i]) {
            const nb = bb.slice();
            nb[i] = mover;
            n.kids.push(mk(nb, 3 - mover, i, depth + 1));
          }
        const vs = n.kids.map((k) => k.val);
        n.val = mover === R ? Math.max(...vs) : Math.min(...vs);
      }
      return n;
    };
    const root = mk(b, R, -1, 0);
    const kv = root.kids.map((k) => k.val);
    if (kv.every((v) => v === kv[0])) continue;
    if (root.kids.some((k) => k.term && k.term !== 3)) continue; // 바로 이기는 수가 있으면 너무 쉬움
    const ev: MPos['ev'] = [];
    const walk = (n: MNode): void => {
      ev.push({ k: 'in', n });
      if (!n.kids.length) ev.push({ k: 'leaf', n });
      else {
        for (const c of n.kids) walk(c);
        ev.push({ k: 'up', n });
      }
    };
    walk(root);
    return { root, R, ev, nodes };
  }
  // 못 찾으면 (거의 없음) 아무 판
  return buildMinimax(empties, seed + 1);
}
```

## 관련 기술
- 다음에 해 볼 기술: [알파베타 가지치기](https://ai-techstudio.web.app/ai/t/i341.md) `i341` · [반복 심화 + 시간 예산](https://ai-techstudio.web.app/ai/t/i343.md) `i343` · [평가 함수 설계 (가중치)](https://ai-techstudio.web.app/ai/t/i346.md) `i346`
- 참고 문서: [Wikipedia — Minimax](https://en.wikipedia.org/wiki/Minimax)