보난자(Bonanza) 메서드 해설
오랜 기간 관심을 가지고 연구해온 컴퓨터 일본장기(쇼기) 분야에서 2017년 개최된 제4회 전왕전(電王戦, 컴퓨터 vs 인간 쇼기 대결)을 다시 분석해보려 합니다.
당시 명인 타이틀 보유자 사토 아마히코(佐藤天彦)는 컴퓨터 쇼기 프로그램 포난자(Ponanza)에 패배했습니다. 이때 사용된 포난자 버전은 미니맥스 알고리즘을 개량한 탐색 방식과 기계학습으로 최적화된 평가 함수를 결합한 구조였습니다.
보난자(Bonanza) 메서드
학습할 국면 집합을 $\mathbf{P}$, 특징 벡터를 $\mathbf{v}$로 정의합니다. 국면 $p$에서 가능한 수의 개수를 $M_p$로 표기하고, 기보에서 선택된 수에 의한 다음 국면을 $p_1$, $m$번째 수에 의한 국면을 $p_m$이라 할 때 목적 함수는 다음과 같습니다:
\[J(\mathbf{P},\mathbf{v})=\sum_{p∈\mathbf{P}}\sum_{m=2}^{M_p} T_p[\xi(p_m, \mathbf{v})−\xi(p_1,\mathbf{v})]\]여기서 $\xi(p_m, \mathbf{v})$는 미니맥스 탐색 값이며, $T_p(x)$는 손실 함수입니다.
주요 특징:
- Max 플레이어 차례: $T_p(x)=T(+x)$
- Min 플레이어 차례: $T_p(x)=T(-x)$
- 시그모이드 함수 사용: $1/(1+e^{−0.0273x})$
핵심 원리
프로 기보에서 선택된 수의 정확한 평가값을 알 수 없으므로, 현재 평가 함수를 기준으로 기보에서 선택된 수와 다른 수들 간의 평가값 차이를 손실 함수로 활용합니다.
\[\frac{\partial J}{\partial v_i} = \sum \frac{dT_p}{dx} \left[\frac{\partial \xi(p_m)}{\partial v_i} - \frac{\partial \xi(p_1)}{\partial v_i}\right]\]학습 과정 특징:
- KPP(왕 위치 및 기물 관계) 특징의 선형 결합 사용
- L1 정규화 항 추가로 수렴성 향상
- 45,833국면 학습에 약 1개월 소요 (2006년 기준)
알파고 기법 연계 가능성
알파고의 정책 네트워크(Policy Network)에서 사용된 강화학습 방식을 쇼기에 적용할 경우:
- 정책 네트워크: 기물 이동 패턴 학습
- 가치 네트워크: 장기적 포지션 평가
- Monte Carlo 트리 탐색: 효율적인 수 읽기
다만 KPP 관계 특징이 신경망 기반 모델에 효과적일지 여부는 추가 실험이 필요합니다. 2025년 현재 딥러닝 기반 쇼기 AI들은 이미 이러한 접근법을 발전시켜 적용 중입니다12.