[Search] 게임에서의 탐색
개요
게임에서의 탐색이란 상대방이 있는 상황에서 자신에게 가장 유리한 상태를 탐색하는 것을 말합니다.
한 때 우리를 충격으로 몰아넣었던 초기 알파고도 딥러닝과 함께 게임에서의 탐색 중 몬테카를로 트리 검색을 이용했습니다.
게임 트리
게임 트리란 상대가 있는 게임에서 자신과 상대방의 가능한 게임 상태를 나타낸 트리이다.
이 때 중요한 것은, 많을 수를 볼수록 유리하다는 것입니다. 하지만 각 상황에서 모든 수를 볼 수는 없으므로, 특정 깊이의 수까지 탐색한 후 최선의 상태를 선택합니다.
우리가 앞으로 살펴볼 게임 탐색 알고리즘들은 모두 이 게임 트리 구조를 사용합니다.
Mini-Max 알고리즘
Mini-max 알고리즘에는 MAX 노드와 MIN 노드라는 용어가 등장합니다.
MAX 노드란 자신이 선택할 상황을 나타내는 상태로, 자신에게 가장 유리한 상태를 선택할 것이기 때문에 MAX 노드라고 부릅니다.
MIN 노드란 상대방이 선택할 상황을 나타내는 상태로, 이 경우 상대방에게 가장 유리한, 즉 자신에게 가장 불리한 상태를 선택할 것이기 때문에 MIN 노드라고 부릅니다.
MAX 노드의 값은 자식 노드의 값들 중 가장 큰 값이고, MIN 노드의 값은 자식 노드의 값들 중 가장 작은 값입니다.
Mini-max 알고리즘은 단말 노드부터 위로 올라가면서 최대-최소 연산을 반복하며 최선의 상태를 선택합니다.
즉, 실제적인 값의 계산(평가 함수)은 단말 노드에서만 이루어지고, 그 위의 노드들의 값은 선택으로 결정됩니다.
α-β 가지치기
α-β 가지치기는 알고리즘은 앞서 살펴본 Mini-Max 알고리즘과 같지만, 검토해 볼 필요가 없는 부분을 탐색하지 않는다는 점에서 차이가 있습니다.
앞서 MAX 노드와 MIN 노드의 개념에 대해 알아보았는데, 여기서 이 개념을 활용한 α-cutoff와 β-cutoff라는 용어가 등장합니다.
하나씩 알아보죠.
MAX 노드의 값을 α라 하고, MIN 노드의 값을 β라 합니다. 여기서 α-cutoff와 β-cutoff는 다음과 같이 정의됩니다.
α-cutoff: MIN 노드의 현재 값(β)이 부모 노드(MAX 노드)의 현재 값(α)보다 작거나 같으면, 현재 노드(MIN 노드)의 나머지 자식 노드 탐색 중지β-cutoff: MAX 노드의 현재 값(α)이 부모 노드(MIN 노드)의 현재 값(β)보다 크거나 같으면, 현재 노드(MAX 노드)의 나머지 자식 노드 탐색 중지
그리고 두 cutoff 조건은 다음 하나의 식으로 표현됩니다.
β <= α
처음에는 이해하기 어려울 수 있는데, α란 자식 노드의 값들 중 최대값이고 β란 자식 노드의 값들 중 최소 값이라는 것을 상기하면 이해할 수 있을겁니다.
Mini-Max 알고리즘으로 풀었던 문제를 α-β 가지치기를 이용하면 더 효율적으로 풀 수 있습니다.
몬테카를로 탐색
몬테카를로 시뮬레이션
몬테카를로 탐색을 보기 전에 먼저 몬테카를로 시뮬레이션에 대해 알아야 합니다.
- 특정 확률 분포로부터 무작위 표본을 생성하고,
- 이 표본에 따라 행동을 하는 과정을 반복하여 결과를 확인하고,
- 이러한 결과 확인 과정을 반복하여 최종 결정을 하는 것
유명한 몬테카를로 시뮬레이션 문제로 원의 넓이를 구하는 문제가 있습니다.
몬테카를로 트리 탐색
몬테카를로 트리 탐색 알고리즘 이란 탐색 공간을 무작위 표본 추출하면서, 탐색 트리를 확장하여 최선의 상태를 선택하는 휴리스틱 탐색 방법입니다.
몬테카를로 트리 탐색은 다음 4가지 단계를 계속해서 반복합니다.
- 선택(Selection): 루트 노드에서 시작하여 정책에 따라 자식 노드를 선택하여 단말노드까지 탐색 후 선택
- 확장(expansion): 단말 노드에서 트리 정책에 따라 노드 추가
- 시뮬레이션(simulation): 정책에 의한 몬테카를로 시뮬레이션 적용
- 역전파(backpropagation): 단말 노드에서 루트 노드까지 올라가면서 승점 반영
✋ UCB(Upper Confidence Bound) 정책
몬테카를로 트리 탐색은 가능한 많은 수를 탐색하기 위해 휴리스틱 탐색과 몬테카를로 시뮬레이션을 사용합니다.
이 때 일정 조건을 만족하는 부분은 트리로 구성하고, 나머지 부분은 몬테카를로 시뮬레이션을 수행함으로써 트리의 크기를 적절히 유지하고 탐색 공간을 축소시킵니다.
정리
이상 게임에서의 탐색 기법에 대해 알아보았습니다.
Mini-Max 알고리즘, α-β 가지치기, 몬테카를로 트리 탐색에 대해 알아보았습니다.
이 탐색 알고리즘들은 지금까지 게임 상황에 있어 아주 많이 활용되어 온 알고리즘들입니다.
다음 포스팅에서는 제약 조건 만족 문제에 대해 알아보겠습니다.
Leave a comment