게임 인공지능 | 게임 트리와 Minimax - 4주차 강의 정리
이 글은 게임 인공지능 강의 4주차 내용을 정리한 것입니다.
게임 트리와 Minimax 알고리즘 완전 분석
체스나 바둑에서 AI가 어떻게 다음 수를 결정하는지 궁금했던 적이 있을 것이다. 이러한 보드게임 AI의 핵심은 바로 ‘게임 트리’와 ‘Minimax 알고리즘’이다. 이번 포스트에서는 게임 AI가 어떻게 최선의 수를 찾아내는지 그 원리를 파헤쳐본다.
게임 트리란 무엇인가?
게임 트리는 게임 인공지능 개발에서 널리 활용되는 핵심 방법이다. 특히 보드게임에서 그 위력을 발휘한다.
보드게임의 특징
보드게임은 AI에게 매우 적합한 환경을 제공한다:
- 턴 기반 진행: 플레이어가 번갈아가며 수를 두므로 AI가 충분히 생각할 시간이 있다
- 이산적 행동: 연속적인 움직임이 아닌 정해진 선택지 중에서 하나를 고르는 형태다
- 완전 관측: 대부분의 보드게임은 숨겨진 정보 없이 모든 상황이 공개되어 있다
- 안정적 환경: AI가 결정을 내리는 동안 게임 상태가 변하지 않는다
인공지능 역사 속 보드게임
체스, 바둑, 오델로 등의 보드게임은 인공지능 발전에 중요한 역할을 했다. 새로운 보드게임이 개발될 때마다 이를 해결하는 새로운 AI 기법들이 연구되고 있다.
Tic-Tac-Toe로 보는 게임 트리 구조
가장 간단한 예제인 3×3 틱택토로 게임 트리의 개념을 알아보자.
Complete Game Tree(Tic - Tac - Toe)
게임 트리의 구성
- 루트 노드: 빈 상태의 보드 (게임 시작점)
- 자식 노드: X를 놓을 수 있는 9가지 경우
- 손자 노드: 각 경우마다 O를 놓을 수 있는 8가지 경우
틱택토의 경우의 수
이론적으로는 9! = 362,880가지가 가능하지만, 실제로는:
- X 승리: 131,184경우 (51.4%)
- O 승리: 77,904경우 (30.5%)
- 무승부: 46,080경우 (18.1%)
- 총 255,168가지
완전 게임 트리의 한계
틱택토처럼 단순한 게임은 모든 경우를 다 계산할 수 있지만, 체스나 바둑같이 복잡한 게임에서는 불가능하다. 그렇다면 어떻게 해야 할까?
Minimax 알고리즘: 최선의 수를 찾는 방법
복잡한 게임에서는 완전 게임 트리를 만들 수 없다. 이 문제를 해결하기 위해 Minimax 알고리즘을 사용한다.
게임별 복잡도
보드게임의 복잡도는 다음 요소들로 결정된다:
- 보드 크기: 클수록 복잡하다
- 평균 게임 길이: 길수록 복잡하다
- 분기 인수(Branching Factor): 각 턴마다 선택할 수 있는 경우의 수
제한된 깊이 탐색
복잡한 게임에서는 다음과 같이 접근한다:
- 게임 초반: 제한된 깊이까지만 탐색하여 수를 결정
- 게임 중반: 현재 시점부터 제한된 깊이까지 탐색
- 게임 종반: 완전 게임 트리가 가능한 수준이 되면 최선의 수 결정
평가 함수: 승부를 예측하는 핵심
게임이 끝나지 않은 상황에서 어떻게 좋은 수인지 판단할까? 바로 평가 함수를 사용한다.
평가 함수란?
- 현재 게임 상태가 플레이어에게 얼마나 유리한지 점수로 나타내는 함수다
- 게임 전문가의 도메인 지식을 활용해 설계한다
- 다양한 요소를 반영해 계산한다 (기물 배치, 이동성, 안전성, 중앙 점령 등)
평가 함수 설계 과정
- 도메인 지식 수집: 게임 전문가의 경험과 지식을 활용
- 요소 정의: 게임에서 중요한 요소들을 파악
- 수치화: 각 요소를 점수로 변환할 수 있는 방법을 프로그래밍
- 가중치 조정: 각 요소의 중요도에 따라 가중치를 부여
Minimax 원칙의 핵심
Minimax는 간단하지만 강력한 원칙에 기반한다.
기본 원칙
- 나(최대화 플레이어): 평가값을 최대화하는 행동을 선택
- 상대(최소화 플레이어): 평가값을 최소화하는 행동을 선택
- 가정: 평가값이 클수록 A에게 유리, 작을수록 B에게 유리
상대방 관점 고려
Minimax의 핵심은 단순히 내게 유리한 수만 고려하는 것이 아니라, 상대방도 최선의 수를 둘 것이라고 가정하는 것이다. 따라서 상대방이 선택할 가능성이 높은 수를 예측하여 그에 대응하는 최선의 수를 찾는다.
게임 트리 + Minimax의 중요성
이 조합은 보드게임 AI의 표준이 되었다. IBM Deep Blue처럼 체스 전용 하드웨어까지 개발될 정도로 중요한 기법이다.
Minimax 알고리즘 성능 향상 기법
실제 게임에서는 시간 제약이 있기 때문에 성능 최적화가 필수다.
시간과 깊이의 딜레마
- 탐색 깊이 증가: 더 정확한 판단이 가능하지만 시간이 기하급수적으로 증가
- 체스의 경우: 한 수만 더 깊이 탐색해도 계산량이 엄청나게 늘어난다
- 제한 시간: 실제 게임에서는 정해진 시간 안에 수를 둬야 한다
Iterative Deepening (반복적 심화)
시간 관리를 위한 핵심 기법이다:
- 깊이 1부터 시작: 가장 얕은 깊이부터 탐색
- 점진적 확장: 시간이 허용하는 한 깊이를 하나씩 늘려간다
- 시간 초과 방지: 시간이 부족하면 이전 깊이의 결과를 사용
시간 낭비 우려? 실제로는 깊이가 커질수록 이전 단계의 계산 시간은 무시할 수 있을 정도로 작아진다.
Alpha-Beta Pruning (알파-베타 가지치기)
불필요한 계산을 제거하는 혁신적인 기법이다.
핵심 아이디어: 이미 더 좋은 수를 찾았다면, 그보다 나쁠 것이 확실한 경우들은 계산하지 않는다.
효과: 같은 시간에 약 2배 더 깊이 탐색할 수 있거나, 같은 깊이를 절반 시간에 탐색할 수 있다.
현실적 고려사항
평가 함수의 속도
- 평가 함수가 빠를수록 주어진 시간에 더 많은 노드를 평가할 수 있다
- 초당 평가 가능한 노드 수가 AI의 성능을 결정한다
- IBM Deep Blue처럼 하드웨어로 가속화하기도 한다
시간 관리의 중요성
- 시간 초과로 평가가 미완료되면 좋은 수를 놓칠 수 있다
- 정해진 깊이까지 완전히 평가하는 것이 부분적으로 깊게 평가하는 것보다 낫다
- 실시간 게임에서는 시간 관리가 승부를 좌우한다
마무리
게임 트리와 Minimax 알고리즘은 보드게임 AI의 기초이자 핵심이다. 단순해 보이는 원리지만, 평가 함수 설계, 시간 관리, 성능 최적화 등 다양한 요소가 복합적으로 작용하여 강력한 AI를 만들어낸다.
현대의 AlphaGo나 ChatGPT 같은 고도화된 AI도 결국 이러한 기본 원리에서 출발했다. 게임 AI를 이해하는 것은 인공지능 전반을 이해하는 첫걸음이라고 할 수 있다.