CMU·MIT 연구진, 역대 최강 Stratego 선수를 꺾은 AI Ataraxos 공개

왜 지금 이 주제인가

10월 1일 Nature에 발표된 논문이 보드게임 Stratego에서 처음으로 초인간(superhuman) 수준의 AI를 선보였습니다. Stratego는 체스나 바둑과 달리 상대 말의 정체가 게임 내내 가려진 채 진행되는 게임으로, 지난 수년간 수백만 달러 규모의 연구에도 인간 최정상급 선수를 넘어서지 못한 유일한 고전 게임으로 꼽혀 왔습니다. Carnegie Mellon University, MIT, NYU Tandon, Stanford 연구진이 만든 Ataraxos는 이 벽을 8,000달러 미만의 학습 비용으로 넘어섰습니다.

핵심 내용

Stratego는 10×10 판 위에서 각자 40개의 말을 상대에게 보이지 않게 배치한 뒤 시작하는 전략 보드게임입니다. 말의 종류가 비밀로 숨겨져 있어 가능한 말 배치 조합은 10^33가지를 넘습니다. 이 때문에 숨겨진 정보가 적은 텍사스홀덤(가능한 패 1,326가지) 등에서 통했던 기법은 그대로 적용할 수 없었고, DeepMind가 2022년 Science에 발표한 DeepNash도 톱 수준 인간 선수를 넘어서지는 못했습니다.

Ataraxos는 자기대전 강화학습과 테스트 시점 탐색을 결합해 이 문제를 풀었습니다. 핵심은 정책이 약할 때는 강한 정규화와 큰 폭의 업데이트를, 정책이 강해질수록 약한 정규화와 작은 업데이트를 적용하는 “동적 감쇠(dynamic damping)” 방식입니다. 이를 통해 숨겨진 정보가 많은 환경에서 흔히 나타나는 순환적이고 불안정한 학습 동역학을 억제했습니다. 말 배치(설정)와 수를 두는 과정은 각각 별도의 트랜스포머(설정 네트워크, 수 네트워크)로 학습했고, 실전에서는 상대의 숨겨진 말 종류를 추정하는 “신념 네트워크(belief network)“가 가능한 보드 상태들을 샘플링한 뒤 1,000회의 롤아웃을 수행하는 탐색을 한 수마다 추가로 거칩니다. 평가에서 쓰인 탐색은 40수 깊이, 1,000회 롤아웃 기준으로 수당 약 1.26초가 걸렸습니다.

학습에는 H100 GPU 16개로 1주일(설정·수 네트워크), H100 4개로 4일(신념 네트워크)이 걸렸고, 총 비용은 8,000달러를 넘지 않았습니다. 이는 DeepNash가 TPU v3 1,024개로 23개월간 학습하는 데 든 300만450만 달러와 대비됩니다.

2025년 7월, 연구진은 Ataraxos를 세계선수권 최다 우승(4회, 현역 중 최다), 네덜란드 전국선수권 최다 우승(15회), 온라인 세계선수권 최다 우승(2회), 역대 최장기간 세계 1위 랭킹(600주 이상) 기록을 보유한 Pim Niemeijer와 20판 대국으로 맞붙였습니다. 결과는 15승 1패 4무로, 무승부를 0.5승으로 계산한 실질 승률 85%였습니다. Ataraxos는 상대 전략에 맞춰 적응하지 않는 고정된 정책으로 대국에 임했는데도 이런 격차를 냈고, 대국 결과가 독립동일분포를 따른다는 가정 아래 계산한 p-값은 0.00026 미만이었습니다. 이어 2025년 8월 1~3일 열린 Stratego 세계선수권 현장에서는 참가자들과 40판을 추가로 두어 38승 2패(승률 95%)를 기록했습니다.

의미와 한계

Ataraxos의 성과는 방대한 양의 숨겨진 정보를 가진 전략적 의사결정 문제에도 강화학습과 탐색을 결합한 접근이 통한다는 것을 보여줍니다. 연구진은 빠르고 정확한 시뮬레이터를 만들 수 있는 문제라면 이 설계를 다른 영역에도 적용할 수 있을 것으로 보고 있으며, 자체 개발한 GPU 기반 Stratego 시뮬레이터를 공개해 후속 연구를 지원할 계획이라고 밝혔습니다.

다만 한계도 있습니다. 평가 대국은 Pim Niemeijer 한 명을 상대로 진행됐는데, 그는 여러 판에 걸쳐 Ataraxos의 전략을 파악해 역이용할 기회가 있었던 반면 Ataraxos는 상대에 맞춰 전략을 바꾸지 않았다는 점에서 비대칭적인 조건이었습니다. 연구진 스스로도 대국 결과가 독립동일분포를 따른다고 보기는 어렵다는 점을 인정하며, 통계적 유의성 계산과 별도로 베팅 시장 모델을 활용한 보조 분석을 함께 제시했습니다. 또한 Ataraxos의 테스트 시점 탐색은 한 차례의 정책 업데이트를 모사하는 수준에 머물러 있어, 더 정교한 탐색 알고리즘을 적용하면 추가 개선 여지가 있다고 연구진은 덧붙였습니다.

한 줄 정리

수백만 달러가 들었던 숨은 정보 게임 Stratego 공략을, 연구팀은 8,000달러 미만의 비용으로 해냈습니다.