리버시 수학: 게임 복잡도, 확률, 그리고 숫자들

리버시(오셀로)는 약 10의 28승 가능한 게임 순서의 추정 게임 트리를 가지고 있습니다 — 체스(~10의 123승)보다 훨씬 작지만 현재 하드웨어로는 완전한 해결을 훨씬 넘어섭니다. 돌 배치와 잠재적 패스를 모두 계산하면 모든 게임은 정확히 60수입니다. 최대 가능한 점수는 64-0입니다. 이 숫자들을 이해하면 왜 컴퓨터가 엔드게임을 지배하지만 아직 전체 게임을 해결하지 못하는지가 명확해집니다. 게임이 해결되었는지에 대한 질문은 리버시가 해결되었나요?를 참조하세요.

게임 트리: 리버시는 얼마나 큰가?

총 가능한 게임 수

게임 트리는 시작 포지션에서 가능한 모든 결말까지 수의 별개 순서 수를 셉니다. 리버시의 경우:

• 추정 게임 트리 크기: ~10의 28승 가능한 게임 (Victor Allis의 1994년 박사 논문 Searching for Solutions in Games and Artificial Intelligence, 림부르크 대학교에서 추정)
• 평균 분기 계수: 포지션당 ~10개의 합법적인 수 (오프닝에서 일반적으로 4~12, 미드게임에서 최대 20+, 이후 감소)
• 게임 길이: 60수 (고정, 각 수가 하나의 빈 칸을 채우므로; 패스도 수임)

비교를 위해:

리버시는 해결된 체커와 해결되지 않은 체스 사이에 있습니다. 게임 트리는 체커보다 약 10의 7승 배 더 크며, 이것이 컴퓨터가 초인적인 강도로 플레이함에도 리버시가 아직 해결되지 않은 이유를 설명합니다.

보드 포지션 수

합법적인 플레이 중 발생할 수 있는 별개의 돌 배치인 합법적인 보드 포지션의 수는 약 10의 28승으로 추정됩니다. 이것은 게임 트리(순서를 세는)와 다릅니다. 왜냐하면 이론적으로 같은 보드 포지션이 다른 수 순서로 도달될 수 있기 때문입니다.

64칸에서의 돌 배치의 이론적 최대 (불법 포함)는 3의 64승 ≈ 4.3 × 10의 30승입니다 (각 칸은 비어 있거나, 흑이거나, 백일 수 있음). 실제 합법적 포지션은 이것의 부분집합입니다.

고정 게임 길이

리버시의 수학적으로 특징적인 점: 모든 게임의 길이가 고정입니다.

• 보드에는 64칸이 있음
• 시작 시 4칸이 채워짐
• 각 수가 정확히 하나의 빈 칸을 채움
• 따라서 모든 게임은 정확히 60수입니다 (패스 포함)

이것은 체크메이트나 기권으로 매우 다른 길이에서 끝날 수 있는 체스와 다릅니다. 리버시에서 게임은 항상 60개의 빈 칸이 모두 채워지면 끝납니다 (또는 남은 빈 칸이 모두 접근 불가능한 경우처럼 보드가 가득 차기 전에 끝날 수도 있음).

함의: 모든 리버시 포지션은 정의된 게임 단계를 가집니다. 10수는 항상 오프닝입니다. 45수는 항상 미드게임 깊은 곳입니다. 55수는 항상 엔드게임입니다. 이 예측 가능성은 체계적인 학습에 도움이 됩니다 — 이 단계들에 걸쳐 칸 중요도가 어떻게 변하는지는 보드 가치를 참조하세요.

돌 수 수학

시작 및 종료 상태

시작 포지션: 흑 돌 2개 + 백 돌 2개 = 총 4개의 돌, 60개의 빈 칸

종료 상태: 몇 개의 칸이 채워지느냐에 따라 총 4개에서 64개의 돌. 표준 플레이(60개의 빈 칸이 모두 채워짐)에서 정확히 64개의 돌이 보드에 있습니다.

합 제약: 종료 시 흑 돌 + 백 돌 = 64.

따라서: 종료 시 흑이 B개의 돌을 갖는다면, 백은 (64 - B)개를 갖습니다. 이것은 단 하나의 숫자로 모든 최종 결과를 설명할 수 있음을 의미합니다 — 흑의 돌 수. 일반적인 경쟁 결과는 약 30~34(접전)에서 45~19 이상(압도적 승리)까지 범위입니다.

64-0 결과

한 플레이어가 64-0(모든 돌)으로 이길 수 있나요? 네, 이론적으로. 하지만 다음이 필요합니다:

• 상당한 실력 또는 지식 차이
• 지는 플레이어가 체계적으로 돌을 포기하는 수를 두는 것
• 승자의 마지막 수가 모든 남은 상대방 돌을 뒤집는 특정 게임 경로

실전에서 64-0 결과는 극히 드물고 의도적인 노력이나 치명적인 붕괴가 필요합니다. 60-4, 58-6, 또는 54-10 결과가 압도적이지만 더 일반적인 승리를 나타냅니다.

돌 뒤집기의 보존

각 수는 하나의 새로운 돌을 놓고 하나 이상의 기존 돌을 뒤집습니다. 핵심 항등식:

흑이 놓은 수 + 백이 놓은 수 = 60 (총 수)

흑 돌의 순 수 = 흑이 놓은 수 - (백에 의해 뒤집힌 흑 돌) + (흑에 의해 뒤집힌 백 돌)

이것은 최종 돌 수가 단순히 각 플레이어가 몇 번의 수를 두었는지에 관한 것이 아님을 의미합니다 — 이것은 배치와 뒤집기의 복잡한 상호작용입니다. 30번의 수를 두지만 돌이 반복적으로 뒤집히는 플레이어는 30개보다 훨씬 적은 돌로 끝날 수 있습니다.

엔드게임 해결 가능성 수학

마지막 20수가 계산 가능한 이유

20개의 빈 칸이 남았을 때, 그 시점부터 도달 가능한 포지션의 수는 각 단계에서의 수 수의 곱으로 제한됩니다. 수당 10개의 옵션이 있어도 20수는 최대 10의 20승 포지션을 산출합니다 — 크지만 효율적인 알고리즘을 가진 현대 컴퓨터에게는 처리 가능합니다.

알파-베타 가지치기와 최고우선 수 순서 지정으로 강한 리버시 프로그램은 빈 칸이 25~30개인 포지션을 초에서 분 단위로 해결할 수 있습니다. 이것이 엔드게임 해결이 경쟁 AI에서 표준인 이유입니다.

감소하는 분기 계수

리버시의 분기 계수는 게임이 진행될수록 감소합니다:

• 오프닝 (1~20수): 포지션당 4~12개의 합법적인 수
• 미드게임 (20~44수): 포지션당 4~15개의 합법적인 수
• 엔드게임 (44~60수): 포지션당 1~8개의 합법적인 수 (급속히 감소)

이 감소하는 분기 계수가 엔드게임을 처리 가능하게 만드는 것입니다. 마지막 10수에서 턴당 가용한 수의 수는 종종 2~4개로 떨어져 컴퓨터에게 정확한 계산을 간단하게 만듭니다.

확률 및 결과 통계

오프닝 대칭

시작 포지션은 완전히 대칭입니다 — 두 플레이어 모두 동일한 상황에 직면합니다 (수 순서를 제외하고). 첫 번째 플레이어(흑)는 네 가지 가능한 오프닝 수가 있지만, 대칭에 의해 네 가지 모두 동등한 포지션으로 이어집니다 (단지 회전되거나 반사됨).

이것은 리버시의 진정한 첫 번째 수가 두 번째 수에서 일어남을 의미합니다 — 백이 흑의 첫 번째 수에 응할 때, 처음으로 대칭이 깨집니다.

흑 대 백 승률

동등한 실력 수준에서 경쟁 데이터는 다음을 시사합니다:

• 흑 (첫 번째 플레이어)이 초급에서 중급 수준에서 약간 더 자주 이김
• 최고 수준에서, 이 이점은 논쟁적 — 백은 흑에 응하는 정보 이점을 가짐
• 컴퓨터 분석은 시작 포지션에서 완벽한 플레이가 흑 승리, 백 승리, 또는 무승부인지 결정적으로 확립하지 못했음

오프닝 대칭은 어느 플레이어도 명백한 구조적 불이익이 없음을 의미합니다 — 예를 들어 체스에서는 백이 보편적으로 선수 이점을 가지는 것과 달리.

경쟁 플레이에서의 점수 분포

고수준 경쟁 플레이에서 점수는 승자에 대해 약 32~36개 돌 범위에 집중됩니다 — 강한 플레이어 간의 게임은 종종 접전입니다. 분포는 대략:

• 30~35 범위: 접전 경쟁 게임에서 가장 일반적
• 36~44 범위: 결정적이지만 압도적이지 않은 승리
• 45~60+ 범위: 초기 코너 손실로 인해 주로 발생하는 일방적인 게임

더 약한 상대나 낮은 설정의 AI에 대한 게임에서 포지셔널 실수가 증가함에 따라 고득점 승리가 더 흔해집니다.

수학적 호기심

단일 수에서 최대 뒤집기

단일 리버시 수는 동시에 최대 8방향으로 돌을 뒤집을 수 있습니다 (놓인 돌에서 여덟 방향 모두). 한 수에서 이론적으로 뒤집을 수 있는 최대 돌의 수는 24개입니다 (대칭 구성에서 모든 남은 상대방 돌), 하지만 실전에서 한 수로 6~10개의 돌을 뒤집는 것도 인상적입니다.

완벽한 게임 대칭

두 플레이어가 대칭적으로 플레이하면 (보드의 대각선을 중심으로 서로의 수를 미러링), 한 플레이어가 깰 때까지 게임이 완벽한 대칭으로 진행됩니다. 이 수학적 관찰은 초기 리버시 연구에서 이론적 호기심으로 이어졌습니다 — 때때로 적어도 무승부를 보장할 수 있는 백을 위한 “미러 전략”.

패리티와 마지막 수

보드의 어떤 닫힌 영역에서든 마지막 수를 두는 플레이어는 패리티 이점을 갖습니다. 이것은 수학적으로 조합 게임 이론의 “마지막으로 수를 두는 플레이어가 이긴다” 원칙과 유사합니다. 리버시의 엔드게임 패리티 분석은 조합 게임 이론 원칙의 직접적인 응용입니다 — 레크리에이션 수학과 실용적인 게임 전략 간의 연결.