게임 트리

1. 게임트리

• 게임에서 가능한 모든 상태를 트리 구조로 나타낸 것
• 노드 (Node) : 게임 보드의 상태
• 간선 (Edge) : 한 상태에서 다음 상태로의 수
• 특징 : 2인용 게임, zero-sum 게임, 순차적인 게임
• 예시 : Tic-Tac-Toe, 체스, 바둑

2. Min-Max Algorithm

• 최선의 수를 선택하여 승리를 목표
• MAX : 자기 차례에서 가능한 수 중 최대 평가값 선택
• MIN : 상대 차례에서 가능한 수 중 최소 평가값 선택
• 시간 복잡도 :$O(b^m)$ => b는 각 노드에서 가능한 수 , m은 트리의 깊이

3. Tic-Tac-Toe

• 한 수를 두면 가능한 선택지가 줄어드는 유한 상태 문제(Finite State Problem)
• 게임트리 크기는 => 9!
• 시간 복잡도 :$O(b^m)$ => b는 각 노드에서 가능한 수

3. 알파 베타 가지치기 (Alpha-Beta Pruning)

• MIn-Max는 모든 노드를 탐색 -> 비효율적
• α(Alpha), β(Beta) 값을 이용하여 불필요한 탐색 제거
  • MAX는 α 값만 갱신 → β보다 크면 더 이상 탐색 안 함 (β-cut)
  • MIN은 β 값만 갱신 → α보다 작으면 더 이상 탐색 안 함 (α-cut)
• 같은 최적 수를 찾지만 훨씬 효율적

4. 불완전한 결정

• 모든 경우를 계산하지 않고, 일부만 계산 후 추정으로 결정
• 1) 깊이 제한
• 2) 휴리스틱 계산 : 끝까지 계산하지 않았지만, 현재 상태를 점수로 평가해서 좋고 나쁨을 판단