게임 트리와 탐색

• 게임의 정의
  • 여러 행위자가 규칙 내에서 전략을 선택하고, 그 결과에 따라 보상이 결정되는 수학적 모델
  • 경쟁적 환경과 적대적 검색 상황
  • 2인용 제로섬 게임: 한쪽의 승리가 다른 쪽의 패배를 의미 (협동적인 승리는 없음)
  • 예시: 체스, 바둑, 틱택토
    • 최적의 경로를 상대방의 수로 인해 제한될 수 있음
• 게임 트리

  • 예시: Tic-Tac-Toe 게임 트리

    

    • 특징
      • 3x3 보드
      • 한 수를 둘 때마다 가능한 위치 수 감소
      • 전체 경우의 수: 9×8×...×1 = 9! (362,880개)
      • 대칭을 고려하면 약 5478개로 감소

게임 트리 탐색: Min-Max 알고리즘

• 게임 트리 탐색 목표: 승리에 해당하는 리프 노드 탐색

  • 상대방의 선택에 따라 탐색 경로가 바뀌기 때문에 탐색 알고리즘과 다른 접근이 필요함

• Min-Max 기본 원리

  • 일반 탐색 알고리즘과 달리 상대방이 최선의 수를 둔다고 가정

    

  • 내 차례: 최대 이득을 선택

  • 상대 차례: 내 손해를 최소화하는 수를 선택

    

• 예시

  

• 재귀적 구현

  function minimax(node, depth, maxPlayer)
      if depth == 0 or node가 단말 노드면
          return node의 휴리스틱 값
      if maxPlayer then
          value ← -∞
          for each child of node do
              value ← max(value, **minimax(child, depth-1, FALSE)**)
          return value
      else
          value ← +∞
          for each child of node do
              value ← min(value, **minimax(child, depth-1, TRUE)**)
          return value
  

• 특성

  • 완결성: 유한한 트리에서는 항상 해를 찾을 수 있음
  • 최적성: 최악의 경우에도 가장 좋은 결과 보장 (단, 무조건 승리를 보장하지는 않음)
  • 시간 복잡도: O(b^m)
  • 공간 복잡도: O(bm)

Alpha-Beta Pruning

• Min-Max 알고리즘의 시간 복잡도를 줄이기 위해 고안

• 루트 노드(현재 내 턴)의 최적 선택만 필요하다.

  • 서브트리(후속 게임들)는 최적 수를 찾기 위한 계산 수단일 뿐이다.

  • 모든 노드를 평가할 필요 없음 ⇒ 시간 복잡도 O(b^(m/2))

    

    • B의 왼쪽 노드를 평가하면 9이므로 적어도 9보다 같거나 작을 것이다.
    • B의 중간 노드를 평가하면 9이므로 적어도 9보다 같거나 작을 것이다.
    • B의 오른쪽 노드를 평가하면 7이므로 적어도 7보다 같거나 작을 것이다.
    • B의 평가값은 7이되고 A로 전달되게 된다.
    • C의 왼쪽 자식 노드를 평가하면 6이된다. A의 값은 적어도 7인데 C에서 올라올 수 있는 값은 최대 6이다.
    • 따라서 C에 대한 자식을 더 이상 평가하는 것은 무의미하다.

• 핵심 아이디어

  • 현재 최대값(α)과 최소값(β)을 추적
    • Alpha (α): MAX 노드가 보장할 수 있는 현재까지의 최선(최대) 값
      • 루트 노드의 α = -∞
    • Beta (β): MIN 노드가 보장할 수 있는 현재까지의 최선(최소) 값
      • 루트 노드의 β = +∞
  • α ≥ β가 되는 순간, 이후 탐색 생략
    • MAX 노드에서 β ≤ α이면 더 이상 탐색 X
    • MIN 노드에서 α ≥ β이면 더 이상 탐색 X
  • DFS와 같이 왼쪽부터 탐색한다고 가정한다!

  function alphabeta(node, depth, α, β, maxPlayer)
      if depth == 0 or node가 단말 노드면
          return node의 휴리스틱 값
      if maxPlayer then
          value ← -∞
          for each child of node do
              value ← max(value, alphabeta(child, depth-1, α, β, FALSE))
              α ← max(α, value)
              **if α ≥ β then
                  break // β 컷**
          return value
      else
          value ← +∞
          for each child of node do
              value ← min(value, alphabeta(child, depth-1, α, β, TRUE))
              β ← min(β, value)
              **if α ≥ β then
                  break // α 컷**
          return value
  

  • 베타 컷: 최소화 노드에서 α ≥ β 조건이 성립하면 이후 탐색 중단
    • 현재 노드의 최대값이 부모 노드의 값(β)보다 커지게 되면 더 이상 탐색할 필요가 없음
  • 알파 컷: 최대화 노드에서 α ≥ β 조건이 성립하면 이후 탐색 중단
    • 현재 노드의 최소값이 부모 노드의 값(α)보다 작게 되면 더 이상 탐색할 필요가 없음

Alpha-Beta Pruning 문제풀이

[1단계] 트리 구조를 보고 루트 노드가 MAX인지 MIN인지 표시