Mini-Max procedure, Game playing problem

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

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

- 예를 들어, 체스에서 유용한 특징들은 상대적인 말의 이점, 중심의 제어권, 킹에 의한 중심제어 여부 등이 있는데, 게임트리를 분석할 때 max에 유리한 상태에서는 평가함수 값이 양수, min에 유리한 상태에서는 평가 함수 값이 음수, 그리고 max나 min 어느 편에 특별히 유리하지 않은 상태에서는 0에 가까운 값을 갖도록 하는게 보통임.

- 좋은 첫 번째 행동은 최대최소절차(mini-max procedure)라고 하는 방법에 의해 선정될 수 있음 (Nils J.Nilsson, 1998)

- Game playing problem에서 DFS? BFS? 어떤 것이 유리한가?

- 대부분의 게임에서는 완전한 탐색(승패에 대한) 실질적으로 불가능

- 체스에 대해 완전 그래프는 10^40승의 노드가 있는 것으로 추정됨

- 그래서 DFS(depth-first search)와 BFS(Breadth-first search) 중 하나를 택일해야 한다면?

- 왜 DFS를 선택해야 하는가? 시간 제한과 메모리 제한, 탐색트리에서 노드의 깊이에 대한 제한이 있기 때문임.