# AI 꾸러미 — 정지 탐색 (수평선 효과 막기) — Quiescence search > 깊이 끝에서 바로 평가하지 않고 잡기가 끝나 판이 조용해질 때까지 잡는 수만 더 봐서, 「공짜 룩!」 같은 수평선 착각을 막는다. > 견본: https://ai-techstudio.web.app/#t/i345 이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요. ## 주문서 ### 만들어 줘: 정지 탐색 (수평선 효과 막기) — Quiescence search #### 1. 목표 체스 · 장기 AI의 알파베타 끝에 정지 탐색을 넣어 줘 — 깊이 끝에서 잡기가 끝날 때까지 더 보게. 분위기는 깊이 1 에서 멈춤 vs 정지 탐색을 나란히 보여 주는 설명. #### 2. 핵심 기술 용어 - **Quiescence search** — 조용한 판이 될 때까지 잡기만 더 보기 - **Horizon effect** — 탐색 깊이 바로 너머의 손해를 못 보는 착각 - **Stand pat** — 「안 잡고 지금 점수로 멈춤」도 고를 수 있다는 기준값 #### 3. 환경 - 플랫폼: TypeScript (브라우저), 라이브러리 없이 — 화면과 떨어진 순수 함수로 - 화면: 브라우저 — PC · 폰 모두 #### 4. 조건 - 알파베타의 깊이 0 자리에서 평가 대신 정지 탐색을 부른다 - stand pat 으로 시작해 α · β 가지치기를 정지 탐색 안에서도 - 정지 탐색에도 최대 깊이(예: 8)를 둔다 - 잡는 수는 「큰 말을 싼 말로 잡기」부터 정렬 - 설명 화면이면 왼쪽 깊이 1 · 오른쪽 정지 탐색을 같은 판에서 나란히 #### 5. 완성 기준 (이게 보이면 성공) - 왼쪽(깊이 1)은 룩을 잡고 다음 수에 퀸을 잃어 평가가 +5 → −4 로 떨어진다 - 오른쪽(정지 탐색)은 룩 줄을 끝까지 보고 −4 를 알아내 나이트(+3)를 고른다 - 같은 깊이에서 정지 탐색을 켜면 공짜처럼 보이는 미끼에 덜 걸린다 #### 6. 진행 방식 - 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘. - 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘. - 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘. - 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘. - 답변과 코드 주석은 한국어로 해 줘. ## 원리 - 깊이 1 에서 멈춘 AI 는 「퀸으로 룩을 잡으면 +5」 만 보고, 다음 수에 폰이 퀸(−9)을 잡는 걸 못 본다 — 수평선 너머라서. - 정지 탐색은 깊이 0 에 닿아도 바로 평가하지 않고, 잡는 수만 계속 펼친다. 잡을 게 없으면(조용한 판) 그때 평가한다. - 각 마디에서 「안 잡고 멈춤(stand pat)」 = 지금 평가값을 기본으로 깔고, 잡는 수가 그보다 좋을 때만 바꾼다 — 잡기를 억지로 하지 않는다. - 견본 결과: 룩 잡기는 끝까지 보면 −4, 나이트 잡기는 다시 잡을 것이 없어 +3 → 안전한 나이트를 고른다. ## 핵심 코드 — 정지 탐색 (알파베타 깊이 0 에서 부르기) (발췌: 새로 씀 (demos/demosGameAI.ts i345 견본 「잡기가 끝날 때까지 더 봄」과 같은 방식, 네가맥스 꼴)) ```ts // 점수는 「지금 둘 차례」 기준 (네가맥스): 상대 점수 = -내 점수 function quiesce(s: Board, a: number, b: number, qdepth = 0): number { const standPat = evaluate(s); // 안 잡고 여기서 멈춰도 이만큼 if (standPat >= b) return b; // 이미 상대가 허락 안 할 만큼 좋다 if (standPat > a) a = standPat; if (qdepth >= 8) return a; // 잡기가 끝없이 이어지는 판 대비 for (const m of captures(s).sort(mvvLva)) { // 큰 말을 싼 말로 잡는 수부터 const v = -quiesce(play(s, m), -b, -a, qdepth + 1); if (v >= b) return b; if (v > a) a = v; } return a; } function alphaBeta(s: Board, depth: number, a: number, b: number): number { if (isOver(s)) return terminalScore(s); if (depth === 0) return quiesce(s, a, b); // 평가 대신 조용해질 때까지 더 for (const m of moves(s)) { const v = -alphaBeta(play(s, m), depth - 1, -b, -a); if (v >= b) return b; if (v > a) a = v; } return a; } ``` ## 흔한 실수 · 확인 목록 - [ ] **stand pat 없이 잡기를 강제하면 손해 보는 잡기까지 하게 된다** — 「안 잡고 멈춤」의 평가값을 기본으로 두고 잡기가 더 좋을 때만 바꾼다. - [ ] **정지 탐색에 상한이 없으면 잡기가 이어지는 판에서 멈추지 않는다** — qdepth 상한(8 정도)을 둔다. - [ ] **장군 · 진급 같은 큰 수를 빼면 여전히 수평선 착각이 남는다** — 게임에 따라 「장군 피하기」 · 「승급」도 정지 탐색에 넣는다. ## 완성 기준 체크리스트 - [ ] 왼쪽(깊이 1)은 룩을 잡고 다음 수에 퀸을 잃어 평가가 +5 → −4 로 떨어진다 - [ ] 오른쪽(정지 탐색)은 룩 줄을 끝까지 보고 −4 를 알아내 나이트(+3)를 고른다 - [ ] 같은 깊이에서 정지 탐색을 켜면 공짜처럼 보이는 미끼에 덜 걸린다 ## 이 기술 정보 - id: `i345` · 분류: 게임 시스템 · AI › 게임 AI · 공통 · 난이도 보통 · 폰 부담 보통 (폰 주의) — 잡는 수만 보니 가지는 적지만 마디 수가 전체의 절반을 넘기도 한다. 「잡는 말이 싼 것부터(MVV-LVA)」 정렬로 줄인다. - 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i345 - 쓰면 좋을 때: 잡기 · 맞바꾸기가 있는 게임(체스 · 장기 · 고누) / 깊이 제한 탐색이 「다 잡고 끝」에서 자꾸 손해를 볼 때 - 쓰지 말 때: 잡기가 없는 게임(틱택토 · 커넥트4) — 대신 「위협(3줄)」을 평가 함수에 넣는다 / 잡기가 끝없이 이어지는 게임 — 정지 탐색에도 깊이 상한을 둔다 ## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript) ### i345 견본 항목 — `src/demos/demosGameAI.ts:1248` ```ts i345: { kind: '2d', caption: '왼쪽은 한 수만 보고 멈춰 「룩 공짜!」라 착각 → 다음 수에 퀸을 잃어요. 오른쪽은 잡기가 끝날 때까지 더 보고(정지 탐색) 안전한 나이트를 골라요', make() { const st = { speed: 1 }; let T = 0; const CYCLE = 8.5; const VAL: Record = { Q: 9, R: 5, N: 3, P: 1, K: 0 }; const base = (): Pc[] => [ { k: 'K', white: true, c: 0, r: 4 }, { k: 'Q', white: true, c: 2, r: 4 }, { k: 'R', white: false, c: 2, r: 1 }, { k: 'P', white: false, c: 1, r: 0 }, { k: 'N', white: false, c: 4, r: 2 }, { k: 'K', white: false, c: 4, r: 0 }, ]; const GL: Record = { K: ['♚', '♚'], Q: ['♛', '♛'], R: ['♜', '♜'], N: ['♞', '♞'], P: ['♟', '♟'] }; const drawBoard = (g: G, x0: number, y0: number, s: number, pcs: Pc[], ghost: Pc[], u: number): number => { const c = s / 5; for (let r = 0; r < 5; r++) for (let q = 0; q < 5; q++) { g.fillStyle = (r + q) % 2 ? '#7a6a8f' : '#cfc3dc'; g.fillRect(x0 + q * c, y0 + r * c, c, c); } g.strokeStyle = 'rgba(0,0,0,0.5)'; g.lineWidth = 1 * u; g.strokeRect(x0, y0, s, s); const put = (p: Pc, a: number): void => { g.globalAlpha = a; const px = x0 + p.c * c + c / 2; const py = y0 + p.r * c + c / 2; g.fillStyle = 'rgba(0,0,0,0.35)'; g.beginPath(); g.arc(px + c * 0.04, py + c * 0.06, c * 0.4, 0, TAU); g.fill(); const gr = g.createRadialGradient(px - c * 0.12, py - c * 0.14, c * 0.04, px, py, c * 0.4); gr.addColorStop(0, p.white ? '#fffaf0' : '#4a3f63'); gr.addColorStop(1, p.white ? '#e2d6bd' : '#191427'); g.fillStyle = gr; g.beginPath(); g.arc(px, py, c * 0.39, 0, TAU); g.fill(); g.strokeStyle = p.white ? '#a8915f' : '#b7a6e6'; g.lineWidth = Math.max(1, c * 0.035); g.stroke(); g.font = `${c * 0.56}px ${FS}`; g.textAlign = 'center'; g.textBaseline = 'middle'; g.fillStyle = p.white ? '#3a2c14' : '#f1ebff'; g.fillText(GL[p.k]![0], px, py + c * 0.03); g.globalAlpha = 1; }; for (const p of pcs) put(p, 1); for (const p of ghost) put(p, 0.45); return c; }; const sq = (x0: number, y0: number, c: number, q: number, r: number): [number, number] => [x0 + q * c + c / 2, y0 + r * c + c / 2]; return { draw(g, w, h, _t, dt) { reset(g); T += Math.min(dt, 0.1) * st.speed; if (T > CYCLE) T = 0; const u = scaleOf(w, h); bg(g, w, h); const pw = w / 2; const s = Math.min(pw - 34 * u, h - 52 * u); [0, 1].forEach((side) => { const px = side * pw; const x0 = px + (pw - s - 14 * u) / 2; const y0 = 30 * u; txt(g, side ? '정지 탐색 (잡기 끝까지)' : '깊이 1 에서 멈춤', px + pw / 2, 11 * u, 8.5 * u, side ? C.green : C.red, 'center', 900); let pcs = base(); let ghost: Pc[] = []; const arrows: [number, number, number, number, string, string][] = []; let evalV = 0; let msg = ''; let msgCol = C.text; const Q = (): Pc => pcs.find((p) => p.k === 'Q')!; const take = (k: string, white: boolean): void => { pcs = pcs.filter((p) => !(p.k === k && p.white === white)); }; if (T < 1.4) { arrows.push([2, 4, 2, 1, 'rgba(255,255,255,0.75)', `+${VAL.R}`]); arrows.push([2, 4, 4, 2, 'rgba(255,255,255,0.75)', `+${VAL.N}`]); msg = '잡을 수 있는 것 둘'; } else if (side === 0) { if (T < 2.4) { arrows.push([2, 4, 2, 1, C.gold, `+${VAL.R}`]); msg = '룩이 더 크다!'; evalV = 5 * ease((T - 1.4) / 1); } else { take('R', false); const q = Q(); q.c = 2; q.r = 1; evalV = 5; msg = '평가 +5 → 이 수로 결정'; msgCol = C.gold; if (T > 3.6) { // 수평선 너머: 폰이 퀸을 잡음 const k = ease((T - 3.6) / 0.7); const p = pcs.find((x) => x.k === 'P')!; p.c = lerp(1, 2, k); p.r = lerp(0, 1, k); if (k >= 1) take('Q', true); evalV = lerp(5, -4, k); msg = k >= 1 ? '다음 수: 폰이 퀸을 잡음 → −4' : '그런데 다음 수에…'; msgCol = C.red; } } } else { if (T < 3.2) { // 룩 줄을 끝까지 const k = clamp((T - 1.4) / 0.6, 0, 1); ghost = [{ k: 'Q', white: true, c: 2, r: 1 }]; arrows.push([2, 4, 2, 1, 'rgba(255,209,102,0.8)', '+5']); if (k >= 1) { arrows.push([1, 0, 2, 1, C.red, '−9']); msg = '룩 잡으면 → 폰이 다시 잡음: −4'; msgCol = C.red; evalV = -4; } else msg = '룩 줄 더 보기…'; } else if (T < 4.8) { ghost = [{ k: 'Q', white: true, c: 4, r: 2 }]; arrows.push([2, 4, 4, 2, 'rgba(255,209,102,0.8)', '+3']); msg = '나이트 잡으면 → 다시 잡을 것 없음: +3'; msgCol = C.green; evalV = 3; } else { const k = ease((T - 4.8) / 0.6); take('N', false); const q = Q(); q.c = lerp(2, 4, k); q.r = lerp(4, 2, k); evalV = 3; msg = '안전한 +3 을 고름 ✓'; msgCol = C.green; } } const c = drawBoard(g, x0, y0, s, pcs, ghost, u); for (const [a, b, cc, d, col, lab] of arrows) { const [ax, ay] = sq(x0, y0, c, a, b); const [bx2, by2] = sq(x0, y0, c, cc, d); arrow(g, ax, ay, bx2, by2, col, 2 * u, 7 * u); pill(g, lab, (ax + bx2) / 2 + 6 * u, (ay + by2) / 2, 6.5 * u, col === C.red ? C.red : 'rgba(255,240,200,0.95)', '#140f05'); } // 평가 막대 const mx = x0 + s + 7 * u; const mh = s; g.fillStyle = 'rgba(255,255,255,0.08)'; rr(g, mx, y0, 6 * u, mh, 3 * u); g.fill(); const mid = y0 + mh / 2; const yv = mid - (evalV / 10) * (mh / 2); g.fillStyle = evalV >= 0 ? C.green : C.red; g.fillRect(mx, Math.min(mid, yv), 6 * u, Math.abs(yv - mid)); g.strokeStyle = 'rgba(255,255,255,0.5)'; g.lineWidth = 0.8 * u; g.beginPath(); g.moveTo(mx - 1 * u, mid); g.lineTo(mx + 7 * u, mid); g.stroke(); txt(g, `${evalV >= 0 ? '+' : ''}${evalV.toFixed(0)}`, mx + 3 * u, y0 - 5 * u, 6.5 * u, evalV >= 0 ? C.green : C.red, 'center', 900); // 수평선 (왼쪽만) if (side === 0 && T > 2.4) { const hy = y0 + s + 6 * u; g.strokeStyle = 'rgba(255,93,108,0.8)'; g.setLineDash([3 * u, 2 * u]); g.lineWidth = 1 * u; g.beginPath(); g.moveTo(x0, hy); g.lineTo(x0 + s, hy); g.stroke(); g.setLineDash([]); } pill(g, msg, px + pw / 2, h - 9 * u, 6.8 * u, 'rgba(10,14,30,0.85)', msgCol); }); g.strokeStyle = 'rgba(255,255,255,0.08)'; g.lineWidth = 1; g.beginPath(); g.moveTo(pw, 20 * u); g.lineTo(pw, h - 20 * u); g.stroke(); }, controls: [speedCtl(st), { type: 'button', label: '처음부터', on: () => { T = 0; } }] as Control[], }; }, } ``` ## 관련 기술 - 먼저 알면 좋은 기술: [알파베타 가지치기](https://ai-techstudio.web.app/ai/t/i341.md) `i341` · [평가 함수 설계 (가중치)](https://ai-techstudio.web.app/ai/t/i346.md) `i346` - 다음에 해 볼 기술: [같은 판 기억 (전치표 · 조브리스트 해시)](https://ai-techstudio.web.app/ai/t/i344.md) `i344` - 참고 문서: [Chessprogramming wiki — Quiescence Search](https://www.chessprogramming.org/Quiescence_Search) · [Wikipedia — Horizon effect](https://en.wikipedia.org/wiki/Horizon_effect)