게임 AI의 버릇: '항상 9' 익스플로잇을 찾아내고 고치기

“봇은 어떻게 당신의 패를 읽는가: 흑백게임 AI의 belief-MCTS” 의 후속 글. 그 글이 관심법 봇이 숨겨진 패를 어떻게 추론하는지를 다뤘다면, 이 글은 봇이 어떻게 두는지에 있던 버그 — 사람이 farming 할 수 있던 결정론적 ‘버릇’ — 과 그걸 고치는 의외로 깊은 토끼굴 이야기다.

버릇

게임 요약: 두 플레이어가 1–9 타일을 들고, 매 라운드 하나씩 비밀로 공개해 큰 수가 이긴다(단 1은 9를 이긴다). 먼저 5라운드 이기면 승. 색은 공개(○ 홀 / ● 짝), 숫자는 비공개.

버그는 이거였다. 사람이 흑(짝수) 을 먼저 내면, 봇은 — 후공으로서 — 거의 항상 9 로 답했다:

흑 오프너에 대한 정책:   9: 99.9%    나머지: ~0%

9는 실제로 라운드를 이긴다 — 9는 모든 짝수를 이긴다. 그래서 얼핏 괜찮아 보인다. 하지만 자세히 보자: 2 를 이기려고 봇은 가장 강한 카드를 써버렸다. 그것도 매번. 이건 전략이 아니라 버릇이다.

”매 수가 이기는데도” 버릇이 버그인 이유

사람은 패턴을 알아채고, 자기가 선일 때마다 가장 낮은 흑 타일로 연다. 봇은 충실히 그 2를… 9로 부순다. 사람은 라운드를 지지만 쓸모없는 2를 봇의 최고 카드와 맞바꾼다. 반복하면 사람은 봇의 강한 카드를 말려 죽이고, 정작 중요한 라운드를 가져간다.

이게 진짜 문제인지 추측하기 싫어서 익스플로잇 상대를 만들어 측정했다. 매번 가장 낮은 흑으로 여는 NineBaiter 를, 매 게임 선공으로 앉혔다:

                      NineBaiter 상대 봇 승률
  배포된 봇            ████░░░░░░░░░░░░░░   24%

봇은 24% 만 이겼다. 이 한 가지 수법을 찾은 사람은 봇을 4판 중 3판 이긴다. 버릇은 진짜로, 심각한 구멍이었다.

정책이 무너지는 두 곳

수정은 붕괴 — 정책이 한 수에 ~100%를 몰아주는 것 — 를 서로 다른 두 곳에서 되돌려야 한다.

1. 정책 자체가 붕괴했다. 네트워크는 강한 플레이를 모방하도록 학습되고, 학습 신호는 그 라운드를 이긴 수에 보상을 줬다. 흑 오프너에 대해 9는 확실히 이기는 유일한 수라서, 그래디언트가 모든 확률을 9에 쌓았다. 네트워크는 7·8(75% 이기면서 9를 남기는)도 충분히 좋은 답이라는 걸 배운 적이 없다.

2. 탐색이 그걸 다시 붕괴시켰다. 강한 봇은 네트워크의 직감만 두지 않는다 — 그 위에서 탐색(belief-MCTS)을 돌린다. 탐색은 정책을 개선해야 한다. 하지만 표준 게임트리 탐색은 가장 가치 높은 한 수에 노력을 집중한다 — 그래서 네트워크가 확률을 {7, 8, 9}에 퍼뜨리도록 가르친 뒤에도, 탐색은 충실히 그걸 9로 되-붕괴시켰다.

모든 비공개정보 게임에 해당하는 더 깊은 교훈: 결정론적 전략은 정의상 exploit 가능하다. 상대가 너를 예측할 수 있으면, 너를 상대로 계획을 세울 수 있다. 이런 게임에서 무적의 전략은 혼합된 것이다 — 읽히지 않으려고 좋은 선택지들 사이에서 무작위화한다. 봇의 문제는 9가 틀렸다는 게 아니라, 항상 9라서 읽힌다는 것이었다.

수정 1부: 주사위 말고, 모델이 섞도록 가르치기

손쉬운 수정은 play-time 랜덤성 — 그냥 “temperature”로 수를 샘플링하는 것이다. 우리는 일부러 그렇게 하지 않았다. 99.9% 스파이크에 temperature를 거는 건 무딘 잡음이다: 9를 흔들어 풀 만큼 높이면, 지는 2·3도 같이 두기 시작한다.

대신 학습 타깃을 고쳤다. 탐색이 배운 것을 기록할 때, “이번 라운드에 어떤 타일이 이길 수 있고, 얼마나” 를 소량 섞는다 — 좋은 수에만 퍼지게({7, 8, 9}에 확률, 지는 수는 0) — 그리고 이 블렌딩을 불확실성이 가장 큰 초반 라운드에 더 싣는다. 이제 모델은 합리적인 답들의 진짜 분포처럼 생긴 타깃을 학습한다:

흑 오프너 정책, 이전 → 이후
  이전:  9: 99.9%                          (엔트로피 0.012 bits)
  이후:  9: 65%   7: 11%   8: 9%   ...      (엔트로피 1.85 bits)

“엔트로피”는 그냥 선택이 얼마나 퍼져 있는지다. 거의 확정(0.012)에서 진짜 혼합(1.85)으로 — 그것도 옳은 수들 위에서 — 바뀌었다.

수정 2부: 혼합을 존중하는 탐색

이제 미묘한 부분. 새로 퍼진 정책을 가이드로 탐색을 다시 돌렸더니… 봇은 여전히 거의 매번 9를 뒀다. 탐색이 혼합을 되-붕괴시키고 있었다.

범인은 단 하나의 상호작용이었다. 변화를 주려고 봇은 최종 수를 1보다 작은 temperature로 샘플링하는데, 이건 분포를 제곱한다. 9:71% 7:9% 8:8% 같은 혼합을 제곱하면 곧장 9:96% 로 되돌아간다. 변화 손잡이가 우리가 방금 학습시킨 혼합을 되돌리고 있었다.

수정: 배포 탐색이 자기 수 선택을 네트워크의 (이제 혼합된) 학습된 prior 와 블렌딩하게 하되, 초반에 더 싣고, 그 블렌드를 선형으로 샘플링한다 — 제곱 없이. 이건 주사위가 아니라, 탐색이 모델이 언제 섞어야 하는지 배운 것에 따르는 것이다. 켜면:

                      흑 오프너: '9'의 비율
  탐색, 이전           ████████████████░  97%
  탐색, 이후           ████████████░░░░░  73%

9에 73%, 더 싼 승리수에 27% — 미끼가 더는 통하지 않을 만큼.

효과는? (그리고 솔직한 함정)

                      NineBaiter 상대 봇 승률
  이전                 ████░░░░░░░░░░░░░░   24%
  이후                 █████████░░░░░░░░░   54%

미끼 저항력이 24% → 54%, 2배 넘게. 그리고 두 봇 페르소나 모두 이득을 본다: 탐색 기반 봇(관심법)은 54%로, 상위 두 수를 두는 더 빠른 정책 봇(중꺽마)은 이제 9와 함께 더 싼 승리수를 찾아 같은 baiter 상대 57% 에 안착한다. 라이브 봇에서 익스플로잇은 막혔다.

하지만 솔직한 부분. 옛 봇은 어떤 예측 가능한 봇 상대를 박살냈다 — 교과서적인 수만 두는 상대에겐 92% 이겼다, 그들의 예측가능성을 exploit하는 법을 배웠으니까. 새로 섞는 봇은 같은 상대에게 ~50%만 이긴다. exploit하기를 덜 exploit당하기와 맞바꾼 것이다.

이건 회귀가 아니라 핵심 그 자체다. 박살나던 상대들은 결정론적 봇이지 사람이 아니다. 실제 사람 스타일 플레이엔 여전히 강하고(랜덤 플레이 60%, 카드 비축형 77%), 단지 한 가지 미끼로 farming당하지 않을 뿐이다. “뾰족함 — 예측가능한 상대 박살, 미끼엔 무너짐”에서 “평평함 — 모든 것에 견고함”으로 옮겨가는 건 정확히 게임이론적 균형의 방향이다.

진짜 목적지

우리 수정은 좋고, 배포 가능한 근사치다 — 하지만 여전히 손으로 튜닝한 혼합량이다. 원리적 종착점은 게임의 내쉬 균형을 계산하는 것(CFR — Counterfactual Regret Minimization 같은 방법으로)인데, 모든 포지션에서 정확히 맞는 혼합을 찾아준다: 구조적으로 exploit 불가능하고, 아름답게도 — 손잡이 없이 — 초반(상대 패가 넓을 때)엔 더 섞고 후반(수가 강제될 때)엔 날카로워진다.

단, 더 큰 작업이다. 게임의 서로 다른 의사결정 상황(“정보집합”)을 세어보니 천만 개를 훌쩍 넘었다 — 단순히 표로 만들기엔 너무 많다. 그래서 균형 계산엔 샘플링 방법(Monte-Carlo CFR)이나 신경망 근사(Deep CFR), 또는 이 익스플로잇이 사는 초반 게임만 푸는 방식이 필요하다. 그게 다음 장이다.

지금은: board-game.wintersalmon.com 의 봇은 더 이상 항상 9를 현금화하지 않는다. 흑을 낮게 몇 번 열어보고 직접 확인해보시길.

---

여기 숫자들은 배포된 모델에서 실제 측정한 값이다. 정확한 퍼센트는 실행마다 조금씩 움직이지만, 이야기 — 결정론적 버릇, 그걸 farming한 baiter, 그리고 옳은 수들 위에서 섞도록 배운 모델 — 는 정확히 일어난 그대로다.