[인공지능] 게임트리

최대최소 탐색

• 게임이 진행되는 과정에서 나와 상대방은 서로에게 이기기 위해 자신에게 유리한 수를 두려고 한다.
• 나는 내게 가장 유리한 수를 선택하고, 상대방은 내게 가장 불리한 수를 선택하려고 할 것이다.
• 최대최소 탐색에 의한 수의 선택
  • 나와 상대방이 각자에게 최적의 선택을 한다는 가정하에 나에게 최악인 선택(최소가치)을 하는 상대방을 대상으로 나의 결정의 가치가 최대가 되는 결정을 내림

최대최소 탐색 알고리즘

• 깊이우선 탐색
  • 시스템의 가용자원에 따라 얼마나 깊이 탐색 과정을 반복할 것인지 정함
• 트리의 규모가 매우 큰 경우 모든 경우의 수를 탐색하여 종단상태까지 도달할 수 없다.
  • 종단상태 : 더 이상 게임을 진행할 수 없는 상태 (승리, 패배, 무승부가 결정되는 상태)

삼목게임

• 두 사람이 가로/세로 3×3 크기의 판에 교대로 수를 두어 한 행, 열, 또는 대각선을 모두 점유하면 이기는 게임
• 평가함수 F의 정의
  • 승리한 상태 : F = ∞
  • 패배한 상태 : F = -∞
  • 그 외의 경우 : F = W - L
    • W : 이길 가능성이 있는 행, 열, 대각선의 수
    • L : 질 가능성이 있는 행, 열, 대각선의 수

내가 X이고 상대방이 ○일 때, 위 예시의 출발 상태에서 내가 응수할 수 있는 경우가 a,b라고 할 떄,

• a : 내가 X를 (1,1)에 두는 경우
  • 상대방이 응수할 수 있는 경우는 c,d,e,f이다. 이들의 평가함숫값은 각 1,2,1,2이다.
  • 상대방은 나에게 가장 불리한 수(1)를 둘 것이므로 a의 가치는 1이 된다.
• b : 내가 X를 (1,2)에 두는 경우
  • 상대방이 응수할 수 있는 경우는 g,h,i,j이다. 이들의 평가함숫값은 각 -∞,1,0,1이다.
  • 상대방은 나에게 가장 불리한 수(-∞)를 둘 것이므로 b의 가치는 -∞이 된다.
• 다시 출발 상태로 돌아와서, 나는 내게 가장 유리한 수를 두어야 하므로 a,b 중 가치가 가장 높은 a를 선택하고, 출발노드의 가치는 1이 된다.

α-β 가지치기

• 최대최소 탐색트리에서 탐색이 불필요한 가지를 잘라내서 탐색의 성능을 높이기 위한 알고리즘
• α : 어떠한 최대화 노드의 최대화 과정에서 지금까지 구한 가장 큰 가치
• 최대화 노드의 후계노드(최소화 노드)는 α보다 더 큰 가치를 가져야만 그 최대화 노드의 가치가 될 수 있다.
• 최소화 노드에서 어느 한 후계노드의 가치가 v일 때 α≥v라면 그 최소화 노드의 나머지 후계들은 가지치기한다.

• β : 어떠한 최소화 노드의 최소화 과정에서 지금까지 구한 가장 작은 가치
• 최소화 노드의 후계노드(최대화 노드)는 β보다 더 작은 가치를 가져야만 그 최소화 노드의 가치가 될 수 있다.
• 최대화 노드에서 어느 후계노드의 가치가 v일 때 β≤v라면 그 최대화 노드의 나머지 후계노드들은 가지치기한다.

몬테카를로 트리 탐색

• 경험적 탐색 알고리즘
• 방대한 경우의 수가 있는 게임에 사용 (ex. 바둑 알파고)
• 탐색공간의 무작위 표본화를 바탕으로 탐색트리 구성
• 탐사 : 아직 검토해 보지 않은 영역을 들여다봄
• 활용 : 유망한 것으로 보이는 영역을 살펴봄

몬테카를로 트리 탐색 알고리즘

알고리즘은 아래 네 단계로 구성된다.

1. 선택
   • 루트노드에서 시작하여 선택전략에 따라 자식노드를 선택하는 과정을 깊이방향으로 반복한다.
   • 이 선택과정을 아직 시도해 보지 않은 행동이 남아 있는 노드에 도달할 때까지 반복한다.
2. 확장
   • 선택된 노드에 새로운 행동을 함으로써 자식노드를 생성하고 트리에 추가하여 트리를 확장한다.
3. 시뮬레이션
   • 확장된 노드로부터 시작하여 게임이 끝날 때까지 스스로 게임을 진행한다. (롤아웃, 플레이아웃)
   • 모의게임의 결과는 게임에 따라 정의된 점수이다.
4. 역전파
   • 시뮬레이션 결과를 확장된 노드로부터 루트노드까지 선택경로를 따라 역전파하여 통계를 업데이트한다.