[AI] Game Playing

1. Game Playing

 - Game Playing은 AI research의 좋은 문제이다. 

 - 결과가 간단하고, 평가하기 쉽다.

 - 특정 시간 안에 decision making을 해야 한다.

2. Game Playing as Searching

 - 두 명이서 하는 턴제보드게임일 때

 - states          : 보드의 상태

 - operators     : 규칙에 맞게 움직이는 경우들

 - initial state    : 현재의 보드 상태 

 - goal state     : 최종적으로 이기거나 지는 상태

3. Minimax Algorithm

 - 현재  상태에서 수행 가능한 operator로 진행했을 때, AI 턴일 때는 점수가 가장 높은 쪽으로, 상대방 턴일 때는 점수가 가장 낮은 쪽으로 가도록 한다.

1) 0 번위치가 현재 보드 상태라고 가정하고, depth는 4까지 탐색한다.

    (네모는 AI의 선택으로 움직일 수 있는 상태들, 동그라미는 상대의 선택으로 움직일 수 있는 상태들이다.)

    (각 네모, 동그라미 속 숫자는 클수록 AI에게 유리하다.)

 2) 왼쪽으로 계속 내려가서 4의 가장 왼쪽 노드까지 내려간다. 10과 무한대를 비교

 3) 3에서 4로 갈때는 상대의 선택이므로 AI에게 가장 불리한 선택을 한다고 가정하고 10을 선택한다.

 4) 그 뒤, 오른쪽을 탐색하고 5라는 결과를 불러온다.

 5) 2에서 3은 AI의 선택이므로 5와 10 중 더 큰 값을 가져온다.

 6) 위 과정을 계속 반복하면 -7이 가장 크므로 -7 쪽으로 움직인다.

4. Alpha-Beta Pruning

 - Minimax algorithm을 기반으로 더 빠르게 노드들을 탐색하기 위한 알고리즘

 1) Alpha Cutoff

   a) 처음 D와 E를 비교했을 때, D가 더 작으므로 B는 5가 된다. ( alpha = 5 )

   b) 그 다음 오른쪽으로 내려가서 F를 탐색한다.

   c) C는 F와 G 중에서 작은 수를 가져온다. F가 4라면 G가 어떤 수라도 C가 4보다 클 수 없다.

   d) 이미 alpha값이 5이므로 C는 4를 가져오고 G를 보지 않는다.

 2) Beta Cutoff 

   a) 처음 H와 I를 비교했을 때, I가 더 크므로 D는 5가 된다. ( beta = 5 )

   b) 그 다음 오른쪽으로 내려가서 J를 탐색한다.

   c) E는 J와 K 중에서 큰 수를 가져온다. J가 10라면 K가 어떤 수라도 E가 10보다 작을 수 없다.

   d) 이미 beta값이 5이므로 E는 10를 가져오고 K를 보지 않는다.