여우는 뭐라고 할까? 보드게임 Starve the Fox의 승률을 분석하다

여우가 압도적으로 유리하다고 여겼던 Starve the Fox를 컴퓨터로 분석하자, 비교적 강한 탐색에서는 양이 약 50%, 여우가 15% 승리하고 나머지 35%는 무승부였음 초기 몬테카를로 트리 탐색(MCTS) 자가 대국에서는 여우 승률이 약 85%였지만, 탐색량을 늘리자 양의 협력 전략이 드러남 양은 개별 대치에서 약하므로 무리 전체를 조율해야 하며, 한 턴에 말 하나만 움직이는 규칙 때문에 여우보다 여러 턴 앞을 내다봐야 함 자가 대국에서 수집한 국면으로 회귀 기반 평가 함수를 학습하고 이를 짧은 시뮬레이션과 결합해, 제한된 사고 시간에도 더 강한 상대를 구현함 완벽한 플레이의 승패를 증명한 결과는 아니지만, 이번 규칙과 탐색 조건에서는 여우가 압도적으로 강하다는 통념이 맞지 않았음 비대칭 규칙과 무승부 조건 Starve the Fox는 스웨덴에서 Fox Game이라고도 부르는 오래된 노르드 보드게임임 Wikipedia에 따르면 영어권의 Fox and Geese는 이를 단순화한 게임임 여우는 2개, 양은 20개로 시작하며, 번갈아 자기 말 하나를 보드의 선을 따라 한 칸씩 움직임 말끼리 통과하거나 같은 자리를 차지할 수 없음 양의 목표는 여우가 시작하는 상단 중앙의 3×3 우리, 즉 c5부터 e7까지를 양 9마리로 채우는 것임 행 번호가 줄어드는 후진은 불가능함 턴 종료 시 움직일 수 없도록 갇힌 여우는 제거됨 여우 둘을 모두 제거하면 즉시 승리함 여우의 목표는 양이 우리를 채우지 못하게 막는 것임 먼저 시작하며 모든 방향으로 이동할 수 있음 직선으로 두 칸 떨어진 곳이 비어 있고 중간에 양이 있으면, 양을 뛰어넘어 잡아먹을 수 있음 남은 양이 9마리 미만이면 승리함 이번 분석에서 선공 이점은 매우 작았음 같은 국면을 반복하며 진전하지 않는 순환 게임이 될 수 있음 어린이와 함께 배운 규칙에는 이런 상황의 처리가 없었으므로, 분석에서는 진전 없이 40수 동안 진행되면 무승부로 처리함 양은 후진할 수 없으므로 행 번호를 이용해 진전을 측정함 얕은 탐색이 놓친 양의 협력 전략 가족 내 경험과 몇 차례 직접 대국에서는 여우가 크게 실수해야 양이 이긴다는 인식이 강했음 게임 규칙을 Python으로 구현하고, 범용 트리 탐색을 제공하는 OpenSpiel에 연결해 분석함 첫 구현은 끝까지 무작위로 진행하는 시뮬레이션으로 말단 국면을 평가하는 기본 MCTS였음 최적화하지 않은 Python에서 초당 약 1,000회 탐색...