Minimax 알고리즘의 탐색 공간을 줄이기 위해서 Alpha-beta-pruning을 사용함
그럼에도 불구하고, 여전히 상태공간은 넓고, 결국은 terminal state까지 도달해야 된다는 점에서 시간 제약 발생
해결방안
첫 번째
to replace the utility function by a heuristic evaluation function
즉, 말단 노드까지 가서 유틸리티 함수의 가중치를 구하는 것이 아닌 중간에 딱 잘라서 추정치를 구하는 것
-> 추정치를 구하기 위해 휴리스틱 함수 사용
Eval(s) = w₁f₁(s) + w₂f₂(s) + ... + wnfn(s)
체스 같은 가중치와 수 계산이 어느정도 되어진 게임에서 사용할 수 있는 방법
두 번째
to replace the terminal test by a cutoff test
말단 노드까지 가지 않고 적당한 곳에서 cutoff 하는 것
즉, 탐색 깊이를 줄이는 방법
단 그만큼 난이도는 떨어진다는 단점 존재
참고
안녕하세요