바둑까지 정복한 AI가 왜 이 게임에는 오래 걸렸을까
2016년 알파고가 이세돌 9단을 이겼을 때 많은 분들이 "이제 보드게임은 AI한테 다 끝났구나" 하셨을 거예요. 그런데 AI가 꽤 오랫동안 인간 최고수를 확실하게 넘지 못한 게임이 있었어요. 바로 스트라테고(Stratego)예요. 최근 한 연구팀의 AI가 역대 최강으로 꼽히는 인간 플레이어를 이겼는데요, 더 눈길을 끄는 건 빅테크급 컴퓨팅 자원 없이 비교적 적은 비용으로 해냈다는 점이에요.
스트라테고는 10×10 판 위에서 각자 말 40개로 상대의 깃발을 빼앗는 전략 게임이에요. 말마다 계급이 있어요. 원수(Marshal)가 가장 세고, 정찰병(Scout)은 한 번에 여러 칸을 달릴 수 있고, 공병(Miner)은 폭탄을 해체할 수 있어요. 스파이는 제일 약하지만 먼저 공격하면 원수를 잡을 수 있죠. 핵심은 상대에게 내 말의 정체가 보이지 않는다는 거예요. 상대에게는 말의 뒷면만 보이고, 두 말이 부딪혀야 비로소 정체가 드러나요.
완전 정보 vs 불완전 정보, 이게 왜 중요하냐면
바둑과 체스는 '완전 정보 게임'이에요. 판 위의 모든 게 양쪽에 다 보이죠. 그래서 알파고처럼 "내가 여기 두면 상대는 저기 두겠지" 하고 미래를 쭉 내다보는 트리 탐색이 아주 잘 통해요.
스트라테고는 '불완전 정보 게임'이에요. 지금 판의 상태부터 정확히 모르니까, 미래를 내다보려면 먼저 "저 말이 원수일 확률은 얼마나 될까?" 같은 추정(belief)부터 해야 해요. 게다가 상대도 나를 속이려고 하거든요. 약한 말을 강한 말처럼 당당하게 전진시키는 블러핑이 기본 전략이에요. 이런 게임에서 늘 같은 패턴으로 두면 금방 읽히기 때문에, 최적 전략은 어느 정도 무작위성을 섞은 형태가 돼요. 게임이론에서 말하는 '내시 균형'에 가까운 전략을 찾아야 하는 거죠. 포커에서 좋은 패일 때만 베팅하면 상대가 다 눈치채는 것과 같은 원리예요.
규모도 어마어마해요. DeepMind 분석에 따르면 스트라테고에서 나올 수 있는 게임 상태는 약 10^535가지로, 바둑(약 10^360)보다 훨씬 많아요. 게임 시작 전 말을 배치하는 경우의 수만 10^66가지인데요, 텍사스 홀덤 포커의 시작 패 조합이 10^6 수준인 걸 생각하면 차원이 다르죠.
이전 도전자, DeepMind의 DeepNash
2022년 DeepMind는 DeepNash라는 AI를 Science에 발표했어요. R-NaD(Regularized Nash Dynamics)라는 기법을 써서, 탐색 없이 자기 대국 강화학습만으로 내시 균형에 가까운 전략을 학습시켰죠. 온라인 대전 플랫폼 Gravon에서 역대 랭킹 3위 안에 들었고, 숙련된 인간 플레이어를 상대로 84% 승률을 기록했어요. 대단한 성과였지만 '역대 최강 인간을 확실히 꺾었다'고 할 수준은 아니었고, DeepMind 규모의 연산 자원이 투입됐다는 한계도 있었어요.
이번엔 무엇이 달랐나
이번 성과의 포인트는 두 가지예요. 최정상급 인간과 직접 붙어서 이겼다는 것, 그리고 그걸 훨씬 적은 비용으로 해냈다는 거예요.
요즘 이 분야에서 주목받는 방향은 자기 대국 강화학습으로 기본 직관(정책)을 기르고, 실제 대국 중에는 테스트 타임 탐색(test-time search)으로 그 순간의 판단을 한 번 더 다듬는 조합이에요. 비유하자면 강화학습은 수많은 판을 두며 쌓은 '감'이에요. 테스트 타임 탐색은 실전에서 "잠깐, 저 말은 지금까지 한 번도 안 움직였으니 폭탄일 가능성이 높아. 다시 계산해보자" 하고 머리를 한 번 더 굴리는 거고요. DeepNash가 '감'만으로 뒀다면, 요즘 흐름은 감과 계산을 합친 셈이죠.
다만 불완전 정보 게임에서는 탐색이 생각보다 훨씬 까다로워요. 상대 말의 정체를 모르니 가능한 배치 시나리오를 확률적으로 그려보고 그 위에서 탐색해야 하는데, 경우의 수가 폭발하거든요. 결국 얼마나 효율적으로 추정하고 탐색하느냐가 비용을 낮추는 열쇠예요. 구체적인 학습 구조와 대국 전적은 원문 기사와 논문에서 꼭 확인해보세요.
업계 맥락: 포커에서 LLM까지
불완전 정보 게임 AI의 계보를 따라가 보면 흐름이 보여요. 카네기멜론대의 Libratus(2017)와 Pluribus(2019)는 포커에서 프로를 이겼는데요, CFR(반사실적 후회 최소화)이라는 알고리즘과 상황별 부분 게임 풀이를 썼어요. 하지만 포커는 숨겨진 정보가 카드 몇 장뿐이라, 말 40개가 숨겨진 채로 수백 수를 두는 스트라테고에는 그대로 적용하기 어려웠죠. 2022년에는 Meta의 CICERO가 협상 게임 디플로머시에서 언어 모델과 전략 추론을 결합하기도 했고요.
흥미로운 건 이 흐름이 요즘 LLM과도 맞닿아 있다는 거예요. o1, o3 같은 '생각하는 모델'의 핵심 아이디어도 학습된 직관에 추론 시점 연산(test-time compute)을 더해서 성능을 끌어올리는 거거든요. 모델을 무작정 키우기보다 실전에서 더 생각하게 만드는 쪽이 가성비가 좋다는 교훈이 게임 AI에서도 다시 확인된 셈이에요.
한국 개발자에게 주는 시사점
당장 스트라테고 AI를 만들 일은 없겠지만, 정보가 가려진 상황에서 결정을 내려야 하는 문제는 실무 곳곳에 있어요. 광고 경매 입찰가 결정, 보안에서 공격자 행동 예측, 협상 봇 같은 것들이요. 특히 한국은 게임 산업이 크니까, 카드 게임이나 '전장의 안개'가 있는 전략 게임에서 사람처럼 블러핑하고 추론하는 AI 상대를 만들 때 직접적인 힌트가 될 수 있어요.
공부해볼 키워드로는 내시 균형과 CFR, 그리고 DeepMind의 오픈소스 게임 AI 프레임워크인 OpenSpiel을 추천해요. 포커 변형을 비롯해 다양한 불완전 정보 게임과 알고리즘이 구현되어 있어서, 직접 돌려보면서 감을 잡기 좋거든요.
'적은 비용'이라는 부분도 의미가 커요. 거대한 연산 자원이 없는 대학 연구실이나 스타트업도 알고리즘 설계만 잘하면 최전선 성과를 낼 수 있다는 증거니까요.
마무리
한줄 정리: 속고 속이는 게임에서도 AI가 인간 최강자를 넘었어요. 비결은 거대한 자원보다 '학습된 직관 + 실전 탐색'이라는 영리한 설계였고요.
여러분은 어떻게 생각하세요? 블러핑과 심리전이 핵심인 게임까지 AI가 넘어섰다면, 실제 비즈니스 협상이나 보안처럼 현실의 불완전 정보 게임에서도 이런 기법이 통할까요?
🔗 출처: Hacker News