# AI 꾸러미 — 님합 · 그런디 수 (게임 이론) — Nim-sum (bitwise XOR) > 더미 크기를 이진수로 써서 자리마다 XOR 한 님합이 0 이면 지는 자리 — 님합을 0 으로 만드는 수를 두면 늘 마지막 돌을 가져간다. > 견본: https://ai-techstudio.web.app/#t/i350 이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요. ## 주문서 ### 만들어 줘: 님합 · 그런디 수 (게임 이론) — Nim-sum (bitwise XOR) #### 1. 목표 님 (돌 더미 4개)의 AI 를 님합(이진수 XOR)으로 만들어 줘 — 이기는 수를 바로 찾게. 분위기는 이진수 표로 자리마다 1 을 세는 설명. #### 2. 핵심 기술 용어 - **Nim-sum (bitwise XOR)** — 더미 크기들의 XOR — 자리마다 1 의 개수가 짝수면 0 - **Bouton’s theorem** — 님합 0 = 지는 자리, 0 아님 = 이기는 자리 - **Sprague–Grundy number** — 님 꼴 게임을 님 더미 하나로 바꾼 값 (그런디 수) #### 3. 환경 - 플랫폼: TypeScript (브라우저), 라이브러리 없이 — 화면과 떨어진 순수 함수로 - 화면: 브라우저 — PC · 폰 모두 #### 4. 조건 - 이기는 수 찾기는 h XOR X < h 인 더미 — 더미를 h XOR X 개로 줄인다 - 님합이 0 이면 (지는 자리) 무작위로 조금만 가져가 시간을 끈다 - 설명 화면: 더미마다 이진수 줄, 자리마다 1 의 개수 짝 · 홀 표시, 님합 0 이 되는 순간 강조 - 마지막 돌을 가져가는 쪽이 이기는지(보통 님) 지는지(미제르 님) 규칙을 분명히 #### 5. 완성 기준 (이게 보이면 성공) - AI 차례가 지나면 이진수 표의 모든 자리가 짝수(님합 0)가 된다 - 처음 님합이 0 이 아니면 AI 가 늘 마지막 돌을 가져간다 - 「새 판」을 눌러도 같은 규칙으로 이긴다 #### 6. 진행 방식 - 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘. - 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘. - 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘. - 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘. - 답변과 코드 주석은 한국어로 해 줘. ## 원리 - 더미 크기를 이진수로 쓰고 자리(1 · 2 · 4 …)마다 1 의 개수를 센다. 모든 자리가 짝수면 님합 = 0. - 님합이 0 인 자리에서 어떤 수를 둬도 0 이 아니게 된다. 0 이 아닌 자리에서는 늘 0 으로 만드는 수가 있다. - 이기는 수: X = 님합. 크기 h 가 h XOR X < h 인 더미를 찾아 h XOR X 개만 남긴다. - 그래서 님합 0 을 상대에게 넘기는 쪽이 끝까지 그렇게 할 수 있고, 마지막 돌을 가져간다. - 다른 님 꼴 게임도 자리마다 그런디 수(갈 수 있는 자리 값에 없는 가장 작은 수)를 구해 같은 XOR 로 합친다. ## 핵심 코드 — 님합으로 이기는 수 찾기 (발췌: demos/demosGameAI.ts I350 의 gen() 을 정리) ```ts /** 더미들(hs)에서 둘 수: 어느 더미를 몇 개로 줄일지 */ function nimMove(hs: number[]): { heap: number; to: number } { const X = hs.reduce((a, b) => a ^ b, 0); // 님합 if (X) { const heap = hs.findIndex((v) => (v ^ X) < v); // 늘 하나는 있다 return { heap, to: hs[heap]! ^ X }; // 이렇게 두면 님합 = 0 } // 님합 0 = 지는 자리: 아무 더미에서 조금 가져가며 상대 실수를 기다린다 const ne = hs.map((v, i) => (v ? i : -1)).filter((i) => i >= 0); const heap = ne[Math.floor(Math.random() * ne.length)]!; return { heap, to: Math.floor(Math.random() * hs[heap]!) }; } // 예) [3, 5, 6] → 3 ^ 5 ^ 6 = 0 (지는 자리), [3, 4, 5] → X = 2, 3 ^ 2 = 1 → 첫 더미를 1 개로 ``` ## 흔한 실수 · 확인 목록 - [ ] **더하기로 님합을 구하면 틀린다** — 자리 올림이 없는 XOR 이어야 한다 — 「자리마다 1 의 개수가 짝수인가」. - [ ] **미제르 님(마지막 돌을 가져가면 짐)에 그대로 쓰면 끝에서 진다** — 더미가 모두 1 개 이하가 되는 순간만 규칙을 뒤집는다 (1 짜리 더미 수를 홀수로 남기기). - [ ] **늘 완벽하게 두면 아이들이 금방 그만둔다** — 난이도별로 일정 확률로 아무 수나 두게 한다 (i358). ## 완성 기준 체크리스트 - [ ] AI 차례가 지나면 이진수 표의 모든 자리가 짝수(님합 0)가 된다 - [ ] 처음 님합이 0 이 아니면 AI 가 늘 마지막 돌을 가져간다 - [ ] 「새 판」을 눌러도 같은 규칙으로 이긴다 ## 이 기술 정보 - id: `i350` · 분류: 게임 시스템 · AI › 게임 AI · 공통 · 난이도 쉬움 · 폰 부담 가벼움 (폰 OK) — XOR 몇 번. 비용 없음. - 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i350 - 쓰면 좋을 때: 님 · 님 꼴 게임의 완벽한 AI / 이진수 · XOR 을 게임으로 가르칠 때 - 쓰지 말 때: 님 꼴이 아닌 게임 — 후퇴 분석(i349)이나 탐색 / 아이용 쉬운 난이도 — 늘 완벽하면 못 이긴다. 온도 실수(i358)를 섞는다 ## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript) ### I350 — `src/demos/demosGameAI.ts:2191` ```ts const I350: DemoMap = { i350: { kind: '2d', caption: '더미 크기를 이진수로 쓰고 자리마다 1 의 개수를 세요 — AI 는 늘 모든 자리를 짝수(님합 0)로 맞추는 수를 둬서 마지막 돌을 가져가요', make() { const st = { speed: 1 }; let bits = true; let moves: NimMove[] = []; let start: number[] = []; const gen = (): void => { const r = rng(newSeed()); let hs: number[]; do hs = [0, 0, 0, 0].map(() => 1 + Math.floor(r() * 7)); while ((hs[0]! ^ hs[1]! ^ hs[2]! ^ hs[3]!) === 0); start = hs.slice(); moves = []; let who: 0 | 1 = 0; while (hs.some((v) => v > 0)) { const before = hs.slice(); const X = hs.reduce((a, b) => a ^ b, 0); let heap = -1; let to = 0; if (who === 0 && X) { heap = hs.findIndex((v) => (v ^ X) < v); to = hs[heap]! ^ X; } else { const ne = hs.map((v, i) => (v ? i : -1)).filter((i) => i >= 0); heap = ne[Math.floor(r() * ne.length)]!; to = Math.floor(r() * hs[heap]!); } moves.push({ who, heap, from: hs[heap]!, to, before }); hs[heap] = to; who = (1 - who) as 0 | 1; } }; gen(); const DUR = [2.4, 1.5]; let T = 0; const stateAt = (): { mi: number; k: number } => { let tt = T; for (let i = 0; i < moves.length; i++) { const d = DUR[moves[i]!.who]!; if (tt < d) return { mi: i, k: tt / d }; tt -= d; } return { mi: moves.length, k: tt }; }; return { draw(g, w, h, _t, dt) { reset(g); T += Math.min(dt, 0.1) * st.speed; const u = scaleOf(w, h); bg(g, w, h); const { mi, k } = stateAt(); if (mi >= moves.length && k > 2.6) { gen(); T = 0; } const m = moves[mi]; const cur = m ? m.before.slice() : moves.length ? moves[moves.length - 1]!.before.map((v, i) => (i === moves[moves.length - 1]!.heap ? moves[moves.length - 1]!.to : v)) : start; const think = m && m.who === 0 ? 0.45 : 0.15; const moving = m && k > think; const mk = m ? clamp((k - think) / 0.35, 0, 1) : 0; const after = cur.slice(); if (m && moving) after[m.heap] = m.to; const X = after.reduce((a, b) => a ^ b, 0); const showX = m && k > think + 0.35 ? X : cur.reduce((a, b) => a ^ b, 0); header(g, w, u, '님 — 님합', C.text, m ? (m.who === 0 ? 'AI 차례 (님합 계산)' : '상대 차례 (아무렇게나)') : 'AI 승!', m ? (m.who === 0 ? C.gold : C.x) : C.gold); // 더미 const HW = bits ? w * 0.5 : w - 16 * u; const colW = HW / 4; const sr = Math.min(colW * 0.3, (h - 52 * u) / 15); const baseY = h - 22 * u; for (let i = 0; i < 4; i++) { const cx = 8 * u + colW * i + colW / 2; const isHeap = m && m.heap === i; if (isHeap && k > 0.05) glow(g, cx, baseY - sr * 6, colW * 0.7, m!.who === 0 ? C.gold : C.x, 0.18); g.fillStyle = 'rgba(255,255,255,0.08)'; rr(g, cx - colW * 0.38, baseY + sr * 0.9, colW * 0.76, 3 * u, 1.5 * u); g.fill(); const n0 = cur[i]!; for (let s = 0; s < n0; s++) { let x = cx; let y = baseY - s * sr * 1.85; let a = 1; const leaving = isHeap && s >= m!.to && moving; if (leaving) { const e = easeOut(mk); x += (s % 2 ? 1 : -1) * e * 14 * u; y -= e * 22 * u; a = 1 - e; } g.globalAlpha = a; const gr = g.createRadialGradient(x - sr * 0.35, y - sr * 0.4, sr * 0.1, x, y, sr); gr.addColorStop(0, '#f6e7c8'); gr.addColorStop(1, isHeap && s >= m!.to && k > 0.05 ? (m!.who === 0 ? '#c89316' : '#c2415a') : '#8a7a62'); g.fillStyle = gr; g.beginPath(); g.ellipse(x, y, sr, sr * 0.8, 0, 0, TAU); g.fill(); g.globalAlpha = 1; } txt(g, String(moving && isHeap ? m!.to : n0), cx, baseY + sr + 9 * u, 8.5 * u, isHeap ? (m!.who === 0 ? C.gold : C.x) : C.text, 'center', 900); } // 이진수 표 if (bits) { const tx = w * 0.5 + 12 * u; const cw = Math.min(18 * u, (w - tx - 10 * u) / 4.2); const rh = Math.min(17 * u, (h - 50 * u) / 5.6); const ty = 32 * u; ['4', '2', '1'].forEach((s, j) => txt(g, s, tx + cw * (1.2 + j) + cw / 2, ty - 4 * u, 7 * u, C.sub, 'center', 800)); for (let i = 0; i < 4; i++) { const v = moving ? after[i]! : cur[i]!; const y = ty + 3 * u + i * rh; txt(g, String(v), tx + cw * 0.5, y + rh / 2, 8 * u, m && m.heap === i ? C.gold : C.text, 'center', 900); for (let j = 0; j < 3; j++) { const bit = (v >> (2 - j)) & 1; const bx = tx + cw * (1.2 + j) + cw / 2; g.fillStyle = bit ? '#e8ecff' : 'rgba(255,255,255,0.07)'; g.beginPath(); g.arc(bx, y + rh / 2, Math.min(cw, rh) * 0.3, 0, TAU); g.fill(); if (bit) txt(g, '1', bx, y + rh / 2 + 0.3 * u, Math.min(cw, rh) * 0.38, '#0b1020', 'center', 900); } } const yx = ty + 6 * u + 4 * rh; g.strokeStyle = 'rgba(255,255,255,0.4)'; g.lineWidth = 1 * u; g.beginPath(); g.moveTo(tx, yx - 2 * u); g.lineTo(tx + cw * 4.2, yx - 2 * u); g.stroke(); txt(g, '⊕', tx + cw * 0.5, yx + rh / 2, 8 * u, C.sub, 'center', 900); for (let j = 0; j < 3; j++) { const bit = (showX >> (2 - j)) & 1; const bx = tx + cw * (1.2 + j) + cw / 2; rr(g, bx - cw * 0.42, yx + 1 * u, cw * 0.84, rh - 2 * u, 3 * u); g.fillStyle = bit ? 'rgba(255,93,108,0.85)' : 'rgba(111,227,160,0.75)'; g.fill(); txt(g, String(bit), bx, yx + rh / 2, 8 * u, '#0b1020', 'center', 900); } pill(g, showX ? `님합 ${showX} → 두는 쪽이 이김` : '님합 0 → 상대가 짐', tx + cw * 2.1, h - 10 * u, 6.8 * u, showX ? C.red : C.green, '#0b1020'); } }, controls: [ speedCtl(st), { type: 'toggle', label: '이진수 표 보기', value: true, on: (v) => { bits = v; } }, { type: 'button', label: '새 판', on: () => { gen(); T = 0; } }, ] as Control[], }; }, }, }; ``` ## 관련 기술 - 먼저 알면 좋은 기술: [끝에서 거꾸로 푸는 완전 해법 (후퇴 분석)](https://ai-techstudio.web.app/ai/t/i349.md) `i349` - 다음에 해 볼 기술: [난이도 = 사람 같은 실수 (온도 소프트맥스)](https://ai-techstudio.web.app/ai/t/i358.md) `i358` - 참고 문서: [Wikipedia — Nim](https://en.wikipedia.org/wiki/Nim) · [Wikipedia — Sprague–Grundy theorem](https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem)