인공지능 - 7. 게임 트리

게임을 이용해 인공지능 연구 이유

- 문제가 잘 풀렸는지 판단하기 쉬움

- 많은 지식이 필요없이, 이기는 위치를 탐색 알고리즘으로 찾으면 됨.

- 단순 탐색 알고리즘으론 힘듬.

 

 

최대-최소 탐색 min-max search

- 나는 최대한 유리, 상대도 최대한 유리한 수를 선택한다 판단.

- 각 노드에 가치 부여

- 최대화 : 최대의 가치를 갖는 후계 노드 선택. 현재 노드는 가장 큰 후계노드의 가치를 가짐.

- 최소화 : 상대는 나에게 가장 낮은 가치를 주는 노드 선택할것. 현재 노드는 가장 낮은 후계노드의 가치를 가짐.

- 최대, 최소화를 여러 단계 거쳐 나에게 유리한 수 선택

 

 

 

 

최대 최소 탐색 트리

- 상대방의 응수를 고려하여 결정하는 경우에 대한 트리

- 내가 A를 선택시 상대는 D 선택, 나는 그나마 다른 노드의 최소에 비해 가장 큰 가치를 갖는 J를 선택 할 수 있음.

 

 

 

몬테 카를로 탐색

- 기존의 게임 트리 탐색 : 경우의 수가 방대한 경우 경험적 지식으로 평가 함수 만들기 어려움.

- 의사 결정 문제에서 활용되는 경험적 탐색 알고리즘

- 탐색 공간 무작위 표본화로 탐색 트리 구성

 

 

몬테카를로 트리 탐색 절차

1. 트리는 점증, 비대칭적 방식으로 생성.

2. 매 반복시 루트 노드서 시작하여 적절한 자식 노드를 선택하는 과정을 반복.

3. 리프노드에 도달한 다음 자식 노드를 생성하여 확장.

4. 리프토드 경로 결정 정책은 탐사, 활용을 균형적으로 설계

  * 탐사 exploration : 검사하지 않은 영역을 확인

  * 활용 exploitation : 유망 영역 확인

5. 시뮬레이션 시행 : 새 노드 가치 평가 위하여 몬테카를로 롤아웃 수행. 

  * 몬테카를로 롤아웃 : 무작위 방식으로 게임 깥까지 진행.

6. 시뮬레이션 결과 시작 리프노드에서 루프노드까지 통계치 업데이트에 활용

 => 경험적 지식을 반영한 평가 함수를 사용하지는 않음.

7. 제한에 도달할떄 까지 반복. 도달 시 우수한 행동 선택

  * 제한 : 시간, 메모리, 반복 횟수 등

 

 

 

몬테카를로 트리 탐색 알고리즘

- 노드 n_i : 게임 특정 상태. 그 노드의 현재 가치 v_i, 노드 방문 횟수 N_i 등 포함.

- 루트 노드 하나인 트리로 탐색 시작하여 4단계 수행

1. 선택 : 선택 전략에 따라 깊이 방향으로 자식 노드 선택 반복. 

2. 확장 : 선택된 노드에 추가 행동하여 트리 확장

3. 시뮬레이션 : 확장된 노드에서 게임이 끝날떄까지 게임 진행(롤아웃).

4. 역전파 : 시뮬레이션 결과 시작 노드에서 루트노드까지 선택경로를 따라 업데이트