2. 탐색과 최적화 - 게임에서의 탐색

* 게임 트리: 상대가 있는 게임에서 자신과 상대방의 가능한 게임 상태를 나타낸 트리

 

1. Mini-Max 알고리즘

• Max 노드: 자신에 해당하는 노드. 자기에게 유리하도록 최대값 선택
• Min 노드: 상대방에 해당하는 노드. 최소값 선택
• 단말 노드부터 위로 올라가면서 최대-최소 연산을 반복하며 자신이 선택할 수 있는 
  방법 중 가장좋은 값을 결정 

 

 

2. α-β 가지치기

• 검토해 볼 필요가 없는 부분을 탐색하지 않도록 하는 기법
• 깊이 우선 탐색으로 제한 깊이까지 탐색하면서 α-β 자르기
  α: Max 노드에 대해 정하는 값으로 현재까지 확보한 자식의 값 중 최대값
  β: Min 노드에 대해 정하는 값으로 현재까지 확보한 자식의 값 중 최소
• 예) Min의 현재 노드가 4라면 4보다 작은 값들을 선택할 것이지만, 
  부모 노드가 5이므로 4보다 작은것들이 나와도 부모 노드에 영향을 주지
  않으므로 더 이상 탐색 x 

 

 

3) 몬테카를로 트리 탐색

* 몬테카를로 시뮬레이션

:  특정 확률 분포로부터 무작위 표본 생성하고 이 표본에 따라 행동을 하는 과정을 반복하여

결과를 확인하고 최종 결정을 하는 것.

 

• 탐색 트리를 확장하여 가장 좋아보이는 것을 선택하는 휴리스틱 탐색 방법
• 선택-> 확장 -> 시뮬레이션 -> 역전파의 과정을 거친다.
• 선택: 트리 정책 적용.
  자주 쓰이는 정책(UCB): 승률과 노드 방문횟수 고려하여 선택
• 확장: 트리 정책에 따라 노드 추가
• 시뮬레이션: 기본 정책에 의한 몬테카를로 시뮬레이션 적용
• 역전파: 단말 노드에서 루트 노드까지 올라가면서 승점 반영(노드 업데이트)

 

4) 몬테카를로 트리 검색

: 일정 조건을 만족하는 부분은 트리로 구성하고, 나머지 부분은 시뮬레이션만

-> 조건을 만족하지 않는 부분은 탐색 공간을 축소하기 위해 트리에 추가하지 않음.