Building Games With Artificial Intelligence

Using search algorithms in games

; 미래를 예측해 최선의 선택지를 고르는 과정에는 검색 알고리즘이 활용된다. 검색 알고리즘은 여러 요소들을 고려해 가능한 경로 중 최선의 경로를 찾는다. 게임의 진행에 따라 발생 가능한 모든 상황을 트리로 표현한다면 게임은 트리를 검색하는 과정으로 볼 수 있다. 트리의 각 노드는 게임의 진행 방향에 따라 도달 가능한 미래의 상태 중 하나를, 트리의 마지막 노드는 최종 결과를 나타낸다. 검색 알고리즘은 이렇게 구성된 트리를 검색해 게임의 각 단계마다 승리를 위한 최적의 경로를 찾는다.
+) 상대 플레이어가 있다면 이는 매차례 이동경로를 다시 검색해봐야 함을 의미한다.

Combinatorial search

: 검색 알고리즘은 철저한 검색(exhaustive search) 혹은 무차별 검색(brute force search)이라고 불리는 방법을 사용한다. 다시 말해 기본적으로 모든 가능한 경우를 철저히 탐색하고 가능한 모든 선택의 결과를 예측해야한다. 게임이 복잡할수록 계산량이 많아 결과를 빠르게 예측할 수 없다는 것이다. 이 문제를 해결하기 위해서 조합 검색을 사용한다. 이는 휴리스틱을 사용하거나 검색 공간의 크기를 줄여 솔루션 공간을 효율적으로 탐색할 수 있게 한다.

Minimax algorithm

: 그 대표적인 휴리스틱이 바로 미니 맥스 알고리즘이다. 미니 맥스 알고리즘은 두 명의 플레이어가 서로 반대되는 목표를 가지고 승부를 겨룬다고 가정하고 상대방의 목표 달성을 방해하는 것을 목적으로 한다. 승패가 결정되는 말단 노드부터 거슬러 올라가며 선택지별로 점수를 매겨 현재 최적의 선택을 고를 수 있도록 한다.이때 점수는 상대방이 승리하는 상황을 얼마나 쉽게 회피했느냐에 따라 결정된다.

Alpha-Beta pruning

: 미니 맥스는 효율적인 전략이긴 하나 여전히 승리와 무관한 이동 경로까지 탐색에 포함시킨다. 불필요한 노드 탐색을 회피하도록 알고리즘을 디자인하는 것을 가지치기 pruning이라고 한다. 알파-베타 가지치기는 어느 한쪽에게 일방적으로 좋은 경로로는 게임이 진행되지 않을 것이라 가정하고 이러한 경로를 가지치기한다. 알파는 가능한 솔루션의 최대 하한 점수이고 베타는 가능한 솔루션의 회소 상한 점수를 의미하는 매개변수이다. 노트 점수의 추정치가 알파와 베타 사이에 있는지를 판단해 가지치기를 할지 말지를 결정한다.

Negamax algorithm

: 네가맥스 알고리즘은 미니 맥스 알고르짐의 변형이다. 네가맥스는 상대방의 점수를 최소화해 자연스럽게 내 점수를 최대화하는 방향으로 움직인다.

+) 2인용 게임 구축을 위해 easyAI 라이브러리를 설치해 다양한 실습을 진행할 수 있다.

$ pip3 install easyAI