# AI 꾸러미 — 끝에서 거꾸로 푸는 완전 해법 (후퇴 분석) — Retrograde analysis > 끝난 자리부터 거꾸로 — 지는 칸으로 갈 수 있으면 이기는 칸, 모든 수가 이기는 칸으로만 가면 지는 칸 — 으로 모든 자리의 승패 표를 만든다. > 견본: https://ai-techstudio.web.app/#t/i349 이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요. ## 주문서 ### 만들어 줘: 끝에서 거꾸로 푸는 완전 해법 (후퇴 분석) — Retrograde analysis #### 1. 목표 퀸 구석으로 (위토프 게임)의 모든 자리 승패를 끝에서 거꾸로 푸는 후퇴 분석으로 구해 줘. 분위기는 칸이 하나씩 금빛 · 초록으로 칠해지는 설명. #### 2. 핵심 기술 용어 - **Retrograde analysis** — 끝에서 거꾸로 모든 자리의 승패 정하기 - **P-position / N-position** — 지는 자리(앞사람 승) · 이기는 자리(둘 차례 승) - **Wythoff game** — 퀸을 왼쪽 · 아래 · 왼아래로 옮겨 구석에 넣는 게임 #### 3. 환경 - 플랫폼: TypeScript (브라우저), 라이브러리 없이 — 화면과 떨어진 순수 함수로 - 화면: 브라우저 — PC · 폰 모두 #### 4. 조건 - 순서가 핵심: 어떤 칸을 정할 때 그 칸에서 갈 수 있는 칸은 이미 다 정해져 있어야 한다 (견본은 x + y 순) - 이기는 칸마다 「어디로 가면 되는지」(목표 칸)도 저장 - 설명 화면: 칸이 하나씩 정해지는 애니메이션 + 지금 칸에서 갈 수 있는 길 + 다 풀면 규칙선 - 판 크기 슬라이더 (견본 가로 10~34) #### 5. 완성 기준 (이게 보이면 성공) - 구석(⌂)부터 대각선 순으로 칸이 금빛(지는 칸) · 초록(이기는 칸)으로 칠해진다 - 이기는 칸에서 금빛 칸으로 가는 화살표가 늘 하나 이상 있다 - 다 풀면 금빛 칸이 φ 기울기 두 선 위에 놓인 것이 보인다 #### 6. 진행 방식 - 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘. - 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘. - 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘. - 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘. - 답변과 코드 주석은 한국어로 해 줘. ## 원리 - 끝난 자리(더 둘 수 없음 = 앞사람이 이김)는 「지는 칸」이다 — 견본은 구석 (0, 0). - 구석에서 가까운 칸부터(x + y 가 작은 순) 차례로: 한 번에 갈 수 있는 칸 중 지는 칸이 하나라도 있으면 「이기는 칸」 — 거기로 가면 된다. - 갈 수 있는 칸이 모두 이기는 칸이면 「지는 칸」. - 모든 칸을 정하면 완벽한 AI 가 된다: 이기는 칸에선 지는 칸으로 옮기기만 하면 된다. - 위토프 게임의 지는 칸은 기울기 φ ≈ 1.618 과 1/φ 두 선 위에 늘어선다 — 견본은 다 풀고 그 선을 그린다. ## 핵심 코드 — 퀸 구석으로 — 구석부터 거꾸로 승패 표 만들기 (발췌: demos/demosGameAI.ts I349 의 build() 를 정리) ```ts // stat: 0 모름 · 1 이기는 칸 · 2 지는 칸, target: 이기는 칸에서 갈 지는 칸 function solveWythoff(W: number, H: number): { stat: Int8Array; target: Int32Array } { const stat = new Int8Array(W * H); const target = new Int32Array(W * H).fill(-1); // 구석에서 가까운 순 (x + y 가 작은 칸부터) — 갈 수 있는 칸은 늘 먼저 정해져 있다 for (let s = 0; s < W + H; s++) for (let x = 0; x < W; x++) { const y = s - x; if (y < 0 || y >= H) continue; const id = y * W + x; let tg = -1; for (let k = 1; k <= Math.max(x, y) && tg < 0; k++) { if (x - k >= 0 && stat[y * W + x - k] === 2) tg = y * W + x - k; // 왼쪽 else if (y - k >= 0 && stat[(y - k) * W + x] === 2) tg = (y - k) * W + x; // 아래 else if (x - k >= 0 && y - k >= 0 && stat[(y - k) * W + x - k] === 2) tg = (y - k) * W + x - k; // 왼아래 } stat[id] = tg >= 0 ? 1 : 2; // 지는 칸으로 갈 수 있으면 이기는 칸, 아니면 지는 칸 (구석 = 지는 칸) target[id] = tg; } return { stat, target }; } // AI: stat[지금] === 1 이면 target[지금] 으로 옮긴다. 2 면 아무 수나 (지는 자리) ``` ## 흔한 실수 · 확인 목록 - [ ] **칸을 아무 순서로 정하면 아직 모르는 칸을 「지는 칸 아님」으로 착각한다** — 갈 수 있는 칸이 모두 먼저 정해지는 순서(여기선 x + y)로 돈다. - [ ] **수가 순환하는 게임에 그대로 쓰면 틀린다** — 「아직 안 정해진 자식 수」를 세어 0 이 되면 지는 칸으로 정하는 큐 방식으로 바꾼다. - [ ] **지는 자리에서 AI 가 늘 같은 수를 둔다** — 지는 자리에선 상대가 실수할 여지가 큰 수(오래 버티는 수)를 고르면 더 사람 같다. ## 완성 기준 체크리스트 - [ ] 구석(⌂)부터 대각선 순으로 칸이 금빛(지는 칸) · 초록(이기는 칸)으로 칠해진다 - [ ] 이기는 칸에서 금빛 칸으로 가는 화살표가 늘 하나 이상 있다 - [ ] 다 풀면 금빛 칸이 φ 기울기 두 선 위에 놓인 것이 보인다 ## 이 기술 정보 - id: `i349` · 분류: 게임 시스템 · AI › 게임 AI · 공통 · 난이도 보통 · 폰 부담 가벼움 (폰 OK) — 칸마다 갈 수 있는 수를 한 번씩 본다. 18×11 판 = 198칸 × 최대 수십 수 — 순식간. 결과 표는 미리 구워 둘 수 있다. - 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i349 - 쓰면 좋을 때: 자리 수가 표로 담길 만큼 작은 게임 (수천 ~ 수백만) / 「이기는 규칙」을 발견하는 수학 체험 - 쓰지 말 때: 자리 수가 너무 큰 게임 — 탐색 AI(i341 · i347) / 수가 순환하는 게임(같은 자리로 돌아옴) — 「모든 자식이 정해질 때까지」 세는 방식으로 바꿔야 한다 ## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript) ### I349 — `src/demos/demosGameAI.ts:2045` ```ts const I349: DemoMap = { i349: { kind: '2d', caption: '퀸을 왼쪽 · 아래 · 왼아래로 옮겨 구석(⌂)에 넣으면 승 — 구석부터 거꾸로: 「지는 칸(금빛)으로 갈 수 있으면 이기는 칸」, 지는 칸은 황금비 선 위에 늘어서요', make() { let W = 18; let H = 11; let order: number[] = []; let stat: Int8Array = new Int8Array(0); let target: Int32Array = new Int32Array(0); let rays = true; const build = (): void => { order = []; for (let s = 0; s < W + H; s++) for (let x = 0; x < W; x++) { const y = s - x; if (y >= 0 && y < H) order.push(y * W + x); } stat = new Int8Array(W * H); target = new Int32Array(W * H).fill(-1); for (const id of order) { const x = id % W; const y = Math.floor(id / W); let tg = -1; for (let k = 1; k <= Math.max(x, y) && tg < 0; k++) { if (x - k >= 0 && stat[y * W + x - k] === 2) tg = y * W + x - k; else if (y - k >= 0 && stat[(y - k) * W + x] === 2) tg = (y - k) * W + x; else if (x - k >= 0 && y - k >= 0 && stat[(y - k) * W + x - k] === 2) tg = (y - k) * W + x - k; } stat[id] = tg >= 0 ? 1 : 2; target[id] = tg; } }; build(); const seq = new Seq(order.length, 38, 3.4, () => seq.restart(order.length)); let demoCell = -1; return { draw(g, w, h, _t, dt) { reset(g); seq.tick(dt); const u = scaleOf(w, h); bg(g, w, h); const done = seq.done; const n = seq.i; header(g, w, u, '후퇴 분석', C.text, done ? '다 풀었다 — 모든 칸의 승패' : `푼 칸 ${n} / ${order.length}`, done ? C.gold : C.sub); const cs = Math.min((w - 16 * u) / W, (h - 30 * u) / H); const ox = (w - cs * W) / 2; const oy = 22 * u + (h - 26 * u - cs * H) / 2; const P = (x: number, y: number): [number, number] => [ox + x * cs + cs / 2, oy + (H - 1 - y) * cs + cs / 2]; const known = new Int8Array(W * H); for (let i = 0; i < n; i++) known[order[i]!] = stat[order[i]!]!; for (let y = 0; y < H; y++) for (let x = 0; x < W; x++) { const id = y * W + x; const k = known[id]!; const [px, py] = P(x, y); rr(g, px - cs / 2 + 0.6 * u, py - cs / 2 + 0.6 * u, cs - 1.2 * u, cs - 1.2 * u, cs * 0.18); g.fillStyle = k === 2 ? C.gold : k === 1 ? '#22533f' : (x + y) % 2 ? '#1a2136' : '#1e263e'; g.fill(); if (k === 2) { const idx = order.indexOf(id); const age = n - idx; if (age < 12) glow(g, px, py, cs * 1.6, C.gold, 0.5 * (1 - age / 12)); } } const [hx, hy] = P(0, 0); txt(g, '⌂', hx, hy + 0.3 * u, cs * 0.7, '#3a2a00', 'center', 900); // 지금 칸 if (!done && n < order.length) { const id = order[n]!; const x = id % W; const y = Math.floor(id / W); const [px, py] = P(x, y); if (rays) { g.strokeStyle = 'rgba(255,255,255,0.28)'; g.lineWidth = 1.2 * u; g.beginPath(); g.moveTo(px, py); g.lineTo(...P(0, y)); g.moveTo(px, py); g.lineTo(...P(x, 0)); const m = Math.min(x, y); g.moveTo(px, py); g.lineTo(...P(x - m, y - m)); g.stroke(); } const tg = target[id]!; if (tg >= 0 && seq.frac > 0.2) { const [tx, ty] = P(tg % W, Math.floor(tg / W)); arrow(g, px, py, tx, ty, C.green, 1.6 * u, 5 * u); } g.strokeStyle = '#fff'; g.lineWidth = 1.5 * u; g.strokeRect(px - cs / 2, py - cs / 2, cs, cs); } if (done) { const phi = (1 + Math.sqrt(5)) / 2; g.setLineDash([3 * u, 2.5 * u]); g.strokeStyle = 'rgba(255,240,190,0.75)'; g.lineWidth = 1.2 * u; g.beginPath(); g.moveTo(...P(0, 0)); g.lineTo(...P(Math.min(W - 1, (H - 1) / phi), Math.min(H - 1, (W - 1) * phi))); g.moveTo(...P(0, 0)); g.lineTo(...P(Math.min(W - 1, (H - 1) * phi), Math.min(H - 1, (W - 1) / phi))); g.stroke(); g.setLineDash([]); // 이기는 수 보여 주기 const k = Math.floor(seq.holdT / 1.1); const rr0 = rng(k + 7); if (demoCell < 0 || seq.holdT % 1.1 < 0.03) { let c0 = -1; for (let tries = 0; tries < 50 && c0 < 0; tries++) { const c1 = Math.floor(rr0() * W * H); if (stat[c1] === 1) c0 = c1; } demoCell = c0; } if (demoCell >= 0) { const [px, py] = P(demoCell % W, Math.floor(demoCell / W)); const tg = target[demoCell]!; const [tx, ty] = P(tg % W, Math.floor(tg / W)); arrow(g, px, py, tx, ty, '#fff', 1.6 * u, 5 * u); glyph(g, '♛', px, py, cs * 0.95, '#fff', '#1a1430'); } pill(g, '금빛 = 지는 칸 · 기울기 φ ≈ 1.618', w - 8 * u, h - 8 * u, 6.8 * u, 'rgba(255,209,102,0.95)', '#1a1405', 'right'); } }, controls: [ speedCtl(seq, 6), { type: 'toggle', label: '퀸이 갈 수 있는 길 보기', value: true, on: (v) => { rays = v; } }, { type: 'range', label: '판 가로 크기', min: 10, max: 34, step: 1, value: 18, on: (v) => { W = v; H = Math.round(v * 0.6); build(); seq.restart(order.length); } }, { type: 'button', label: '다시', on: () => seq.restart(order.length) }, ] as Control[], }; }, }, }; ``` ## 관련 기술 - 먼저 알면 좋은 기술: [미니맥스 게임 나무](https://ai-techstudio.web.app/ai/t/i340.md) `i340` - 다음에 해 볼 기술: [님합 · 그런디 수 (게임 이론)](https://ai-techstudio.web.app/ai/t/i350.md) `i350` - 참고 문서: [Wikipedia — Retrograde analysis](https://en.wikipedia.org/wiki/Retrograde_analysis) · [Wikipedia — Wythoff’s game](https://en.wikipedia.org/wiki/Wythoff%27s_game)