Combinatorial Game Theory

필승 전략 수학 게임

표준 님 게임과 배스킨라빈스 31을 플레이하며 님-합, 역산법, 불변량의 원리를 탐구합니다.

표준 님 게임 한 더미에서 원하는 만큼 제거하고 마지막 아이템을 가져가세요.
당신의 차례입니다.
더미를 누르면 제거할 개수가 바뀝니다.
Mathematical structure

게임에 숨어 있는 수학적 원리

두 게임은 가능한 수를 계산하여 유리한 상태를 계속 유지할 수 있는 조합게임입니다. 어려움 난이도의 AI는 아래의 핵심 원리를 활용합니다.

표준 님 게임과 님-합

각 더미의 개수를 이진수로 나타내고 배타적 논리합을 계산합니다. 님-합을 0으로 만들면 상대에게 불리한 상태를 넘길 수 있습니다.

Nim-sum = pile₁ XOR pile₂ XOR pile₃

배스킨라빈스 31과 역산법

31을 부르는 사람이 지므로 30을 먼저 확보하는 것이 목표입니다. 상대와 내가 한 차례씩 부르는 숫자의 개수 합을 4로 유지합니다.

목표 수: 2, 6, 10, 14, 18, 22, 26, 30

불변량 유지

필승 전략은 매 차례 뒤에도 특정 조건이 변하지 않도록 만드는 방법입니다. 님 게임에서는 님-합 0, 31 게임에서는 4 간격의 목표 수가 불변량 역할을 합니다.

해결된 게임

현재 상태에서 가능한 모든 선택과 결과를 분석할 수 있으므로, 완전한 정보를 가진 두 사람이 최선으로 행동할 때의 승패를 이론적으로 결정할 수 있습니다.