[Multi-Agent Search_4] Expectimax (1)

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

Expectimax

Minimax와 Alpha-Beta Pruning은 훌륭한 알고리즘이지만, 두 알고리즘은 모두 최적의 결정을 하고 있는 적과 게임을 하고 있다고 가정하고 있습니다. 하지만 모든 적들이 항상 최적의 결정을 하는 것은 아닙니다. 이번 과제에서는 Pacman이 최선이 아닌 차선의 방법을 선택할 수 있는 확률론적 행동을 할 수 있게 도와주는 ExpectimaxAgent를 구현해볼 것입니다.

지금까지 여러 과제를 통하여 구현해왔던 다른 탐색 알고리즘과 같이 이번 알고리즘의 장점 또한 일반적으로 다양한 곳에 적용 가능하다는 점입니다. 개발에 도움이 될 수 있는 트리 기반의 몇 가지 테스트 케이스들이 공급될 것입니다. 아래와 같은 명령어를 사용하면 작은 트리 기반의 게임에서 구현한 알고리즘을 확인할 수 있을 것입니다.

 

- python autograder.py -q q4

 

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

python autograder.py -q q4 실행 시 출력 화면

 

이러한 작고 관리하기 쉬운 테스트 케이스에서 디버깅은 버그를 빠르게 찾는데 도움이 될 수 있습니다. 코드를 구현하는 데 있어서 평균값을 계산할 때는 float를 사용해야만 합니다. 파이썬에서 1/2 = 0처럼 정수들을 나눈 결과를 보면 되면 소수점 아래가 잘리게 되지만, float를 사용하면 1.0/2.0 = 0.5 소수점 아랫부분이 그대로 보이기 때문입니다.

구현이 완료된 알고리즘이 작은 트리에서 정상적으로 동작한다면 Pacman 게임에서도 성공적으로 동작하는 것을 확인할 수 있습니다. 물론 랜덤한 유령은 최적화된 minimax 알고리즘으로 움직이지 않기 때문에 그들을 minimax 탐색 알고리즘을 사용하여 모델링하는 것은 적절하지 않을 것입니다. ExpectimaxAgent는 모든 유령의 움직임에 대하여 최솟값을 구하지 않고 기댓값을 구하여 사용합니다. 코드를 단순화하기 위해서 getLegalActions 중에서 무작위로 행동을 선택하는 적을 상대로 실행해보겠습니다.

 

아래의 명령어를 통하여 ExpectimaxAgent가 Pacman을 어떻게 행동하게 하는지를 살펴보십시오.

- python pacman.py -p ExpectimaxAgent -l minimaxClassic -a depth=3

 

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

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

 

이제 유령이 근처에 있을 때 조금 더 무심하게 접근을 관찰해야 할 것입니다. 

당신은 이제 유령과 가까운 곳에서의 조금 더 무신경한 접근을 관찰해야 할 것이다. Pacman이 움직이게 되면 함정에 빠질 수도 있고, 음식을 더 먹을 수도 있다는 것을 알게 될 경우 움직이는 것을 도전해볼 수 있습니다. 이 두 가지 시나리오의 결과는 아래의 명령어로 살펴보십시오. 

 

- python pacman.py -p AlphaBetaAgent -l trappedClassic -a depth=3 -q -n 10

 

python pacman.py -p AlphaBetaAgent -l trappedClassic -a depth=3 -q -n 10 실행 시 출력 화면

 

- python pacman.py -p ExpectimaxAgent -l trappedClassic -a depth=3 -q -n 10

 

python pacman.py -p ExpectimaxAgent -l trappedClassic -a depth=3 -q -n 10 실행 시 출력 화면

 

AlphaBetaAgent는 항상 게임에서 지게 되지만, ExpectimaxAgent는 절반의 확률로 게임에서 이긴다는 것을 발견할 수 있습니다. 이러한 차이를 만든 minimax 상황에서의 행동이 왜 다른지를 이해해야 할 것입니다.

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