# AI 꾸러미 — 같은 판 기억 (전치표 · 조브리스트 해시) — Zobrist hashing
> 칸 · 말마다 무작위 비트를 정해 두고 놓인 말의 비트를 XOR 로 모은 값을 판의 이름표로 써서, 다른 순서로 온 같은 판의 결과를 표에서 바로 꺼낸다.  
> 견본: https://ai-techstudio.web.app/#t/i344

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

## 주문서

### 만들어 줘: 같은 판 기억 (전치표 · 조브리스트 해시) — Zobrist hashing

#### 1. 목표
체스 · 오목 AI의 탐색에 조브리스트 해시 전치표를 넣어 줘 — 같은 판은 다시 계산하지 않게. 분위기는 비트가 XOR 되는 과정을 보여 주는 설명.

#### 2. 핵심 기술 용어
- **Zobrist hashing** — 칸 × 말마다 무작위 수 — 판 이름표 = 놓인 것들의 XOR
- **Transposition table** — 판 이름표 → 이미 계산한 값 · 깊이 · 최선 수 표
- **Incremental hash update** — 말 하나 놓거나 빼면 그 칸 수 하나만 XOR

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

#### 4. 조건
- 무작위 수는 판마다가 아니라 게임 시작 때 한 번 (같은 판 = 늘 같은 이름표)
- 말을 둘 때 · 뺄 때 이름표를 XOR 로 갱신 (차례도 Z 하나로 넣는다)
- 표 항목에 이름표 전체를 같이 저장해 다른 판이 같은 칸에 온 것(충돌)을 걸러낸다
- 저장한 깊이가 지금 필요한 깊이보다 얕으면 값을 그대로 쓰지 않는다 (최선 수만 참고)
- 전치표 켬/끔 비교로 아낀 계산 수를 보여 주기

#### 5. 완성 기준 (이게 보이면 성공)
- 두 길(다른 순서)로 같은 판에 닿으면 이름표 비트가 똑같다
- 켬이면 두 번째 판은 「찾았다! 계산 0」, 끔이면 다시 계산한다
- 같은 깊이 탐색에서 켬일 때 본 마디 수가 확실히 적다

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

## 원리
- 시작할 때 칸 i · 말 종류 p 마다 무작위 수 Z[i][p] 를 정한다 (빈 판 = 0).
- 판의 이름표 = 놓인 말들의 Z 를 모두 XOR. XOR 은 순서와 상관없으니 「X→1, O→5, X→9」 와 「X→9, O→5, X→1」 이 같은 이름표가 된다.
- 말을 놓거나 뺄 때 그 칸의 Z 하나만 XOR 하면 이름표가 바로 갱신된다 (판 전체를 다시 볼 필요 없음).
- 이름표의 아래 몇 비트를 표의 칸 번호로 쓰고(견본은 아래 3비트 = 8칸), 거기에 계산한 값을 저장한다. 같은 판이 또 나오면 꺼내 쓰고 계산을 건너뛴다.

## 핵심 코드 — 조브리스트 이름표 + 전치표
(발췌: 새로 씀 (demos/demosGameAI.ts i344 견본의 칸 × 말 무작위 수 XOR · 해시 아래 비트 = 표 칸 방식))
```ts
const CELLS = 225, PIECES = 2;                       // 예: 15×15 오목, 흑 · 백
const rnd32 = (): number => (Math.random() * 0x100000000) >>> 0;
// 32비트 두 개를 이어 충돌을 줄인다 (hi 는 확인용, lo 는 칸 번호용)
const Zlo = Array.from({ length: CELLS * PIECES }, rnd32);
const Zhi = Array.from({ length: CELLS * PIECES }, rnd32);
const Zturn = [rnd32(), rnd32()];

let lo = 0, hi = 0;                                   // 빈 판 = 0
function toggle(cell: number, piece: number): void {  // 놓기 · 빼기 모두 같은 XOR
  lo ^= Zlo[cell * PIECES + piece]!;
  hi ^= Zhi[cell * PIECES + piece]!;
}
function flipTurn(): void { lo ^= Zturn[0]!; hi ^= Zturn[1]!; }

interface Entry { hi: number; lo: number; depth: number; value: number; best: number }
const BITS = 16;
const table: (Entry | undefined)[] = new Array(1 << BITS);

function probe(depth: number): Entry | undefined {
  const e = table[lo & ((1 << BITS) - 1)];             // 아래 비트 = 칸 번호
  if (!e || e.hi !== hi || e.lo !== lo) return undefined; // 다른 판이 같은 칸 (충돌)
  return e.depth >= depth ? e : undefined;             // 얕게 본 값은 그대로 쓰지 않기
}
function store(depth: number, value: number, best: number): void {
  table[lo & ((1 << BITS) - 1)] = { hi, lo, depth, value, best };
}
```

## 흔한 실수 · 확인 목록
- [ ] **해시 비트가 적으면 다른 판이 같은 이름표가 된다** — 64비트(32비트 두 개)로 만들고 항목에 이름표 전체를 저장해 확인한다.
- [ ] **차례를 해시에 안 넣으면 「같은 판 · 다른 차례」 값을 섞어 쓴다** — 차례 전용 무작위 수를 차례가 바뀔 때마다 XOR.
- [ ] **얕은 깊이로 저장한 값을 깊은 탐색에 그대로 쓰면 수읽기가 짧아진다** — 저장 깊이 ≥ 필요한 깊이일 때만 값을 쓰고, 아니면 최선 수만 먼저 보기에 쓴다.
- [ ] **알파베타의 잘린 값(하한 · 상한)을 정확한 값처럼 저장하면 틀린다** — 항목에 「정확 · 하한 · 상한」 표시를 같이 두고 꺼낼 때 α · β 와 비교한다.

## 완성 기준 체크리스트
- [ ] 두 길(다른 순서)로 같은 판에 닿으면 이름표 비트가 똑같다
- [ ] 켬이면 두 번째 판은 「찾았다! 계산 0」, 끔이면 다시 계산한다
- [ ] 같은 깊이 탐색에서 켬일 때 본 마디 수가 확실히 적다

## 이 기술 정보
- id: `i344` · 분류: 게임 시스템 · AI › 게임 AI · 공통 · 난이도 보통 · 폰 부담 가벼움 (폰 OK) — 갱신은 XOR 한 번. 표 메모리는 칸 수 × 항목 크기 — 2^20 칸이면 몇십 MB 이니 폰은 2^16 정도로.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i344
- 쓰면 좋을 때: 다른 순서로 같은 판에 자주 닿는 게임 (체스 · 오목 · 슬라이딩 퍼즐) / 반복 심화(i343)와 함께 — 앞 깊이의 최선 수를 표에서 꺼내 먼저 보기
- 쓰지 말 때: 같은 판이 거의 안 겹치는 작은 탐색 — 표 관리 비용만 든다 / 판을 문자열로 바꿔 Map 열쇠로 쓰기 — 느리다. 정수 해시로

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### I344 — `src/demos/demosGameAI.ts:1083`
```ts
const I344: DemoMap = {
  i344: {
    kind: '2d',
    caption: '칸 · 돌마다 정해 둔 무작위 비트를 XOR 로 모은 값이 판의 이름표(해시) — 순서가 달라도 같은 판이면 같은 이름이라 표에서 바로 꺼내요',
    make() {
      const BITS = 12;
      let tt = true;
      let seed = newSeed();
      let codes: number[][] = [];
      let mv: [number, number][] = [];
      let saved = 0;
      const setup = (): void => {
        const r = rng(seed);
        codes = [];
        for (let i = 0; i < 9; i++) codes.push([0, 1 + Math.floor(r() * 4095), 1 + Math.floor(r() * 4095)]);
        const cells = shuffle([0, 1, 2, 3, 4, 5, 6, 7, 8], r);
        mv = [[cells[0]!, 1], [cells[1]!, 2], [cells[2]!, 1]];
        saved = 30 + Math.floor(r() * 90);
      };
      setup();
      // 사건: 0 시작 · 1~3 A 경로 · 4 저장 · 5~7 B 경로 · 8 찾기
      const seq = new Seq(9, 0.85, 2.6, () => {
        seed = newSeed();
        setup();
        seq.restart(9);
      });
      const pathMoves = (p: number): [number, number][] => (p === 0 ? mv : [mv[2]!, mv[1]!, mv[0]!]);
      const hashAfter = (p: number, k: number): number => {
        let hv = 0;
        for (let i = 0; i < k; i++) {
          const [cell, pc] = pathMoves(p)[i]!;
          hv ^= codes[cell]![pc]!;
        }
        return hv;
      };
      const boardAfter = (p: number, k: number): number[] => {
        const b = Array<number>(9).fill(0);
        for (let i = 0; i < k; i++) {
          const [cell, pc] = pathMoves(p)[i]!;
          b[cell] = pc;
        }
        return b;
      };
      const bitsRow = (g: G, v: number, x: number, y: number, bw: number, u: number, col: string, lowHi = false, label = ''): void => {
        if (label) txt(g, label, x - 3 * u, y + bw / 2, 6.5 * u, C.sub, 'right', 800);
        for (let k = 0; k < BITS; k++) {
          const bit = (v >> (BITS - 1 - k)) & 1;
          const bx = x + k * bw + (k >= 4 ? 1.5 * u : 0) + (k >= 8 ? 1.5 * u : 0);
          rr(g, bx, y, bw - 1 * u, bw, 1.5 * u);
          const low = lowHi && k >= BITS - 3;
          g.fillStyle = bit ? (low ? C.gold : col) : 'rgba(255,255,255,0.07)';
          g.fill();
          if (bw > 6 * u) txt(g, String(bit), bx + (bw - 1 * u) / 2, y + bw / 2 + 0.3 * u, bw * 0.62, bit ? '#0b1020' : 'rgba(255,255,255,0.3)', 'center', 800);
        }
      };
      return {
        draw(g, w, h, t, dt) {
          reset(g);
          seq.tick(dt);
          const u = scaleOf(w, h);
          bg(g, w, h);
          const ev = seq.i;
          const fr = seq.frac;
          header(g, w, u, '전치표 · 조브리스트', C.text, tt ? '표 켬' : '표 끔', tt ? C.green : C.red);
          // 왼쪽: 두 길
          const lw = Math.min(w * 0.5, 150 * u);
          const bs = Math.min(29 * u, (h - 74 * u) / 2);
          const gapX = (lw - 14 * u) / 3;
          const rows = [0, 1];
          const progress = (p: number): number => (p === 0 ? clamp(ev, 0, 3) : clamp(ev - 4, 0, 3));
          rows.forEach((p) => {
            const y = 40 * u + p * (bs + 34 * u);
            txt(g, p === 0 ? '길 ①' : '길 ②', 8 * u, y - bs / 2 - 7 * u, 7.5 * u, p === 0 ? C.violet : C.teal, 'left', 900);
            const k = progress(p);
            for (let i = 0; i < 3; i++) {
              const x = 8 * u + bs / 2 + 3 * u + i * gapX;
              const shown = i < k;
              const [cell, pc] = pathMoves(p)[i]!;
              miniTTT(g, boardAfter(p, i + 1), x, y, bs, { alpha: shown ? 1 : 0.22, hi: shown ? cell : undefined, frame: shown && i === k - 1 ? (p === 0 ? C.violet : C.teal) : undefined });
              txt(g, `${pc === 1 ? 'X' : 'O'}→${cell + 1}`, x, y + bs / 2 + 6 * u, 6.5 * u, shown ? (pc === 1 ? C.x : C.o) : C.dim, 'center', 800);
              if (i < 2) arrow(g, x + bs / 2 + 2 * u, y, x + gapX - bs / 2 - 2 * u, y, shown ? 'rgba(200,210,255,0.6)' : C.dim2, 1 * u, 3.5 * u);
            }
          });
          // 같은 판 표시
          if (ev >= 8) {
            const x = 8 * u + bs / 2 + 3 * u + 2 * gapX + bs / 2 + 4 * u;
            const y1 = 40 * u;
            const y2 = 40 * u + bs + 34 * u;
            g.strokeStyle = C.gold;
            g.lineWidth = 1.4 * u;
            g.beginPath();
            g.moveTo(x, y1);
            g.quadraticCurveTo(x + 10 * u, (y1 + y2) / 2, x, y2);
            g.stroke();
            pill(g, '같은 판!', x + 6 * u, (y1 + y2) / 2, 6.5 * u, C.gold, '#1a1405', 'left');
          }
          // 오른쪽: 해시 계산
          const rx = lw + 22 * u;
          const bw = Math.min(8.2 * u, (w - rx - 8 * u) / 12.6);
          const inA = ev >= 1 && ev <= 3;
          const inB = ev >= 5 && ev <= 7;
          const p = inB || ev >= 8 ? 1 : 0;
          const k = p === 0 ? clamp(ev, 0, 3) : clamp(ev - 4, 0, 3);
          const hy = 26 * u;
          if (inA || inB) {
            const [cell, pc] = pathMoves(p)[k - 1]!;
            const prev = hashAfter(p, k - 1);
            const code = codes[cell]![pc]!;
            const showRes = fr > 0.45;
            bitsRow(g, prev, rx, hy, bw, u, '#8f9ad0', false, '해시');
            bitsRow(g, code, rx, hy + bw + 3 * u, bw, u, pc === 1 ? C.x : C.o, false, `⊕${pc === 1 ? 'X' : 'O'}${cell + 1}`);
            g.strokeStyle = 'rgba(255,255,255,0.4)';
            g.lineWidth = 1 * u;
            g.beginPath();
            g.moveTo(rx, hy + 2 * bw + 5.5 * u);
            g.lineTo(rx + 12 * bw + 3 * u, hy + 2 * bw + 5.5 * u);
            g.stroke();
            if (showRes) bitsRow(g, prev ^ code, rx, hy + 2 * bw + 8 * u, bw, u, p === 0 ? C.violet : C.teal, true, '=');
          } else {
            const hv = hashAfter(p, k);
            bitsRow(g, hv, rx, hy + bw + 3 * u, bw, u, p === 0 ? C.violet : C.teal, true, '해시');
            if (ev === 0) txt(g, '빈 판 = 0', rx + 6 * bw, hy + bw * 0.2, 7 * u, C.sub, 'center', 700);
          }
          // 표
          const ty = hy + 3 * bw + 24 * u;
          const slotH = Math.min(11 * u, (h - ty - 6 * u) / 8);
          const finalHash = hashAfter(0, 3);
          const slot = finalHash & 7;
          txt(g, '전치표 (해시 끝 3비트 = 칸 번호)', rx, ty - 6 * u, 6.5 * u, C.sub, 'left', 700);
          for (let i = 0; i < 8; i++) {
            const y = ty + i * slotH;
            const has = ev >= 4 && i === slot && tt;
            const hit = ev >= 8 && i === slot;
            rr(g, rx, y, w - rx - 8 * u, slotH - 1.5 * u, 2 * u);
            g.fillStyle = hit && tt ? `rgba(111,227,160,${0.25 + 0.15 * Math.sin(t * 8)})` : has ? 'rgba(184,146,255,0.22)' : 'rgba(255,255,255,0.04)';
            g.fill();
            txt(g, String(i), rx + 5 * u, y + slotH / 2 - 0.5 * u, 6.5 * u, has ? C.gold : C.dim, 'center', 800);
            if (has) {
              const a = ev === 4 ? easeOut(fr * 2) : 1;
              g.globalAlpha = a;
              txt(g, `판 값 저장 · 계산 ${saved}노드`, rx + 12 * u, y + slotH / 2 - 0.5 * u, 6.5 * u, C.text, 'left', 700);
              g.globalAlpha = 1;
            }
          }
          if (ev >= 8) {
            if (tt) pill(g, `찾았다! 계산 0 (아낀 ${saved}노드)`, w - 8 * u, h - 8 * u, 7 * u, C.green, '#06180e', 'right');
            else {
              const k2 = clamp(seq.holdT / 2, 0, 1);
              pill(g, `다시 계산 … ${Math.round(saved * k2)} / ${saved}노드`, w - 8 * u, h - 8 * u, 7 * u, C.red, '#1a0610', 'right');
            }
          } else if (ev === 4) pill(g, '표에 저장', w - 8 * u, h - 8 * u, 7 * u, C.violet, '#140a26', 'right');
        },
        controls: [
          speedCtl(seq),
          { type: 'toggle', label: '전치표 쓰기', value: true, on: (v) => { tt = v; } },
          { type: 'button', label: '다른 수 · 다른 비트', on: () => { seed = newSeed(); setup(); seq.restart(9); } },
        ] as Control[],
      };
    },
  },
};
```

## 관련 기술
- 먼저 알면 좋은 기술: [알파베타 가지치기](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/i345.md) `i345`
- 참고 문서: [Wikipedia — Zobrist hashing](https://en.wikipedia.org/wiki/Zobrist_hashing) · [Chessprogramming wiki — Transposition Table](https://www.chessprogramming.org/Transposition_Table)