[인공지능] 탐색과 최적화 - 게임에서의 탐색

게임 트리(game tree)

• 상대가 있는 게임에서 자신과 상대방의 가능한 게임 상태를 나타낸 트리 (tic-tac-toe, 바둑, 장기, 체스 등)
• 게임의 결과는 마지막에 결정
• 많은 수(lookahead)를 볼 수록 유리

mini-max 게임 트리

• MAX 노드 = 자신에 해당하는 노드. 자기에게 유리한 최댓값 선택
• MIN 노드 = 상대방에 해당하는 노드. 최소값 선택
• 단말 노드부터 위로 올라가면서 최소(minimum)-최대(maximum)연산을 반복하여 자신이 선택할 수 있는 방법 중 가장 좋은 값을 결정.
• 일반적으로 게임이 끝나는 시점까지 수를 보기 어렵기 때문에, 어느 정도 깊이의 수까지 본 다음에 해당 상태에서 유리한 정도를 판정(휴리스틱 이용)하여 이를 바탕으로 최선의 방법을 선택.

α-β 가지치기(α-β pruning)

• 정해진 깊이까지 DFS로 탐색.
• 해당 깊이에 도달하면, 휴리스틱을 사용하여 해당 노드의 상태에 대한 평가값을 계산.
• 현재 노드와 부모 노드의 값을 비교하여 검토해 볼 필요가 없는 부분을 탐색하지 않도록 한다.
  • α-자르기(cut-off) = MIN 노드의 현재값이 부모 노드의 현재 값보다 작거나 같으면, 나머지 자식 노드 탐색 중지
    • MIN 노드의 부모 노드는 MAX 노드인데, MAX 노드는 자식 노드들의 값 중 가장 큰 값을 가진다. 근데 MIN노드가 MAX노드의 현재 값보다 작거나 같은 값을 가졌다면 MIN 노드는 자식 노드를 아무리 탐색해도 값이 더 작아질 일밖에 없기 때문에 더 탐색해도 부모인 MAX 노드의 값에 영향을 줄 수 없다. 따라서 검토할 필요가 없는 부분을 탐색하지 않도록 하는 것이다.
  • β-자르기 = MAX 노드의 현재값이 부모 노드의 현재 값보다 같거나 크면, 나머지 자식 노드 탐색 중지
    
    • MAX 노드의 부모 노드는 MIN 노드인데, MIN 노드는 자식 노드들의 값 중 가장 작은 값을 가진다. 근데 MAX 노드가 MIN 노드의 현재 값보다 크거나 같은 값을 가졌다면 MAX 노드는 자식 노드를 아무리 탐색해도 값이 더 커질 일밖에 없기 때문에 더 탐색해도 부모인 MIN 노드의 값에 영향을 줄 수 없다. 따라서 검토할 필요가 없는 부분을 탐색하지 않도록 하는 것이다.

 

몬테카를로 시뮬레이션 (Monte Carlo Simulation)

• 형세를 판단하여 수치화하는 것이 어려울 때 무작위적인 시뮬레이션에 의해 유리한 정도를 결정하여 게임 트리를 구성하는 알고리즘.
• 무작위로 게임을 하는 시뮬레이션을 많이 수행한 다음에 승률을 계산하여 단말 노드의 형세 판단 값으로 사용함.
• mini-max 알고리즘과는 다르게 일정 깊이까지 탐색을 하지 않고, 도움이 될 것 같은 부분을 점진적으로 확장해가며 게임 트리를 만들어간다.
• 게임 트리의 각 노드에는 해당 노드를 경유해서 게임을 한 횟수(노드 방문 횟수)와 승률 정보가 기록된다.
• (선택 -> 확장 -> 시뮬레이션 -> 역전파 -> 선택)을 반복한다.
  • 선택(Selection)
    • 루트 노드로부터 아래로 이동하기 위해 자식 노드를 순차적으로 선택하는 것.
    • 현재까지의 승률이 큰 것과 지금까지 방문횟수가 작은 것을 선호하도록 선택 우선순위를 정한다.
    • 우선순위를 정할 때는 UCB(Upper Confidence Bound)라는 식을 사용한다.

    • 

      UCB. 부모의 방문횟수에 비해 너무 적게 방문한 노드에게 기회를 줌.

  • 확장(Expansion)
    • 선택 과정을 통해 마지막에 도달한 노드에 새로운 노드를 추가.
    • 확장 단계로 진입하게 한 수를 단말 노드에서의 트리 정책에 따라 노드 추가. (일정 횟수 이상 시도된 수가 있으면 해당 수에 대한 노드 추가)
  • 시뮬레이션(Simulation)
    • 노드의 형세 평가를 위해 승패가 결정될 때까지 무작위로 게임을 해보는 단계.
    • 무작위 선택 or 약간 똑똑한 방법으로 게임이 끝날 때까지 시뮬레이션한다.
    • 시뮬레이션을 시작한 노드에는 가능한 첫 수의 시도횟수 및 승률을 기록해서 나중에 선택, 확장 단계에서 이 정보를 이용할 수 있도록 한다.
  • 역전파(Backpropagation)
    • 단말 노드에서 루트 노드까지 올라가면서 승점 반영