# AI 꾸러미 — 알파베타 가지치기 — Alpha-beta pruning
> 미니맥스 탐색에서 「더 봐도 결과가 안 바뀌는 가지」를 잘라, 같은 답을 훨씬 적게 보고 찾는다.  
> 견본: https://ai-techstudio.web.app/#t/i341

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

## 주문서

### 만들어 줘: 알파베타 가지치기 — Alpha-beta pruning

#### 1. 목표
틱택토 · 커넥트4의 컴퓨터 상대를 알파베타 가지치기로 만들어 줘. 탐색 과정은 나무 그림으로 한 단계씩 보여 주는 설명.

#### 2. 핵심 기술 용어
- **Alpha-beta pruning** — 알파베타 가지치기
- **Minimax** — 내 차례는 최댓값 · 상대 차례는 최솟값
- **Move ordering** — 좋은 수부터 보기 — 더 많이 잘린다
- **Negamax · iterative deepening** — 부호만 바꾼 한 줄 판 · 깊이를 1씩 늘리며 찾기

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

#### 4. 조건
- 게임 규칙(수 목록 · 두기 · 평가)과 탐색 함수를 나눠서 — 탐색은 어떤 게임에도 쓸 수 있게
- 결과가 미니맥스와 같은지 자동 검사 (무작위 판 100개에서 값 비교)
- 보는 잎 수를 세어 미니맥스 대비 몇 % 인지 표시
- 한 수에 쓰는 시간 제한 (화면이 멈추지 않게)

#### 5. 완성 기준 (이게 보이면 성공)
- 같은 판에서 가지치기 켬/끔의 결과 값은 같고, 본 잎 수는 켬이 확실히 적다
- 설명 화면에서는 α · β 값이 바뀌는 과정과 잘린 가지(회색 · 가위)가 한 단계씩 보인다
- 수 정렬을 켜면 잘리는 가지가 더 많아진다

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

## 원리
- α = 내가 이미 확보한 가장 좋은 값, β = 상대가 허락할 가장 나쁜 값.
- 어떤 가지에서 α ≥ β 가 되면, 상대(또는 나)는 그 가지로 오지 않으니 남은 형제는 볼 필요가 없다.
- 결과(고르는 수 · 값)는 미니맥스와 똑같고, 보는 잎의 수만 줄어든다.
- 좋은 수를 먼저 보면 더 일찍 잘린다 — 최선이면 잎 수가 대략 제곱근으로 준다.

## 핵심 코드 — 알파베타 탐색 (어떤 게임에도 끼우는 꼴)
(발췌: demos/demosGameAI.ts alphaBetaEvents() 의 탐색 부분을 일반 게임용으로)
```ts
interface Game<S, M> {
  moves(s: S): M[];
  play(s: S, m: M): S;
  over(s: S): boolean;
  score(s: S): number; // 내(최댓값 쪽) 입장 점수
}

function alphaBeta<S, M>(g: Game<S, M>, s: S, depth: number, a: number, b: number, max: boolean, stat: { leaves: number }): number {
  if (depth === 0 || g.over(s)) {
    stat.leaves++;
    return g.score(s);
  }
  let v = max ? -Infinity : Infinity;
  for (const m of g.moves(s)) {            // 좋은 수부터 정렬해 두면 더 많이 잘린다
    const c = alphaBeta(g, g.play(s, m), depth - 1, a, b, !max, stat);
    if (max) { v = Math.max(v, c); a = Math.max(a, v); }
    else { v = Math.min(v, c); b = Math.min(b, v); }
    if (a >= b) break;                     // 가지치기 — 남은 형제는 결과를 못 바꾼다
  }
  return v;
}

/** 가장 좋은 수 고르기 */
function bestMove<S, M>(g: Game<S, M>, s: S, depth: number): { move: M | undefined; leaves: number } {
  const stat = { leaves: 0 };
  let best: M | undefined, a = -Infinity;
  for (const m of g.moves(s)) {
    const v = alphaBeta(g, g.play(s, m), depth - 1, a, Infinity, false, stat);
    if (v > a) { a = v; best = m; }
  }
  return { move: best, leaves: stat.leaves };
}
```

## 흔한 실수 · 확인 목록
- [ ] **가지치기를 켰더니 고르는 수가 달라졌다** — 결과는 미니맥스와 같아야 한다 — 달라지면 α · β 를 자식에 잘못 넘긴 버그. 무작위 판으로 둘을 비교하는 검사를 둔다.
- [ ] **평가 점수를 「지금 차례」 기준으로 주면 부호가 뒤섞인다** — 한쪽(최댓값 쪽) 기준으로 고정하거나, 네가맥스로 매번 부호를 뒤집는다 — 섞지 않는다.
- [ ] **깊이를 고정하면 판에 따라 수십 초 걸린다** — 깊이를 1씩 늘리며 시간 제한 안에서 끝난 가장 깊은 결과를 쓴다 (iterative deepening).
- [ ] **같은 점수 수가 여럿이면 늘 첫 수만 둔다** — 아이들 게임에선 같은 점수 중 무작위로 — 늘 같은 수는 금방 질린다.

## 완성 기준 체크리스트
- [ ] 같은 판에서 가지치기 켬/끔의 결과 값은 같고, 본 잎 수는 켬이 확실히 적다
- [ ] 설명 화면에서는 α · β 값이 바뀌는 과정과 잘린 가지(회색 · 가위)가 한 단계씩 보인다
- [ ] 수 정렬을 켜면 잘리는 가지가 더 많아진다

## 이 기술 정보
- id: `i341` · 분류: 게임 시스템 · AI › 게임 AI · 공통 · 난이도 보통 · 폰 부담 보통 (폰 주의) — 깊이에 따라 지수로 늘어난다. 깊이 4~6 이 보통 한계 — 시간 제한(예: 50ms)과 반복 깊이 늘리기를 함께.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i341
- 쓰면 좋을 때: 두 사람이 번갈아 두는 완전 정보 게임 (틱택토 · 오목 · 체스 · 커넥트4) / 「컴퓨터가 어떻게 생각하나」를 보여 주는 수학 설명
- 쓰지 말 때: 주사위 · 카드처럼 운이 섞인 게임 — 기댓값 탐색(expectimax)이나 몬테카를로 트리 탐색이 맞다 / 경우의 수가 너무 많은 바둑 같은 판

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### alphaBetaEvents — `src/demos/demosGameAI.ts:555`
```ts
function alphaBetaEvents(root: ANode, prune: boolean): AEv[] {
  const ev: AEv[] = [];
  const ab = (n: ANode, a: number, b: number): number => {
    ev.push({ k: 'in', n, a, b });
    if (!n.kids.length) {
      ev.push({ k: 'leaf', n });
      return n.v;
    }
    let v = n.max ? -Infinity : Infinity;
    for (let i = 0; i < n.kids.length; i++) {
      const cv = ab(n.kids[i]!, a, b);
      if (n.max) {
        v = Math.max(v, cv);
        a = Math.max(a, v);
      } else {
        v = Math.min(v, cv);
        b = Math.min(b, v);
      }
      ev.push({ k: 'ab', n, a, b, v });
      if (prune && a >= b && i < n.kids.length - 1) {
        ev.push({ k: 'cut', n, from: i + 1 });
        break;
      }
    }
    ev.push({ k: 'up', n, v });
    return v;
  };
  ab(root, -Infinity, Infinity);
  return ev;
}
```

## 관련 기술
- 먼저 알면 좋은 기술: [미니맥스 게임 나무](https://ai-techstudio.web.app/ai/t/i340.md) `i340`
- 다음에 해 볼 기술: [같은 판 기억 (전치표 · 조브리스트 해시)](https://ai-techstudio.web.app/ai/t/i344.md) `i344` · [반복 심화 + 시간 예산](https://ai-techstudio.web.app/ai/t/i343.md) `i343`
- 참고 문서: [Wikipedia — Alpha–beta pruning](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning) · [Chessprogramming wiki — Alpha-Beta](https://www.chessprogramming.org/Alpha-Beta)