[Multi-Agent Search_3] Alpha-Beta Pruning (1)

※ 이 글은 "UC Berkeley CS188 Intro to AI"의 "Project 2: Multi-Agent Search"을 해결하는 과정을 정리한 글입니다.

Alpha-Beta Pruning

AlphaBetaAgent에서 minimax 트리를 조금 더 효율적으로 탐사하기 위해서 alpha-beta pruning를 구현하십시오. 이전과 마찬가지로 알고리즘은 아래의 수도 코드보다 조금 더 일반화가 되어야 할 것이며, 여러 minimize agent들에게 alpha-beta pruning을 적절하게 확장시켜야 할 것입니다.

코드를 잘 구현하였다면 깊이가 3인 alpha-beta pruning 알고리즘이 깊이가 2인 minimax보다 빠른것을 확인할 수 있을 것입니다. 이론적으로는 깊이가 3인 smallClassic 게임에서는 움직입니다 몇 초밖에 걸리지 않거나 더 빠를 수도 있습니다.

 

- python pacman.py -p AlphaBetaAgent -a depth=3 -l smallClassic

 

python pacman.py -p AlphaBetaAgent -a depth=3 -l smallClassic 실행 시 시작되는 게임 화면

python pacman.py -p AlphaBetaAgent -a depth=3 -l smallClassic 실행 시 출력 화면

 

몇몇 선택되는 움직임이 다를수 있지만, 기본적으로 AlphaBetaAgent의 minimax 값은 MinimaxAgent의 minimax 값과 동일합니다. 또한, 앞의 minimax 과제와 동일하게 초기 상태의 minimax 값은 깊이가 1일 때 9, 2일 때 8, 3일 때 7, 4일 때 -492 값을 갖습니다

구현이 완료된 코드가 올바른 수의 상태를 탐색하는지를 확인하기 위해서는 자식노드가 재 정렬되지 않은 상태로 alpha-beta pruning을 하는 것이 중요합니다. 즉, successor state는 항상 GameState.getLegalAction에 의해서 반환된 순서대로 처리되어야 함을 의미합니다. 다시 한번 강조하지만, GameState.generateSuccessor를 필요 이상으로 호출하지 않기를 바랍니다.

autograder에 의해서 탐색된 state 집합과 같아지기 위해서 같은 값일 때 prunning을 해서는 안됩니다.

아래의 수도코드는 이번 과제에서 구현해야 할 알고리즘에 대하여 나타내고 있습니다.

 

Alpha-Beta Pruning의 수도코드

구현이 완료된 코드는 아래의 명령어로 테스트와 디버깅을 해보십시오.

- python autograder.py -q q3

 

python autograder.py -q q3 실행 시 시작되는 게임 화면

 

명령어를 실행하면 게임에서 구현된 알고리즘을 통해 어떻게 움직이는 지를 보여줄 것입니다. 그래픽 없이 실행하고 싶다면 아래와 같은 명령어를 사용해보십시오.

- python autograder.py -q q3 --no-graphics

 

python autograder.py -q q3 --no-graphics 실행 시 출력 화면

 

alpha-beta pruning를 올바르게 구현했을 경우 어떤 테스트에서 Pacman이 게임에서 지게끔 만들 것입니다. 이것은 걱정하지 않아도 됩니다. 게임에서 지더라도 올바른 구현을 했다면 테스트는 통과할 것입니다.