# AI 꾸러미 — 미니맥스 추측 (최악의 경우 줄이기) — Minimax guessing (Knuth strategy) > 물어볼 수마다 「대답별로 남는 후보 수」를 세어, 가장 나쁜 대답이 와도 후보가 가장 적게 남는 질문을 고른다. > 견본: https://ai-techstudio.web.app/#t/i357 이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요. ## 주문서 ### 만들어 줘: 미니맥스 추측 (최악의 경우 줄이기) — Minimax guessing (Knuth strategy) #### 1. 목표 숫자 야구 (504가지)의 컴퓨터가 미니맥스 추측으로 묻게 해 줘 — 가장 나쁜 대답에서도 후보가 가장 적게 남는 수를 부르게. 분위기는 대답별 묶음 막대로 보여 주는 설명. #### 2. 핵심 기술 용어 - **Minimax guessing (Knuth strategy)** — 최악의 대답에서 남는 후보 수를 가장 작게 - **Candidate partition (buckets)** — 대답(○S○B)마다 후보를 나눈 묶음 - **Mastermind-style deduction** — 대답으로 후보를 줄여 가는 추리 게임 #### 3. 환경 - 플랫폼: TypeScript (브라우저), 라이브러리 없이 — 화면과 떨어진 순수 함수로 - 화면: 브라우저 — PC · 폰 모두 #### 4. 조건 - 대답은 숫자 하나로 묶어(S × 4 + B) 묶음 세기를 빠르게 - 질문 후보는 「남은 후보 밖의 수」도 포함 (더 잘 나누는 수일 수 있다) - 같은 최악이면 남은 후보 안의 수를 고른다 - 첫 질문 등 후보가 많을 때는 표본으로 - 미니맥스 켬/끔(끄면 아무 후보나) 비교 #### 5. 완성 기준 (이게 보이면 성공) - 대답 묶음 막대에서 고른 수의 가장 큰 묶음이 다른 수들보다 작다 - 숫자 야구 504 후보를 거의 늘 7번 안에 맞힌다 - 미니맥스를 끄면 평균 횟수가 늘어난다 #### 6. 진행 방식 - 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘. - 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘. - 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘. - 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘. - 답변과 코드 주석은 한국어로 해 줘. ## 원리 - 숫자 야구: 1~9 서로 다른 세 자리 = 504 후보. 대답은 스트라이크 · 볼 (점수 = S × 4 + B 로 한 수에 묶음). - 부를 수 g 마다 남은 후보 c 전부와 비교해 「g 를 부르면 대답이 무엇일지」로 후보를 묶음(bucket)으로 나눈다. - 가장 큰 묶음 크기 = 그 질문의 최악. 최악이 가장 작은 g 를 부른다 — 같으면 후보 안의 수를 조금 더 좋게 (맞힐 수도 있으니, 견본 −0.5). - 진짜 대답이 오면 그 묶음만 남기고 되풀이. 후보가 많을 땐(120 넘게) 무작위 140개만 시험해 빠르게. ## 핵심 코드 — 숫자 야구 — 최악의 묶음이 가장 작은 질문 고르기 (발췌: demos/demosGameAI.ts bbScore() · bbBuckets() · I357 choose() 를 정리) ```ts const CODES: number[][] = []; for (let a = 1; a <= 9; a++) for (let b = 1; b <= 9; b++) for (let c = 1; c <= 9; c++) if (a !== b && b !== c && a !== c) CODES.push([a, b, c]); // 504가지 function score(x: number[], y: number[]): number { // S × 4 + B let s = 0, b = 0; for (let i = 0; i < 3; i++) { if (x[i] === y[i]) s++; else if (y.includes(x[i]!)) b++; } return s * 4 + b; } function worst(guess: number, cands: number[]): number { // 가장 큰 묶음 크기 const m = new Map(); for (const c of cands) { const k = score(CODES[guess]!, CODES[c]!); m.set(k, (m.get(k) ?? 0) + 1); } return Math.max(0, ...m.values()); } function choose(cands: number[]): number { if (cands.length === 1) return cands[0]!; const pool = cands.length > 120 ? Array.from({ length: 140 }, () => Math.floor(Math.random() * 504)) : Array.from({ length: 504 }, (_, i) => i); const inCands = new Set(cands); let best = cands[0]!, bw = Infinity; for (const g of pool) { const w = worst(g, cands) - (inCands.has(g) ? 0.5 : 0); // 같으면 맞힐 수도 있는 수 if (w < bw) { bw = w; best = g; } } return best; } // 대답이 오면: cands = cands.filter((c) => score(CODES[guess]!, CODES[c]!) === 대답) ``` ## 흔한 실수 · 확인 목록 - [ ] **남은 후보 안에서만 질문을 고르면 덜 나뉘는 수를 부른다** — 후보 밖의 수도 질문 후보에 넣는다 — 대신 같은 최악이면 후보 안의 수. - [ ] **첫 질문에서 504 × 504 를 다 비교하면 멈칫한다** — 표본 140개만 보거나 첫 질문은 미리 정해 둔다. - [ ] **「최악 줄이기」와 「평균 줄이기」를 헷갈린다** — 목표가 「몇 번 안에 꼭」이면 최악, 「보통 빨리」면 묶음 크기 기댓값. ## 완성 기준 체크리스트 - [ ] 대답 묶음 막대에서 고른 수의 가장 큰 묶음이 다른 수들보다 작다 - [ ] 숫자 야구 504 후보를 거의 늘 7번 안에 맞힌다 - [ ] 미니맥스를 끄면 평균 횟수가 늘어난다 ## 이 기술 정보 - id: `i357` · 분류: 게임 시스템 · AI › 게임 AI · 공통 · 난이도 보통 · 폰 부담 가벼움 (폰 OK) — 질문 후보 × 남은 후보 비교. 첫 수 504 × 504 = 25만 번 — 견본처럼 첫 질문은 140개만 시험하거나 미리 정해 둔다. - 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i357 - 쓰면 좋을 때: 대답으로 후보를 줄여 가는 추리 게임 (숫자 야구 · 마스터마인드 · 저울) / 「가장 나쁜 경우를 줄인다」는 생각을 보여 주는 수학 설명 - 쓰지 말 때: 평균 횟수를 줄이는 게 목표일 때 — 묶음 크기의 기댓값(또는 정보량)으로 고르기 / 후보가 수백만 — 일부만 표본으로 시험 ## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript) ### I357 — `src/demos/demosGameAI.ts:3516` ```ts const I357: DemoMap = { i357: { kind: '2d', caption: '504개 후보 중 무엇을 부를까? — 대답(○S○B)마다 남는 후보 수를 세어 「가장 나쁜 대답이어도 가장 적게 남는」 수를 불러요 (미니맥스)', make() { let mini = true; let secret = 0; let cands: number[] = []; let turn = 0; let guess = 0; let trial: [number, number][] = []; let buckets = new Map(); let resp = 0; let phase = 0; let pT = 0; const st = { speed: 1 }; let r = rng(newSeed()); let fadeFrom: number[] = []; const choose = (): void => { const pool = cands.length > 1 ? (cands.length > 120 ? Array.from({ length: 140 }, () => Math.floor(r() * 504)) : Array.from({ length: 504 }, (_, i) => i)) : cands; trial = []; if (!mini) { guess = cands[Math.floor(r() * cands.length)]!; for (let k = 0; k < 6; k++) { const gq = Math.floor(r() * 504); trial.push([gq, worstOf(bbBuckets(gq, cands))]); } } else { const candSet = new Set(cands); let best = cands[0]!; let bw = Infinity; for (const gq of pool) { const wv = worstOf(bbBuckets(gq, cands)) - (candSet.has(gq) ? 0.5 : 0); if (wv < bw) { bw = wv; best = gq; } } for (let k = 0; k < 6; k++) { const gq = pool[Math.floor(r() * pool.length)]!; trial.push([gq, worstOf(bbBuckets(gq, cands))]); } guess = best; } trial.push([guess, worstOf(bbBuckets(guess, cands))]); buckets = bbBuckets(guess, cands); resp = bbScore(BB_CODES[guess]!, BB_CODES[secret]!); }; const restart = (): void => { r = rng(newSeed()); secret = Math.floor(r() * 504); cands = Array.from({ length: 504 }, (_, i) => i); fadeFrom = cands.slice(); turn = 1; phase = 0; pT = 0; choose(); }; restart(); const DUR = [1.7, 0.7, 0.8, 1.0, 2.6]; return { draw(g, w, h, t, dt) { reset(g); pT += Math.min(dt, 0.1) * st.speed; if (pT > DUR[phase]!) { pT = 0; if (phase === 3) { fadeFrom = cands; if (resp === 12) phase = 4; else { cands = cands.filter((c) => bbScore(BB_CODES[guess]!, BB_CODES[c]!) === resp); turn++; phase = 0; choose(); } } else if (phase === 4) restart(); else phase++; if (phase === 3 && resp !== 12) { // 걸러질 후보 미리 } } const u = scaleOf(w, h); bg(g, w, h); const alive = new Set(phase >= 3 ? cands.filter((c) => bbScore(BB_CODES[guess]!, BB_CODES[c]!) === resp) : cands); const prev = new Set(fadeFrom); header(g, w, u, mini ? '미니맥스 추측' : '아무 후보나 부르기', mini ? C.text : C.sub, `${turn}번째 · 후보 ${phase >= 3 ? alive.size : cands.length}`, C.gold); // 점 격자 28 × 18 const gw = w * 0.47; const cs = Math.min((gw - 10 * u) / 28, (h - 30 * u) / 18); const gx = 8 * u; const gy = 24 * u; const fk = phase === 3 ? easeOut(pT / DUR[3]!) : 1; for (let i = 0; i < 504; i++) { const x = gx + (i % 28) * cs + cs / 2; const y = gy + Math.floor(i / 28) * cs + cs / 2; let col = 'rgba(90,100,140,0.25)'; let rad = cs * 0.22; if (alive.has(i)) { col = phase === 4 ? C.gold : C.o; rad = cs * 0.34; } else if (prev.has(i) && phase === 3) { col = `rgba(255,93,108,${(1 - fk) * 0.9 + 0.1})`; rad = cs * lerp(0.34, 0.22, fk); } if (i === guess && phase >= 1) { g.strokeStyle = '#fff'; g.lineWidth = 1 * u; g.beginPath(); g.arc(x, y, cs * 0.5, 0, TAU); g.stroke(); } g.fillStyle = col; g.beginPath(); g.arc(x, y, rad, 0, TAU); g.fill(); } // 오른쪽 위: 부를 수 고르기 const rx = gx + 28 * cs + 14 * u; const rw = w - rx - 8 * u; if (phase === 0) { txt(g, '이 수를 부르면 최악엔 몇 개 남나?', rx, 28 * u, 6.8 * u, C.sub, 'left', 700); const shownN = Math.min(trial.length, 1 + Math.floor((pT / DUR[0]!) * trial.length)); for (let k = 0; k < shownN; k++) { const [gq, wv] = trial[k]!; const y = 40 * u + k * 10.5 * u; const isBest = k === trial.length - 1; txt(g, BB_CODES[gq]!.join(''), rx + 2 * u, y, 8 * u, isBest ? C.gold : C.text, 'left', 900); const bw = (rw - 52 * u) * (wv / Math.max(...trial.map((q) => q[1]))); rr(g, rx + 26 * u, y - 3 * u, Math.max(1, bw), 6 * u, 2 * u); g.fillStyle = isBest ? C.gold : 'rgba(255,93,108,0.7)'; g.fill(); txt(g, String(wv), rx + 30 * u + bw, y, 6.5 * u, isBest ? C.gold : C.sub, 'left', 800); } } else { // 부른 수 · 대답 칸 const digits = BB_CODES[guess]!; const bs = Math.min(18 * u, rw / 4.5); digits.forEach((dgt, k) => { const x = rx + bs / 2 + k * (bs * 1.15); const y = 34 * u; const gr = g.createRadialGradient(x - bs * 0.15, y - bs * 0.18, bs * 0.05, x, y, bs * 0.5); gr.addColorStop(0, '#ffffff'); gr.addColorStop(1, '#d8dbe6'); g.fillStyle = gr; g.beginPath(); g.arc(x, y, bs * 0.46, 0, TAU); g.fill(); g.strokeStyle = 'rgba(214,40,69,0.75)'; g.lineWidth = 0.9 * u; g.beginPath(); g.arc(x - bs * 0.52, y, bs * 0.38, -0.7, 0.7); g.arc(x + bs * 0.52, y, bs * 0.38, Math.PI - 0.7, Math.PI + 0.7); g.stroke(); txt(g, String(dgt), x, y + 0.5 * u, bs * 0.5, '#1b2036', 'center', 900); }); if (phase >= 2) pill(g, phase === 4 ? '3S 정답!' : bbLabel(resp), rx + bs * 3.6 + 6 * u, 34 * u, 8 * u, phase === 4 ? C.gold : C.green, '#0b1020', 'left'); // 대답별 남는 수 막대 const by = 54 * u; const bh = h - by - 18 * u; const mxv = Math.max(1, ...buckets.values()); const cw = rw / BB_KEYS.length; const worst = worstOf(buckets); BB_KEYS.forEach((k, i) => { const v = buckets.get(k) ?? 0; const x = rx + i * cw; const hh = (v / mxv) * (bh - 10 * u); const isResp = phase >= 2 && k === resp; g.fillStyle = isResp ? C.green : v === worst ? C.red : 'rgba(141,151,196,0.6)'; rr(g, x + cw * 0.15, by + bh - hh, cw * 0.7, hh, 1.5 * u); g.fill(); if (v) txt(g, String(v), x + cw / 2, by + bh - hh - 4 * u, 5.5 * u, isResp ? C.green : C.sub, 'center', 800); txt(g, bbLabel(k), x + cw / 2, by + bh + 6 * u, Math.min(5.2 * u, cw * 0.32), isResp ? C.green : C.dim, 'center', 700); }); txt(g, `최악 ${worst}개 남음`, rx, by - 4 * u, 6.5 * u, C.red, 'left', 800); } void t; }, controls: [ speedCtl(st), { type: 'toggle', label: '미니맥스로 고르기 (끄면 아무 후보나)', value: true, on: (v) => { mini = v; restart(); } }, { type: 'button', label: '새 비밀 수', on: () => restart() }, ] as Control[], }; }, }, }; ``` ## 관련 기술 - 먼저 알면 좋은 기술: [미니맥스 게임 나무](https://ai-techstudio.web.app/ai/t/i340.md) `i340` - 다음에 해 볼 기술: [난이도 = 사람 같은 실수 (온도 소프트맥스)](https://ai-techstudio.web.app/ai/t/i358.md) `i358` - 참고 문서: [Wikipedia — Mastermind (board game)](https://en.wikipedia.org/wiki/Mastermind_(board_game))