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

요약

보드게임 Starve the Fox의 승률을 MCTS와 Python으로 분석했습니다. 여우가 압도적이라는 통념과 달리, 충분한 탐색량에서는 양의 협력 전략이 중요하게 드러났습니다. 이는 개별 충돌보다 장기적인 무리 전체의 조율이 핵심임을 보여주며, AI 개발에 활용될 수 있습니다.

핵심 포인트

깊은 탐색을 통해 여우가 압도적이라는 통념이 깨졌습니다.
양은 개별 충돌보다 무리 전체의 장기적인 협력 전략이 중요합니다.
MCTS와 평가 함수 개선을 통해 AI의 성능을 향상시킬 수 있습니다.
게임 분석 시, 단순한 승패를 넘어선 순환 국면과 장기 계획이 핵심입니다.

여우가 압도적으로 유리하다고 여겼던 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회 탐색을 수행함
사고 시간을 1초 미만으로 둔 직접 대국에서는 여우가 대부분 이길 듯했고, 자가 대국에서도 여우 승률이 약 85%였음
다만 양이 충분히 남아 있으면 순환 국면을 이용해 무승부를 강제할 수 있었음
양의 이동 제약 때문에 분기 수가 비교적 작아 깊은 탐색의 효과도 작을 것으로 예상했으나, 8,000회 탐색 을 허용한 양 측 컴퓨터가 사람의 실수 두 번을 활용해 승리 가능한 국면에 도달함
양은 개별 충돌에서 약하므로 무리 전체의 협력 이 필요하고, 한 턴에 한 마리만 이동할 수 있어 장기 전략이 중요함
실질적으로는 무리 안의 빈칸을 움직여, 여우와 가까운 양 뒤에 빈칸이 생기지 않게 하는 플레이임
아이가 여우를 맡고 어른이 양을 맡으면, 어른에게 더 깊은 사고를 요구하면서 함께 즐길 수 있음
자가 대국으로 평가 함수를 개선하는 방법
끝까지 진행하는 무작위 시뮬레이션은 비용이 크므로, 중간에 시뮬레이션을 끊고 휴리스틱으로 평가 하는 방식으로 바꿈
실제 승패가 휴리스틱보다 우선되도록, 휴리스틱 점수의 절댓값을 종료된 게임의 점수보다 작게 조정함
최초 평가 함수에서는 8플라이 후 중단하는 방식이 가장 좋았음
적절한 중단 깊이는 게임 복잡도와 시뮬레이션 정책의 품질 에 달려 있음
완전 무작위 이동은 원래 말단 국면보다 최종 결과를 덜 잘 반영하게 만들 수 있어, 아예 시뮬레이션하지 않는 편이 나을 수도 있음
더 좋은 평가 함수가 있다면 시뮬레이션을 짧게 하고 트리 탐색에 시간을 더 쓰는 편이 유리할 가능성도 있음
단순한 평가 변수로는 생존한 양의 수 , 양이 전진한 행 수의 합 등을 사용할 수 있음
학습은 약한 탐색의 자가 대국 → 국면 표본 수집 → 회귀 모델 학습 순서로 진행함
초기 탐색은 한 수당 약 0.5초를 사용하며, 끝까지 무작위로 진행해 평가함
연속 국면 사이의 강한 상관관계를 피하려고 게임마다 임의의 국면 하나만 추출하고 최종 결과를 기록함
회귀 모델은 국면으로 결과를 예측하며 제곱 손실을 최소화하는 가중치를 학습함
다음 세대는 같은 시간 예산에서 짧은 시뮬레이션과 학습한 평가 함수 를 사용함
이전 세대와 대국해 개선을 확인한 뒤, 새 자가 대국 자료로 다시 학습함
이전 세대가 이기지 못하던 국면에서도 승리 방법을 찾으면서 숙련된 플레이의 결과를 더 잘 예측하도록 반복함
몇 차례 반복한 상대는 짧은 사고 시간에도 직접 대국한 사람을 양쪽 진영 모두에서 안정적으로 이겼음
학습된 가중치와 위치 가치
평가 함수는 쌍곡탄젠트 로 원점수를 −1

부터 +1

까지 변환하며, 무승부는 0으로 취급함
최종 값에는 약 +1

의 편향 항도 필요하며, 값이 확률 그 자체는 아님
따라서 개별 가중치의 절댓값보다 상대적 크기와 다른 변수와의 결합을 살펴봐야 함
위치 변수 이외의 학습된 계수 는 다음과 같음
이미 잡아먹힌 양: 마리당 여우에 +0.036

여우 차례에 잡아먹을 수 있는 양: 마리당 여우에 +0.096

양 차례에 잡아먹힐 수 있는 양: 마리당 여우에 +0.035

여우의 가능한 이동: 수당 여우에 +0.021

양이 전진한 행 수의 합: 행당 양에 +0.0034

우리 안의 양: 마리당 양에 +0.017

칸별 위치 가치 도 함께 학습했으므로, 위 계수만으로 전략을 해석하면 안 됨
우리 안에서 가장 낮은 위치 가치는 0.11

, 우리 밖 평균은 0.09

임
따라서 우리 밖 평균 위치와 비교한 입성 가치는 최소 약 0.11−0.09+0.017=0.04

, 평균 약 0.08

로, 개별 계수 0.017

보다 큼
c7

의 양은 약 0.23

의 가치가 있으며 대부분은 해당 칸의 위치 가치에서 나옴
양의 위치별 특성 은 이동 가능성과 잡아먹힐 위험을 반영함
2행은 잡아먹히기 쉬우면서 목표 달성에도 기여하지 못해 가치가 낮음
b3

, c3

, c6

, d7

처럼 가장자리이되 모서리가 아닌 곳은 잡아먹힐 위험 때문에 인접 모서리보다 대체로 불리함
a5

의 양은 이동 선택지가 하나뿐이며 c5

의 여우가 이를 막을 수 있지만, 더 가치 있는 b5

의 양을 보호할 수 있음
a4

도 이동 선택지가 적어 불리할 가능성이 있음
우리 밖에서 위험이 큰 2행과 4행을 제외하면, 우리에 가까운 행일수록 대체로 가치가 커짐
d6

의 높은 가치는 이유가 명확하지 않으며 이동성과 관련됐을 가능성이 있음
양 한 마리 단위로 읽는 전략
위치 가치까지 반영한 평균 평가값 은 다음과 같음
양 한 마리가 한 행 전진: 양에 0.02

양 한 마리가 우리 밖에서 안으로 이동: 양에 0.08

여우가 양을 잡아먹을 수 있는 상태로 턴 시작: 여우에 0.20

양 한 마리가 이미 잡아먹힘: 여우에 0.15

체스의 폰 가치처럼 양 한 마리의 가치 를 기준으로 환산하면, 양 한 마리의 손실을 상쇄하려면 총 9행을 전진해야 함
양 하나를 희생해 다른 두 마리를 우리에 넣으면 양 가치 기준 +0.07

처럼 보이지만, 잡아먹힐 수 있는 상태를 만드는 비용 까지 고려하면 −0.27

임
잡아먹히기 직전이 이미 잡아먹힌 상태보다 불리한 이유는 확실하지 않음
여우가 두 칸을 뛰어 더 빠르게 이동할 수 있기 때문일 수 있으며, 이 이동 효과만의 평균 가치는 양 약 0.2

마리에 해당함
여우의 위치 가치는 양보다 칸별 차이가 작고 , 살아 있는 여우 한 마리는 평균적으로 양 약 2.3

마리 가치에 해당함
4행과 5행의 중앙이 유리하며, 다른 조건이 같다면 b4

부터 f5

까지의 5×2 영역에 머무르는 편이 좋음
여우가 우리 안에 들어가면 밖의 양들이 방해받지 않고 재배치할 수 있어 불리함
b5

와 대칭 위치 f5

는 양쪽 모두에 특히 가치가 높지만 그 이유는 명확하지 않음
자가 대국 기록으로 만든 퍼즐
자가 대국에서 흥미로운 국면을 골라, 사활 문제나 체스 퍼즐처럼 목표를 달성하는 다음 한 수 를 찾는 문제를 만들 수 있음
양 차례에는 N턴 안에 여우를 가두는 문제임
여우 차례에는 강제 포획을 피하며 N턴 생존하는 문제임
여우 차례에는 N턴 안에 갇히지 않고 양을 잡아먹어야 함
양 차례에는 N턴 동안 양의 손실을 막아야 함
양 차례에는 N턴 안에 우리를 채워야 함
여우 차례에는 N턴 동안 양이 우리를 채우지 못하게 막아야 함
N은 난도와 생성 비용을 함께 결정 함
간단한 필터로 대부분의 국면을 제외할 수 있지만, 여러 유형은 깊이 N까지 완전 탐색해야 적절한 문제인지 확인할 수 있음
예를 들어 양을 잡아먹은 뒤 같은 N턴 안에 여우가 갇힌다면, 이는 양의 단순 손실이 아니라 여우를 잡기 위한 희생이므로 정답에서 제외해야 함
N이 4 미만인 문제만으로 약 2,000개 를 생성했으며, 퍼즐 모음 을 공개함
직접 풀 때는 N=1인 즉시 포획 문제에서도 놓친 경우가 있었음
언어 모델로 가능해진 일회성 분석
이 프로젝트는 최근 약 1년간 개선된 언어 모델 하네스 가 없었다면 시도하지 않았을 작업임
모델 자체의 개선 여부와 별개로, 하네스가 적극적으로 피드백을 만들어내도록 유도하면서 명세에 맞는 코드를 더 안정적으로 생성할 수 있었음
생성물은 Python 구현 3,000줄 이상 , 테스트 1,000줄, HTML 500줄 규모였음
밀도가 높은 코드여서 사람이 쓰는 형식으로 정리하면 총 6,000줄을 넘을 것으로 추산함
불필요하게 복잡하고 경직돼 있으며, 제대로 리팩터링하면 약 4,500줄로 줄여 복잡도를 약 25% 낮출 수 있을 것 으로 추산함
이 경우 목적은 유지할 코드 자산이 아니라 오래된 보드게임을 이해하는 것 이었음
이를 위해 수작업으로 4,500줄을 작성할 의향은 없었고, 코드가 사라져도 아쉬워하지 않을 정도로 코드 자체의 가치는 낮았음
최종 승률과 분석의 한계
이번 규칙과 비교적 강한 탐색에서 양 승리 약 50%, 무승부 35%, 여우 승리 15% 를 얻음
양은 이길 수 없을 때도 대개 무승부를 강제할 수 있었음
이는 게임의 완전한 해답이 아님
완벽하게 플레이하면 양이 항상 이기는지, 여우가 항상 이기는지는 알 수 없음
다만 여우가 압도적으로 유리하다는 최초의 인식은 분석 결과와 맞지 않았음
댓글과 토론

AI 자동 생성 콘텐츠

원문 바로가기