아니요. 8×8 리버시(오셀로)는 풀리지 않았습니다. 컴퓨터가 초인간 강도에 도달했지만 — 엔드게임을 완벽하게 풀고 어떤 인간도 일관되게 맞설 수 없는 수준으로 플레이하지만 — 완전한 게임 트리(~10^28개의 가능한 포지션)는 탐색된 적이 없습니다. 소형 변형은 풀렸습니다: 6×6 리버시는 완벽한 플레이에서 첫 번째 플레이어가 이기는 것으로 증명되었습니다. 8×8 게임은 미결 상태입니다. 이것이 오늘날 플레이어들이 사용하는 프로그램에 어떤 영향을 미치는지는 리버시 AI 작동 원리와 리버시 소프트웨어 도구를 참고하세요.
게임을 “푼다"는 것이 무슨 의미인가?
게임 이론에서 게임은 시작 포지션에서 완벽한 플레이의 결과가 증명될 때 풀린 것으로 간주됩니다 — 어느 플레이어가 어떻게 플레이하든 상관없이 승리, 패배, 또는 무승부. 두 가지 수준의 해결책이 있습니다:
약하게 풀린: 완벽한 플레이에서 시작 포지션의 결과가 알려진 것. 첫 번째 플레이어가 이긴다(또는 무승부, 또는 진다)는 것을 알지만, 완전한 전략 지도를 반드시 갖고 있는 것은 아닙니다.
강하게 풀린: 게임의 모든 가능한 포지션에서 완벽한 플레이가 계산된 것. 어디서든 게임을 시작하든 최적의 결과로 이어지는 완전한 전략이 알려져 있습니다.
대부분의 “풀린” 게임은 약하게만 풀렸습니다. 강한 해결책에는 막대한 계산 자원이 필요합니다.
주목할 만한 풀린 게임
| 게임 | 상태 | 결과 | 연도 |
|---|---|---|---|
| 틱택토 | 강하게 풀림 | 무승부 | 고대부터 알려짐 |
| 커넥트 포 | 강하게 풀림 | 첫 번째 플레이어 승리 | 1988 (빅터 알리스) |
| 체커 (드래프츠, 8×8) | 약하게 풀림 | 무승부 | 2007 (셰퍼 외, 사이언스) |
| 6×6 리버시 | 약하게 풀림 | 첫 번째 플레이어 승리 | 1993 (알리스 & 부로) |
| 체스 (8×8) | 미풀림 | 알 수 없음 | — |
| 바둑 (19×19) | 미풀림 | 알 수 없음 | — |
| 8×8 리버시 (오셀로) | 미풀림 | 알 수 없음 | — |
왜 8×8 리버시는 풀리지 않았는가?
문제의 규모
리버시의 게임 트리는 크지만, 복잡한 보드게임의 기준으로는 천문학적이지 않습니다:
- 가능한 포지션: 약 10^28로 추정
- 평균 분기 계수: 포지션당 약 10개의 합법적인 수
- 게임 길이: 총 60수 (4개의 시작 돌에서 각 빈 칸당 하나씩)
비교하면:
- 체스는 약 10^44개의 가능한 포지션과 10^123개의 게임 트리 노드를 가짐
- 바둑(19×19)은 약 10^170개의 가능한 포지션을 가짐
리버시는 이 게임들의 기준으로는 다루기 쉽습니다 — 하지만 10^28개의 포지션은 여전히 현재 하드웨어로 완전한 열거를 넘어섭니다. 체커 풀기(10^21 포지션)는 수십 년의 분산 컴퓨팅이 필요했습니다 — 앨버타 대학교의 조나단 셰퍼와 동료들이 2007년 사이언스에 증명을 발표하기 전에 거의 20년 가까운 작업이 필요했습니다. 리버시의 게임 트리는 약 천만 배 더 큽니다.
왜 엔드게임은 풀렸지만 전체 게임은 그렇지 않은가
리버시 계산의 핵심 비대칭성: 엔드게임은 다루기 쉽고, 전체 게임은 그렇지 않습니다.
빈 칸이 20개 남으면, 해당 상태에서 고려해야 할 포지션이 최대 10^20개 — 좋은 하드웨어로 몇 초 내에 풀 수 있습니다. 빈 칸이 25개면, 여전히 좋은 하드웨어로 가능합니다. 하지만 첫 수부터 풀기는 전체 게임 트리를 통해 완벽한 플레이를 역방향으로 전파해야 합니다. 이것은 계산적으로 여전히 불가능합니다.
이것이 컴퓨터 리버시 프로그램이 엔드게임은 완벽하게 플레이하지만 초반과 중반에는 휴리스틱 평가(점수 함수)를 사용하는 이유입니다. 휴리스틱은 매우 강합니다 — 어떤 인간도 이길 수 있을 만큼 강합니다 — 하지만 증명적으로 완벽하지는 않습니다.
6×6 해결책
1993년, 연구자 빅터 알리스(Victor Allis)와 마이클 부로(Michael Buro)는 6×6 리버시가 완벽한 플레이에서 첫 번째 플레이어의 승리임을 확인했습니다. 6×6은 36칸만 있고 표준 8×8 버전보다 훨씬 작은 게임 트리를 가지기 때문에 분석이 가능했습니다. 알리스는 이전에 커넥트 포를 풀기 위해 유사한 역행 분석 기술을 적용했습니다(1988년).
이 결과는 8×8 게임을 이해하는 데 중요합니다: 완벽한 8×8 리버시의 결과가 첫 번째 원리에서 명백하지 않다는 것을 시사합니다. 6×6 결과는 또한 더 작은 보드 크기에서 첫 번째 플레이어 이점(검은이 먼저 둠)이 결정적일 수 있음을 확인했습니다. 리버시 변형과 더 작은 보드 크기에 대해서는 리버시 변형을 참고하세요.
오늘날 컴퓨터 리버시는 얼마나 강한가?
게임이 풀리지 않았지만, 컴퓨터는 어떤 인간도 훨씬 넘어서는 플레이 수준에 도달했습니다. 주요 이정표:
Logistello (1990년대)
앨버타 대학교의 마이클 부로가 개발한 Logistello는 인간 세계 챔피언을 지배한 최초의 프로그램 중 하나였습니다. 1997년, Logistello는 세계 오셀로 챔피언 무라카미 타케시와의 매치에서 6–0으로 승리했습니다. 이 프로그램은 부로의 1997년 ICCA Journal 논문에 설명된 정교한 학습된 평가 함수와 함께 깊은 알파-베타 탐색을 결합했습니다.
이것은 같은 해 IBM의 딥 블루가 카스파로프를 격파한 체스의 이정표와 유사한 분수령이었습니다. 리버시 컴퓨터는 실용적 목적에서 인간의 능력을 넘어섰습니다.
현대 엔진
현대 리버시 엔진은 다음을 사용합니다:
- 엔드게임 솔버: 마지막 20~25수에 대한 완벽한 플레이
- 패턴 기반 평가: 수백만 개의 게임으로 훈련된 휴리스틱
- 신경망 평가: 더 최근의 엔진은 AlphaZero와 유사한 딥러닝 접근 방식 통합
- 오프닝 북: 분석된 오프닝 포지션 데이터베이스
이러한 프로그램들은 진지한 플레이에서 인간에게 본질적으로 무적이지만, 첫 수부터 증명적으로 완벽한 플레이를 실행하지는 않습니다.
8×8 리버시를 푸는 데 무엇이 필요한가?
순전히 가설적으로, 완전한 약해는 다음을 필요로 합니다:
- 하드웨어: 충분한 큐비트를 가진 양자 컴퓨터, 또는 체커를 푼 것보다 많은 크기의 차수를 초과하는 대규모 분산 고전 컴퓨팅 노력
- 알고리즘: 공격적인 대칭 축소와 결합된 역행 분석(모든 종단 포지션에서 역방향으로 풀기)
- 시간: 현재 고전 하드웨어로는 잠재적으로 수세기 추정; 미래 기술로는 훨씬 적게
이러한 해결책의 실용적 영향은 흥미롭겠지만 플레이어에게는 다소 반기후적일 것입니다 — 컴퓨터가 이미 초인간 수준으로 플레이하므로, 완벽한 플레이에서의 이론적 결과를 알아도 게임의 인간 경험은 바뀌지 않습니다.
“거의 풀린” 상태가 플레이어에게 의미하는 것
컴퓨터가 리버시를 지배한다는 사실은 실용적인 시사점이 있습니다:
학습을 위해: 컴퓨터 분석은 거의 모든 포지션에서 최선의 수를 보여줄 수 있습니다. 강한 AI에 대해 플레이하고 게임을 분석하는 것이 향상되는 가장 효과적인 방법 중 하나입니다.
경쟁 플레이를 위해: 인간은 인간 심리, 체력, 시간 관리, 오프닝 준비 모두 토너먼트 조건에서 — 심지어 다른 인간에 대해서도 — 중요하기 때문에 최고 수준에서 계속 경쟁합니다. WOC는 여전히 의미 있는 챔피언십입니다.
게임 감상을 위해: 컴퓨터 지배가 일부 게임에서 열정을 식혀온 것과 달리, 리버시 커뮤니티는 컴퓨터 분석을 교육 도구로 받아들였습니다. 오프닝 이론, 엔드게임 기술, 포지셔널 이해 모두 AI 분석 덕분에 깊어졌습니다.
체스 및 바둑과의 비교
| 체스 | 바둑 | 리버시 (8×8) | |
|---|---|---|---|
| 게임 트리 크기 | ~10^123 | ~10^360 | ~10^28 |
| 풀렸는가? | 아니요 | 아니요 | 아니요 |
| 컴퓨터 강도 | 초인간 (2005+) | 초인간 (2016+) | 초인간 (1997+) |
| 엔드게임 완벽? | 엔드게임 테이블베이스 (7개 말) | 부분적 | 네 (마지막 20~25수) |
| 해결 전망 | 매우 낮음 (수세기) | 본질적으로 없음 | 낮지만 가능 |
리버시는 더 작은 상태 공간 때문에 세 게임 중 결국 풀릴 가능성이 가장 높습니다 — 하지만 당분간 열린 문제로 남아 있습니다.