리버시 AI는 어떻게 작동하나요?

리버시 AI는 미니맥스 알고리즘을 사용하여 가능한 미래 수를 탐색하고, 코너 장악, 기동성, 안정적인 돌 수, 경계 돌을 기반으로 포지션을 평가합니다. 알파-베타 가지치기는 패배하는 분기를 조기에 제거하여 같은 시간에 더 깊이 탐색할 수 있게 합니다. 더 강한 AI 설정은 더 많은 수를 미리 보고 더 정교한 평가 함수를 사용합니다.

리버시에서 미니맥스란 무엇인가요?

미니맥스는 대부분의 리버시 AI가 사용하는 핵심 알고리즘입니다. 가능한 모든 수와 대응을 트리로 구성하며, 두 플레이어가 모두 최적으로 플레이한다고 가정합니다. AI는 자신의 점수를 최대화하면서 상대방이 점수를 최소화한다고 가정합니다. 트리의 루트에서 최선의 보장된 결과를 갖는 수가 선택됩니다.

리버시 AI에서 알파-베타 가지치기란 무엇인가요?

알파-베타 가지치기는 최종 결정에 영향을 줄 수 없는 탐색 트리의 분기를 제거하는 미니맥스의 최적화입니다. AI가 이미 찾은 것보다 확실히 더 나쁜 분기를 찾으면, 그 분기의 탐색을 중단합니다. 이를 통해 AI는 같은 시간에 약 두 배 더 깊이 탐색할 수 있습니다.

리버시 AI는 어떻게 수를 선택하나요?

리버시 AI는 현재 포지션의 모든 합법적인 수를 생성하고, 알파-베타 가지치기가 있는 미니맥스를 사용하여 몇 턴 앞을 탐색하고, 코너, 기동성, 안정적인 돌 등을 가중치로 사용하는 평가 함수로 각 결과 포지션을 점수화하고, 가장 높은 점수의 포지션으로 이어지는 수를 선택합니다.

리버시 AI가 항상 코너를 차지하는 이유는 무엇인가요?

코너는 절대로 뒤집을 수 없어 영구적 이득이기 때문에 AI의 평가 함수에서 가장 높은 가중치를 받습니다. AI는 이 지식이 점수 시스템에 내장되어 있어, 코너를 확보하는 수는 매우 높은 점수를 받고, 상대방에게 코너 접근권을 주는 수는 매우 낮은 점수를 받습니다.

리버시 AI의 원리: 미니맥스, 알파-베타, 평가 함수

리버시 AI는 미니맥스 알고리즘을 사용하여 미래 수순을 탐색하고, 알파-베타 가지치기로 패배하는 분기를 제거하며, 코너, 기동성, 안정적인 돌, 경계 돌에 가중치를 두는 평가 함수로 포지션을 점수화합니다. 엔드게임(마지막 20~25수)에서 강력한 AI는 가능한 모든 플레이 라인의 정확한 돌 결과를 계산하는 완벽한 솔버로 전환합니다. 이것이 게임 풀기와 어떤 관련이 있는지는 리버시는 풀린 게임인가?를 참고하세요.

핵심 알고리즘: 미니맥스

미니맥스의 역할

리버시의 모든 포지션에는 합법적인 수가 있습니다. 각 수는 새로운 포지션으로 이어지고, 그 포지션에도 다시 수가 있는 식으로 계속됩니다. 이것이 게임 트리 — 모든 가능한 미래의 분기 구조 — 를 만듭니다.

미니맥스는 하나의 가정으로 이 트리를 탐색합니다: 두 플레이어가 모두 최적으로 플레이합니다. 어떤 포지션에서든:

현재 플레이어(최대화자)는 자신에게 최선의 결과로 이어지는 수를 선택합니다
상대방(최소화자)은 현재 플레이어에게 최악의 결과로 이어지는 수를 선택합니다

평가된 말단 노드(탐색 하단의 포지션)에서 역방향으로 작업하며, 미니맥스는 트리의 모든 노드에 값을 할당합니다. 루트 노드(현재 포지션)는 결국 값을 갖게 되고, AI는 그 값으로 이어지는 수를 플레이합니다.

간단한 예시

검정이 두 가지 합법적인 수 A와 B를 가진다고 상상해보세요.

수 A는 검정이 달성할 수 있는 최선의 점수가 +6(돌의 60%)인 포지션으로 이어집니다
수 B는 검정이 달성할 수 있는 최선의 점수가 +4(돌의 55%)인 포지션으로 이어집니다

미니맥스는 수 A를 선택합니다. 하지만 두 값 모두 흰색의 최적 대응을 시뮬레이션하여 계산된 것이므로, 단순한 희망 사항이 아닌 보장된 결과를 나타냅니다.

탐색 깊이

AI는 전체 게임 트리를 탐색하지 않습니다 — 시간이 너무 오래 걸립니다. 대신 고정된 깊이(몇 수 앞)까지 탐색하고, 그 탐색의 하단에 있는 포지션을 평가 함수를 사용하여 평가합니다.

쉬운 AI: 2~3수 앞 탐색
보통 AI: 4~6수 앞 탐색
어려운 AI: 8~12수 이상 탐색 (+ 완벽한 엔드게임 풀기)

더 깊이 탐색할수록, AI는 자신의 수의 결과를 더 정확하게 예측할 수 있어 더 강하게 플레이합니다.

알파-베타 가지치기: 더 스마트하게 탐색

순진한 미니맥스 구현은 게임 트리의 모든 가능한 분기를 탐색합니다. 알파-베타 가지치기는 결과를 바꿀 수 없는 분기를 건너뛰어 같은 알고리즘을 훨씬 더 효율적으로 만듭니다.

작동 방식

알고리즘은 두 가지 값을 유지합니다:

알파: 최대화자(현재 AI)가 지금까지 찾은 최선의 점수
베타: 최소화자(상대방)가 지금까지 찾은 최선의 점수

알고리즘이 이미 다른 곳에서 찾은 것보다 나쁜 점수를 낼 분기를 발견하면 — 해당 분기의 탐색을 중단합니다. 분기가 “가지치기"됩니다.

결과: 알파-베타 가지치기는 평가되는 노드의 수를 약 제곱근만큼 줄입니다. 실제로 AI는 순진한 미니맥스에 비해 같은 시간에 약 두 배 더 깊이 탐색할 수 있습니다.

수 순서

알파-베타 가지치기는 최선의 수를 먼저 탐색할 때 가장 효과적입니다. AI가 초반에 유망한 수를 검토하면 알파와 베타 경계를 빠르게 확립하여 이후에 더 많은 가지치기가 가능합니다.

강력한 리버시 AI는 수 순서 휴리스틱 — 어떤 수가 최선일 가능성이 있는지 추정하고 먼저 탐색하는 규칙 — 을 사용합니다. 일반적인 휴리스틱:

먼저 코너 차지 탐색
그 다음 X칸을 피하는 수 탐색
나머지 수를 예상 포지션 값으로 정렬

좋은 수 순서는 탐색 트리의 80~90%를 가지치기하여 훨씬 더 깊은 탐색을 가능하게 합니다.

평가 함수

AI가 탐색 트리의 하단(깊이 한계)에 도달하면, 더 이상 탐색하지 않고 포지션을 점수화해야 합니다. 이것이 평가 함수 — 포지션의 가치에 대한 AI의 모델 — 입니다.

주요 구성 요소

1. 코너 장악 (최고 가중치) 코너는 차지했을 때 극도로 높은 양의 가중치를, 상대방에게 줄 때 극도로 낮은 음의 가중치를 받습니다. 코너 하나가 거의 모든 다른 포지셔널 요소를 능가할 수 있습니다. 인간 플레이어가 동일한 칸 가중치 논리를 사용하는 방법은 보드 값 가이드를 참고하세요.

2. 기동성 점수 각 플레이어가 이용 가능한 수의 수 차이. 높은 상대적 기동성은 강하게 긍정적입니다 — 상대방이 선택지가 적다는 의미입니다.

3. 안정적인 돌 수 절대로 뒤집을 수 없는 돌(코너, 전체 엣지 줄 등)은 강한 양의 가중치를 받습니다. 안정적인 돌은 최종 계수에서 해당 점수를 보장합니다.

4. 경계 돌 수 빈 칸에 인접한 돌은 취약한 타깃입니다. 경계 돌이 적을수록 좋습니다 — 평가 함수는 높은 경계 돌 수에 페널티를 부여합니다.

5. 칸 위치 가중치 각 칸은 정적 가중치를 가집니다(코너 ~+20, X칸 ~−6, 엣지 ~+2, 내부 ~0). 이 가중치는 각 플레이어가 차지한 칸을 기반으로 더해집니다.

6. 돌 수 패리티 (엔드게임만) 돌 수는 초반 게임에서 거의 0에 가깝게 가중치가 부여되고 엔드게임에서 주요 요소가 됩니다.

가중치 조율

다른 리버시 AI 프로그램은 다른 평가 함수 가중치를 사용합니다. 가중치는 다음과 같이 결정될 수 있습니다:

수작업 조율: 인간 전문가가 어떤 특성이 가장 중요한지 추정
자기 플레이 훈련: AI가 자신과 수백만 번 대전하며 결과에 따라 가중치 조정
데이터베이스에서 학습: 수천 건의 고수준 인간 게임 분석에서 도출된 가중치

유명한 Logistello 프로그램(1990년대)은 게임 포지션으로 훈련된 대규모 특성 데이터베이스 사용을 도입했습니다 — 수작업으로 조율된 함수에 비해 큰 발전이었습니다.

엔드게임 완벽 풀기

강력한 리버시 AI와 약한 AI의 가장 중요한 차이는 엔드게임 풀기입니다: 가능한 모든 수 시퀀스에 대한 정확한 최종 돌 수를 계산하는 능력.

엔드게임 풀기가 활성화되는 시점

일정 수의 빈 칸이 남으면(프로그램의 속도에 따라 일반적으로 20~25개), AI는 휴리스틱 평가에서 정확한 계산으로 전환합니다. 남은 수의 가능한 모든 시퀀스를 탐색하고 최종 돌 수를 최대화하는 것을 찾습니다.

이것이 가능한 이유:

빈 칸이 20개인 경우, 해당 상태에서 고려해야 할 포지션이 최대 ~10^20개 — 효율적인 알고리즘으로 관리 가능
평가는 정확합니다(돌 세기) — 근사치가 아님
수 순서와 가지치기 기술은 강한 수가 더 예측 가능하기 때문에 엔드게임에서 특히 잘 작동함

결과: 강력한 리버시 AI는 엔드게임을 완벽하게 플레이합니다. 어려운 AI를 상대로 마지막 20수에서 지고 있다면, 그것은 실수를 하는 것이 아닙니다 — 모든 대응이 최적입니다.

엔드게임 풀기 기법

Negamax: 엔드게임 계산에 사용되는 미니맥스의 단순화된 공식
최속우선 휴리스틱: 상대방의 응수가 가장 적은 수를 플레이 — 분기 계수를 극적으로 줄임
NWS (Null Window Search): 좁은 윈도우(알파 = X, 베타 = X+1)로 탐색하여 수가 임계값보다 좋은지 나쁜지 빠르게 결정
전치 테이블: 이전에 계산된 포지션을 캐시하여 중복 계산 방지

현대적 접근: 신경망

더 최근의 리버시 AI 구현은 DeepMind의 AlphaZero(원래 체스와 바둑을 위한)의 성공에서 차용하여 신경망 기반 평가를 적용합니다.

작동 방식:

신경망은 자기 플레이로 훈련됩니다 — AI가 자신과 수백만 번 대전
네트워크는 수작업으로 만든 특성 없이 포지션 평가 방법을 학습
순수 미니맥스 대신 수 선택을 위해 몬테카를로 트리 탐색(MCTS)과 결합

전통적 AI에 비한 장점:

수작업 평가 함수가 놓치는 복잡한 포지셔널 패턴 포착 가능
지속적인 자기 플레이를 통해 자동으로 향상
특성 설계에 인간 전문 지식 불필요

현재 상태: 신경망 리버시 AI는 활발한 연구 분야입니다. 강력한 평가 함수를 가진 전통적인 알파-베타 프로그램은 여전히 매우 경쟁력 있습니다. 특히 리버시의 완벽한 엔드게임 풀기가 매우 효과적이기 때문입니다.

인간 플레이어에게 이것이 의미하는 것

리버시 AI의 작동 방식을 이해하면 실용적인 시사점이 있습니다:

AI가 “치팅"하는 것이 아닙니다 — 같은 규칙으로 같은 게임을 플레이합니다. 단지 더 깊이 탐색하고 더 정확하게 평가할 뿐입니다.

강력한 AI를 상대로 엔드게임은 승산이 없습니다 — 엔드게임 솔버가 활성화되면, 당신은 그것을 계산으로 능가할 수 없습니다. 대신 포지셔널 우위로 엔드게임에 진입하는 데 집중하세요.

AI의 약점은 평가에 있지 계산에 있지 않습니다 — 어려운 AI는 전술적 실수를 하지 않습니다. 하지만 그 포지셔널 평가는 때로 복잡한 중반 포지션에서 직관에 반하는 수를 만들 수 있습니다. 바로 여기서 인간의 창의성이 AI가 과소평가하는 수를 때때로 찾습니다.

AI 게임을 연구하면 AI가 사용하는 것과 같은 원칙을 배울 수 있습니다 — 코너 장악, 기동성, 안정적인 돌, 경계 최소화. AI의 평가 함수는 기본적으로 모든 리버시 전문가가 이미 알고 있는 것의 공식화된 버전입니다.