ABP 성능 이슈

오진서·2022년 2월 4일
3

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 하는 것
즉, 탐색 깊이를 줄이는 방법
단 그만큼 난이도는 떨어진다는 단점 존재


참고

스마트 시스템 이론과 응용 - #5 적대적 탐색

profile
안녕하세요

0개의 댓글