R-GCN 탐정과 GNN Mr. X를 학습시켜 PUCT 검색과 결합해 탐정 승률 91.7% 달성

이 요약은 AI가 원문을 분석해 생성했습니다. 정확한 내용은 원문 기준으로 확인하세요.

TL;DR

이 프로젝트는 199개 역 그래프에서 도망자의 티켓만 관찰하는 불완전 정보 게임을 대상으로 R-GCN 기반의 탐정 정책과 GNN 기반 Mr. X를 각각 학습시켜 검색과 결합한 결과를 제시한다. 탐정은 HMM 스타일 신념 분포와 거리 맵을 입력으로 받아 R-GCN을 통해 행동을 출력하고 초기에는 행동 클로닝으로 시작해 PPO로 파인튜닝하여 동일한 MCTS 상대에서 승률을 25%에서 79%로 향상시켰다. Mr. X는 GNN으로 업그레이드된 뒤 PUCT(정책 프라이어와 value head 포함)로 탐색을 수행하면서 강해졌고, 탐색과 학습의 조합 적용 시 탐정의 상대 승률이 평가에서 91.7%에 도달했다. 실험은 브라우저 데모·재현 영상·코드 저장소로 재현 가능하게 제공되며 정책 초기화, 탐색 예산, 가치추정의 조합이 불완전 정보 추적 문제에서 성능을 크게 좌우한다.

실용적 조언

불완전 정보 환경에서는 신념 분포를 명시적으로 입력으로 포함하고 그래프 구조화된 네트워크를 사용하면 상태 표현이 개선되어 정책 학습에 도움이 된다.
초기 정책을 행동 클로닝으로 확보한 뒤 PPO 같은 온폴리시 알고리즘으로 미세조정하면 샘플 효율과 안정성을 동시에 개선할 수 있다.
검색 기반 강화(예: PUCT)를 도입할 때는 정책 프라이어와 value head를 함께 학습시키고 시뮬레이션 예산(여기서는 16 sims)을 명시적으로 튜닝하면 성능 향상 효과를 얻기 쉽다.

섹션별 상세

문제 상황은 199개 역 그래프에서 탐정들이 도망자가 재생한 티켓만 관찰하며 추적해야 하는 불완전 정보 게임이다. 탐정 쪽 정책은 HMM 스타일의 신념 분포와 각 역 사이 거리 맵을 입력으로 받아 R-GCN으로 처리한 뒤 행동 확률을 출력하도록 설계되었다. 학습은 행동 클로닝으로 초기화한 뒤 PPO로 파인튜닝하여 동일한 MCTS 기반 Mr. X 상대에서 탐정의 승률이 초기 25%에서 79%로 상승한 수치가 제시되었다. 이 결과는 신념 기반 입력과 그래프 구조의 조합이 탐정 정책 학습에 실질적 영향을 미쳤음을 시사한다.

도망자(Mr. X) 측은 처음에는 MCTS로 운영되었고 이후 GNN 기반 정책으로 바꾼 다음 PUCT로 감싸서 정책 프라이어와 value head를 도입했다. 구체적으로 트리 탐색에서 정책 확률을 우선순위로 사용하고 value head로 노드 평가를 보강하며 한 수당 16번의 시뮬레이션을 수행하는 설정이 활용되었다. 이 단계에서 Mr. X의 성능이 21%에서 35%로 상승했고, PUCT를 적용한 탐색 전략과 결합하자 탐정 측의 상대 승률이 별도 평가에서 35%에서 91.7%로 크게 바뀌었다. 정책 우선순위와 가치추정이 결합된 탐색이 게임 성능에 큰 폭의 이득을 준다는 점이 근거로 제시되었다.

훈련 및 평가 절차는 양측 모델을 모두 학습시키고 고정된 상대를 트리 내에서 시뮬레이션하도록 하여 상호작용을 재현하는 방식으로 구성되었다. 작성자는 브라우저 플레이 데모와 20분짜리 재현 영상, 그리고 코드·모델 저장소 링크를 함께 제공하여 실험의 재현 가능성을 확보했다. 평가 결과는 여러 단계의 대조 실험 수치(예: 25%→79%, 21%→35%, 35%→91.7%)로 제시되어 실험적 근거가 포함되었다. 따라서 이 프로젝트는 단일 알고리즘 개선뿐 아니라 학습-검색의 결합이 실전 게임 전략에 어떻게 영향을 주는지 보여주는 사례로 의미가 있다.

개발 과정에서 작성자가 AI 도구와 페어 프로그래밍을 광범위하게 활용했다고 밝힌 점은 소규모 개인 프로젝트의 실행 가능성과 개발 속도 측면에서 시사점을 준다. 도구 지원을 통해 복잡한 모델 구현과 실험 자동화가 가능해졌고, 그 결과로 재현 가능한 코드와 대화형 데모를 공개할 수 있었다. 이 사실은 연구·프로토타이핑 단계에서 개발 도구의 역할이 증대하고 있음을 반영하며 도구 의존성과 검증·재현성 관리라는 실무적 과제를 함께 제시한다.

용어 해설

관계형 그래프 컨볼루션 네트워크(R-GCN): — 노드와 엣지 타입이 다양한 그래프에서 관계별로 합성곱을 적용하는 GNN 구조로, 각 엣지 타입마다 별도 가중치 텐서를 사용하여 이웃 정보의 중요도를 반영한다. 이 글 맥락에서는 탐정들이 그래프 상의 상태와 상호작용을 표현하는 정책 또는 가치 네트워크로 활용되며, 위치와 이동 규칙을 구조화된 입력으로 받아 행동 출력을 만든다. 그래프 구조로 지리적·관계적 정보를 직접 처리할 수 있어 스코틀랜드 야드처럼 도시역 네트워크 환경에서 효과적이다.
PUCT (Policy + UCT)(PUCT): — 정책(prior) 정보를 UCT(Upper Confidence bounds applied to Trees)에 결합한 탐색 알고리즘으로, 각 노드의 방문횟수와 정책 확률을 함께 고려해 다음 확장 지점을 선택한다. 정책 확률은 신경망이 제공하고 가치추정은 트리 내 시뮬레이션과 네트워크의 value head로 보강되어 더 효율적인 시뮬레이션 할당을 가능하게 만든다. 이 글에서는 Mr. X에 PUCT를 적용해 정책 우선순위를 이용한 검색 성능 향상이 나타났다.
행동 클로닝(Behavioral Cloning): — 전문가 행동 로그를 입력과 행동 쌍으로 학습하여 정책을 초기화하는 지도학습 방식으로, 정책을 무작위 초기화하는 대신 초기 성능을 빠르게 확보하는 데 사용된다. 본 프로젝트에서는 BC로 초기 가중치를 얻은 뒤 강화학습으로 미세조정하여 학습 안정성과 샘플 효율을 높였다. 특히 복잡한 추적 게임에서 탐정의 기본 전략을 빠르게 학습시키는 수단으로 쓰였다.
신념 상태(Belief State): — 관측이 불완전한 환경에서 가능한 상태들의 확률 분포를 나타내는 내부 표현으로, 관찰 가능한 티켓 플레이만 보이는 상황에서 도망자의 위치를 추정하는 핵심 입력이다. 이 글에서는 HMM 스타일의 신념 분포와 위치 간 거리 맵을 결합해 그래프 신경망의 입력으로 사용하여 탐정 정책이 불확실성에 기반해 행동을 선택하도록 했다. 신념 상태는 추적 정책의 입력으로 직접 활용되어 탐정의 의사결정에 중요한 역할을 했다.

코드 예제

text

null

원문에 코드 블록이 포함되어 있지 않으므로 스니펫을 추출할 수 없다.

언급된 도구

R-GCN추천

그래프 구조 입력을 처리하는 정책/가치 신경망 아키텍처

PPO추천

정책 미세조정용 온폴리시 강화학습 알고리즘

MCTS / PUCT추천

트리 기반 검색과 정책 프라이어 결합으로 행동 선택을 개선하는 탐색 기법

언급된 리소스

Demo브라우저 데모: Scotland Yard GNN

문서재현 영상(20분, 로그 기반 장면 재구성)

GitHub코드와 모델 저장소