지시 ch3) 게임 트리

게임의 정의

- 게임 : 여러 명의 **행위자(플레이어)** 가 규칙(Rules)에 따라 전략(Strategy)을 선택하고, 그 결과로 보상(Payoff)을 받는 수학적 모델

 

- 경쟁적 환경 (Competitive environment) : 각 플레이어가 상대방의 행동을 고려하면서 결정을 내림

- 적대적 검색 (Adversarial Search) : 경쟁적인 환경에서 각 플레이어의 최선의 선택을 찾는 문제

 

- 2인용 제로섬 게임 : 한 플레이어의 승리는 다른 플레이어의 패배

                                  ex) 체스, 바둑, 틱텍토 (Tic-Tac-Toe)

틱텍토 게임의 게임 트리(일부)

 

게임 트리의 크기 (3*3) - 9! (대칭을 제외하면 5478개)

 

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

- 상대방이 최선의 선택을 한다고 가정, 각 단계에서 최선의 선택을 하도록 유도

- 목표 상태 : 승리 상태에 해당하는 리프 노드(Leaf Node)를 찾기

- 탐색 과정 : 상대방의 전략을 고려해가며, 현재 노드에서 최적의 선택을 유도

미니멕스 알고리즘

 

 

연습문제)

연습 문제

 

Min-Max 수도 코드(재귀호출을 통해 구현)

 

Min-Max 알고리즘 분석

- 완결성 : 유한한 탐색 트리 안에서 해답이 존재하면 반드시 찾을 수 있음.

- 최적성 : 최악의 경우에도 가장 좋은 결과를 보장 (승리를 보장하는 것은 아님!)

- 시간 복잡도 : O(b^m)

- 공간 복잡도 :  O(bm)

 

Alpha-Beta Pruning

- Min-Max 알고리즘의 시간 복잡도를 줄이는 기법

- 핵심 아이디어 : 모든 노드를 전부 탐색할 필요 없이, 불필요한 노드를 자르기 위해 α, β 값을 사용

 

• α: 현재까지 확인된 최대값
• β: 현재까지 확인된 최소값

 

자르기 조건 : α  >=  β 일 경우, 더 이상 해당 노드를 탐색할 필요가 없음

 

알파베타 가지치기

 

C에 올라오는 값은 최소값 -> 하지만 C에서 A로 올라가는 값은 최대값

-> 현재 A의 값은 7이고 최소값인 6이 C로 올라옴 -> C에는 최소값만 올라오기 때문에 6보다 큰 숫자가 올라올 수 없음

-> 그러므로 다른 자식 노드들을 평가할 필요가 없음

 

알파베타 수도 코드

 

시험 문제!!!! (ex) 탐색하지 않아도 되는 노드의 개수

연습 문제

 

 

https://pascscha.ch/info2/abTreePractice/