Game Playing

Game Playing에 AI를 적용하는 이유

인간과 바로 비교할 수 있다

game play은 non-trivial

game is well defined and repeatable

game is limited and accessible

 

One-Ply Search

내가 선택 가능한 case들을 대상으로 evaluation function으로 평가

나에게 제일 유리한 case 선택 => max

 

Two-Ply Search

내가 선택 가능한 case들을 계산하고, 이후 상대방이 선택 가능한 case들까지 계산하여 evaluation fuction으로 평가

상대의 case들 중에서 나에게 제일 치명적인 것을 선택 => min

나에게 치명적인 것들 중에서 나에게 제일 유리한 것을 선택 => max

어차피 지는 경우라면 mini-max 알고리즘이 아닌 다른 알고리즘 적용

 

Mini-Max Algorithm

예상되는 최대의 손실(maximum loss)를 최소화 (minimize) 시키기 위해 사용되는 의사 결정 이론의 한 방법

해당 문제에서 탐색이 끝나면 탐색트리로 부터 최상이라고 추정되는 행동을 찾기 위해, 탐색트리의 단말(leaf) 노드에 정적 평가 함수 (static evaluation function)로 추정값을  얻고 그 단말노드의 가치를 통해 최상의 행동을 찾음

 

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

Mini-max 알고리즘에 의해 평가되는 노드들의 수를 감소시키기 위한 기법

- Alpha Cutoff : 최소값에 의한 pruning

- Beta cutoff : 최대값에 의한 pruning

 

Alpha Cutoff (=Alpha pruning)

minimizing ply에서 일어남

ex) B가 3을 보장하는 상황에서, C의 가능 case중 –5인 case가 존재하면 C의 남은 case들은 연산할 필요 x
-> -5보다 작은 경우가 있으면 minimizing ply이므로–5 보다 작은 case 선택 되어 C<-5, B=3이므로 결국 B가 선택
-> -5보다 큰 경우가 있으면 minimizing ply이므로 C=-5, B=3 이므로 결국 B가 선택

 

Beta Cutoff (=Beta pruning)

maximizing ply에서 일어남

B = -5 일 때, C의 가능 case중 7이 존재하면 C의 남은 case들은 연산할 필요 x
-> 7보다 작은 경우가 있으면 maximizing ply이므로 C=7, B=5이므로 결국 B가 선택됨
-> 7보다 큰 경우가 있으면 maximizing ply이므로 C>7, B=5이므로 결국 B가 선택됨

 

Alternatives to Mini-Max

어차피 지는 게임에서는 Mini-Max 알고리즘 대신 다른 알고리즘 적용