# AI 꾸러미 — 반복 심화 + 시간 예산 — Iterative deepening > 깊이 1, 2, 3 … 차례로 끝까지 탐색하며 끝난 깊이의 최선 수를 늘 들고 있다가, 시간이 다 되면 하던 깊이는 버리고 그 수를 둔다. > 견본: https://ai-techstudio.web.app/#t/i343 이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요. ## 주문서 ### 만들어 줘: 반복 심화 + 시간 예산 — Iterative deepening #### 1. 목표 오목 · 체스 AI의 AI 에 반복 심화 + 시간 예산을 넣어 줘 — 정해진 시간 안에 늘 수를 두게. 분위기는 시간 줄로 깊이마다 막대를 보여 주는 설명. #### 2. 핵심 기술 용어 - **Iterative deepening** — 깊이를 1씩 늘리며 처음부터 다시 찾기 - **Time budget (time management)** — 한 수에 쓸 시간 — 넘으면 멈춤 - **Anytime algorithm** — 언제 멈춰도 그때까지의 가장 좋은 답이 있다 #### 3. 환경 - 플랫폼: TypeScript (브라우저), 라이브러리 없이 — 화면과 떨어진 순수 함수로 - 화면: 브라우저 — PC · 폰 모두 #### 4. 조건 - 시간 검사는 탐색 안에서도 (깊이 사이에서만 보면 마지막 깊이가 예산을 크게 넘긴다) - 시간이 다 되면 하던 깊이 결과는 버리고 끝난 깊이의 수를 쓴다 - 앞 깊이의 최선 수를 다음 깊이에서 가장 먼저 탐색 - 예산은 난이도별로 (견본 0.7 · 2.0 · 4.6초 자동 순환, 0.3~5 슬라이더) - 탐색은 워커에서 — 생각하는 동안 화면이 멈추지 않게(i359) #### 5. 완성 기준 (이게 보이면 성공) - 시간 줄에 깊이 1 · 2 · 3 … 막대가 점점 길게 쌓이고, 예산 선을 넘은 막대는 「버림」으로 표시된다 - 둔 수는 마지막으로 끝난 깊이의 ★ 수와 같다 - 예산을 늘리면 끝난 깊이가 커진다 - 어떤 판에서도 예산 + 소량 안에 수를 둔다 #### 6. 진행 방식 - 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘. - 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘. - 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘. - 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘. - 답변과 코드 주석은 한국어로 해 줘. ## 원리 - 깊이 1 을 끝까지 → 최선 수 저장 → 깊이 2 를 끝까지 → 저장 … 을 시간이 남는 동안 되풀이한다. - 탐색 중 시간이 다 되면 하던 깊이는 결과가 반쪽이니 버리고, 마지막으로 끝난 깊이의 수를 둔다. - 깊이가 1 늘면 시간이 대략 가지 수배로 는다 (견본은 × 3) — 그래서 앞 깊이들을 다시 하는 비용은 전체의 일부뿐. - 앞 깊이의 최선 수를 다음 깊이에서 먼저 보면 알파베타가 더 많이 잘라 오히려 빨라진다. ## 핵심 코드 — 반복 심화 + 시간 예산 (알파베타를 감싸는 꼴) (발췌: 새로 씀 (demos/demosGameAI.ts i343 견본의 「깊이 +1 → 시간 ×3 · 끝난 깊이의 수를 둔다」 규칙과 같은 방식)) ```ts class TimeUp extends Error {} function think(g: Game, s: S, budgetMs: number): { move: M | undefined; depth: number } { const deadline = performance.now() + budgetMs; let nodes = 0; let best: M | undefined; let done = 0; const search = (st: S, depth: number, a: number, b: number, max: boolean): number => { if ((++nodes & 1023) === 0 && performance.now() > deadline) throw new TimeUp(); // 탐색 안에서도 시간 검사 if (depth === 0 || g.over(st)) return g.score(st); let v = max ? -Infinity : Infinity; for (const m of g.moves(st)) { const c = search(g.play(st, m), depth - 1, a, b, !max); 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; }; try { for (let depth = 1; depth <= 64; depth++) { // 앞 깊이의 최선 수를 맨 앞으로 — 더 많이 잘린다 const ms = g.moves(s).sort((x, y) => (x === best ? -1 : y === best ? 1 : 0)); let bm: M | undefined, a = -Infinity; for (const m of ms) { const v = search(g.play(s, m), depth - 1, a, Infinity, false); if (v > a) { a = v; bm = m; } } best = bm; // 이 깊이를 끝까지 마쳤을 때만 바꾼다 done = depth; } } catch (e) { if (!(e instanceof TimeUp)) throw e; // 시간 끝 — 하던 깊이는 버림 } return { move: best, depth: done }; } ``` ## 흔한 실수 · 확인 목록 - [ ] **깊이 사이에서만 시간을 보면 마지막 깊이가 예산을 몇 배 넘긴다** — 탐색 안에서 마디 1024개마다 시간을 보고 넘으면 바로 빠져나온다. - [ ] **시간이 끝난 깊이의 반쪽 결과를 쓰면 엉뚱한 수를 둔다** — 그 깊이는 버리고 마지막으로 끝까지 마친 깊이의 수를 쓴다. - [ ] **깊이 1 조차 못 끝내면 둘 수가 없다** — 깊이 1 은 시간과 상관없이 끝내거나, 수 목록의 첫 수를 기본값으로 들고 시작한다. ## 완성 기준 체크리스트 - [ ] 시간 줄에 깊이 1 · 2 · 3 … 막대가 점점 길게 쌓이고, 예산 선을 넘은 막대는 「버림」으로 표시된다 - [ ] 둔 수는 마지막으로 끝난 깊이의 ★ 수와 같다 - [ ] 예산을 늘리면 끝난 깊이가 커진다 - [ ] 어떤 판에서도 예산 + 소량 안에 수를 둔다 ## 이 기술 정보 - id: `i343` · 분류: 게임 시스템 · AI › 게임 AI · 공통 · 난이도 쉬움 · 폰 부담 보통 (폰 주의) — 앞 깊이를 다시 하는 비용은 가지 수가 3 이면 약 50%, 10 이면 약 11% 더. 시간 검사는 마디 수천 개마다 한 번만. - 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i343 - 쓰면 좋을 때: 판마다 경우의 수가 크게 달라 고정 깊이로는 시간이 들쭉날쭉할 때 / 난이도를 「생각 시간」으로 나눌 때 (유아 0.3초 ~ 고수 2초) - 쓰지 말 때: 틱택토처럼 끝까지 바로 보는 작은 게임 — 그냥 미니맥스(i340) / 몬테카를로 트리 탐색 — 그건 반복 횟수 자체가 시간 예산이라 따로 필요 없다(i347) ## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript) ### i343 견본 항목 — `src/demos/demosGameAI.ts:903` ```ts i343: { kind: '2d', caption: '깊이 1 → 2 → 3 … 차례로 끝까지 — 끝난 깊이의 최선 수를 늘 들고 있다가, 시간이 다 되면 하던 깊이는 버리고 그 수를 둬요', make() { const presets = [2.0, 0.7, 4.6]; let pi = 0; let budget = presets[0]!; let auto = true; let tau = 0; const st = { speed: 1 }; const BASE = 0.045; const cost = (d: number): number => BASE * Math.pow(3, d - 1); let seed = newSeed(); let stones: [number, number, boolean][] = []; let cands: number[] = []; let bestOf: number[] = []; const N = 9; const setup = (): void => { const r = rng(seed); stones = []; const used = new Set(); for (let k = 0; k < 12; k++) { const x = 2 + Math.floor(r() * 5); const y = 2 + Math.floor(r() * 5); if (used.has(y * N + x)) continue; used.add(y * N + x); stones.push([x, y, k % 2 === 0]); } cands = []; while (cands.length < 4) { const x = 1 + Math.floor(r() * 7); const y = 1 + Math.floor(r() * 7); if (!used.has(y * N + x) && !cands.includes(y * N + x)) cands.push(y * N + x); } bestOf = [0]; for (let d = 1; d <= 8; d++) bestOf.push(r() < 0.55 && d > 1 ? bestOf[d - 1]! : Math.floor(r() * 4)); }; setup(); const restart = (): void => { tau = 0; seed = newSeed(); setup(); }; return { draw(g, w, h, _t, dt) { reset(g); tau += Math.min(dt, 0.1) * st.speed; if (tau > budget + 2.4) { if (auto) { pi = (pi + 1) % presets.length; budget = presets[pi]!; } restart(); } const u = scaleOf(w, h); bg(g, w, h); const now = Math.min(tau, budget); // 깊이별 시작 · 끝 const starts: number[] = []; const ends: number[] = []; let cum = 0; let doneD = 0; let curD = 1; for (let d = 1; d <= 8; d++) { starts[d] = cum; cum += cost(d); ends[d] = cum; if (ends[d]! <= now) doneD = d; else if (starts[d]! <= now) curD = d; } const timeUp = tau >= budget; header(g, w, u, '반복 심화', C.text, `시간 예산 ${budget.toFixed(1)}초`, C.gold); // 왼쪽 판 const bs = Math.min(h - 32 * u, w * 0.4); const bx = 8 * u; const by = 24 * u; const c = goBoard(g, bx, by, bs, N); for (const [x, y, bl] of stones) stone(g, bx + c / 2 + x * c, by + c / 2 + y * c, c * 0.43, bl); cands.forEach((cell, k) => { const x = bx + c / 2 + (cell % N) * c; const y = by + c / 2 + Math.floor(cell / N) * c; g.strokeStyle = 'rgba(30,20,10,0.5)'; g.setLineDash([1.5 * u, 1.5 * u]); g.lineWidth = 1 * u; g.beginPath(); g.arc(x, y, c * 0.36, 0, TAU); g.stroke(); g.setLineDash([]); txt(g, 'ABCD'[k]!, x, y + 0.3 * u, c * 0.42, 'rgba(40,25,10,0.75)', 'center', 900); }); if (doneD > 0) { const cell = cands[bestOf[doneD]!]!; const x = bx + c / 2 + (cell % N) * c; const y = by + c / 2 + Math.floor(cell / N) * c; const lastEnd = ends[doneD]!; const pop = back((now - lastEnd) / 0.25); glow(g, x, y, c * 1.6, C.gold, 0.7); stone(g, x, y, c * 0.43 * (timeUp ? 1 : 0.85 + 0.15 * pop), true, timeUp ? 1 : 0.55); g.strokeStyle = C.gold; g.lineWidth = 1.8 * u; g.beginPath(); g.arc(x, y, c * 0.55, 0, TAU); g.stroke(); } const cap = timeUp ? `깊이 ${doneD} 의 수를 둔다` : doneD ? `들고 있는 수: 깊이 ${doneD}` : '생각 중…'; pill(g, cap, bx + bs / 2, by + bs + 7 * u, 7 * u, timeUp ? C.gold : 'rgba(255,255,255,0.14)', timeUp ? '#1a1405' : C.text); // 오른쪽 시간 줄 const rx = bx + bs + 14 * u; const rw = w - rx - 8 * u; const maxT = Math.max(budget * 1.18, 0.5); const X = (tt: number): number => rx + 26 * u + (tt / maxT) * (rw - 26 * u); const showD = Math.min(8, Math.max(doneD + 1, curD) + (timeUp ? 0 : 0)); const rowH = Math.min(15 * u, (h - 50 * u) / Math.max(4, showD)); const ry = 30 * u; // 예산 선 const bxl = X(budget); g.fillStyle = 'rgba(255,93,108,0.08)'; g.fillRect(bxl, ry - 6 * u, X(maxT) - bxl, rowH * showD + 8 * u); g.strokeStyle = C.red; g.lineWidth = 1.4 * u; g.setLineDash([3 * u, 2 * u]); g.beginPath(); g.moveTo(bxl, ry - 6 * u); g.lineTo(bxl, ry + rowH * showD + 2 * u); g.stroke(); g.setLineDash([]); txt(g, '시간 끝', bxl, ry - 9 * u, 6.5 * u, C.red, 'center', 800); for (let d = 1; d <= showD; d++) { const y = ry + (d - 1) * rowH; txt(g, `깊이 ${d}`, rx, y + rowH / 2, 7 * u, d <= doneD ? C.text : C.sub, 'left', 800); const s0 = starts[d]!; const e0 = ends[d]!; const e1 = Math.min(e0, now); if (e1 <= s0) continue; const abandoned = timeUp && e0 > budget; const x0 = X(s0); const x1 = Math.max(x0 + 1.5 * u, X(e1)); rr(g, x0, y + rowH * 0.18, x1 - x0, rowH * 0.64, 2 * u); g.fillStyle = abandoned ? 'rgba(120,128,160,0.35)' : d <= doneD ? C.green : C.o; g.fill(); if (abandoned) { g.save(); g.clip(); g.strokeStyle = 'rgba(255,93,108,0.6)'; g.lineWidth = 1 * u; for (let k = -20; k < 60; k++) { g.beginPath(); g.moveTo(x0 + k * 4 * u, y); g.lineTo(x0 + k * 4 * u + rowH, y + rowH); g.stroke(); } g.restore(); txt(g, '버림', Math.min(x1, X(maxT)) - 3 * u, y + rowH / 2, 6.5 * u, C.red, 'right', 900); } else if (d <= doneD) { txt(g, `★${'ABCD'[bestOf[d]!]}`, x1 + 2 * u, y + rowH / 2, 6.5 * u, C.gold, 'left', 900); } } // 지금 시각 바늘 const nx = X(now); g.strokeStyle = '#fff'; g.lineWidth = 1 * u; g.beginPath(); g.moveTo(nx, ry - 4 * u); g.lineTo(nx, ry + rowH * showD); g.stroke(); txt(g, `${now.toFixed(2)}초`, rx + rw, h - 9 * u, 7 * u, C.sub, 'right', 700); txt(g, '깊이 +1 → 시간 ×3', rx, h - 9 * u, 7 * u, C.sub, 'left', 700); }, controls: [ speedCtl(st), { type: 'range', label: '시간 예산 (초)', min: 0.3, max: 5, step: 0.1, value: 2, on: (v) => { budget = v; auto = false; restart(); } }, { type: 'toggle', label: '예산 자동으로 바꾸기', value: true, on: (v) => { auto = v; } }, { type: 'button', label: '다시', on: () => restart() }, ] as Control[], }; }, } ``` ## 관련 기술 - 먼저 알면 좋은 기술: [알파베타 가지치기](https://ai-techstudio.web.app/ai/t/i341.md) `i341` - 다음에 해 볼 기술: [같은 판 기억 (전치표 · 조브리스트 해시)](https://ai-techstudio.web.app/ai/t/i344.md) `i344` · [화면 안 멈추는 계산 (Web Worker)](https://ai-techstudio.web.app/ai/t/i359.md) `i359` - 참고 문서: [Chessprogramming wiki — Iterative Deepening](https://www.chessprogramming.org/Iterative_Deepening) · [Wikipedia — Iterative deepening depth-first search](https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search)