[Multi-Agent Search_2] Minimax (1)

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

Minimax

이제 multiAgents.py 파일 안에서 제공되는 MinimaxAgent 클래스에 적대적 탐색 방법을 작성할 차례입니다. Minimax가 적용된 Pacman은 유령의 수가 몇 개이더라도 적상적으로 작동되어야 하므로, 알고리즘들을 보다 일반화가 되게끔 구현해야 합니다. 특히, Minimax 트리에서 각각의 max layer마다 여러 개의 min layer를 갖게 되는데, 유령의 수가 드러나면 min layer 수도 늘어납니다.

구현이 완료된 코드는 게임에서 트리의 깊이를 임의로 확장시킬 수 있어야 합니다. scoreEvaluationFunction에서 기본적으로 제공되는 self.evaluationFunction을 사용하여 Minimax 트리의 점수를 확인해보십시오. MinimaxAgent는 self.depth와 self.evaluationFunction에 접근할 수 있는 MultiAgentSearchAgent를 제공합니다. Minimax 코드가 적절하게 구현되었을 경우 이 두 변수를 참조하여 작동하니 이를 확인해보기 바랍니다.

단일 탐색은 Pacman이 한번 움직이고 모든 유령들의 반응을 고려하고, 깊이가 2인 탐색은 Pacman이 움직이고 모든 유령들이 반응하는 과정을 두 번 고려합니다.

당신이 구현한 코드가 올바른 개수의 게임 state를 탐사하도록 만드는지를 확인해야 합니다. 이것이 Minimax 알고리즘을 구현하는데 있어서 매우 작은 오류를 감지할 수 있는 유일한 방법입니다. Autograder는 GameState.generateSuccessor를 몇 번 호출하였는지에 대하여 매우 까다롭게 체크할 것입니다. 만약 구현한 코드가 게임 state를 너무 많이 호출하거나 적게 호출할 경우 autograder의 결과는 낮을 것입니다. 구현이 완료된 코드를 테스트하고 디버깅하기 위해서는 아래와 같은 명령어를 실행하십시오.

 

- python autograder.py -q q2

 

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

 

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

 

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

 

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

 

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

Pacman을 테스트할 평가함수는 이미 self.evaluationFunction에 구현되어 있습니다. 이 함수는 변경되어서는 안 되지만, Reflex Agent에서 처럼 Action 보다는 State를 평가한다는 점을 인지하고 있어야 할 것입니다. Reflex Agent는 현재 상태에서의 움직임을 평가하지만, Look-ahead Agent는 미래의 상태를 평가합니다.

MinimaxClassic 게임에서 초기 상태의 minimax 값은 깊이가 1일 때 9, 2일 때 8, 3일 때 7, 4일 때 -492 값을 갖습니다.  Pacman은 깊이가 4인 minimax를 사용한 엄청난 예측을 함에도 불구하고 무조건 이길 수는 없을 것입니다.

 

- python pacman.py -p MinimaxAgent -l minimaxClassic -a depth=4

 

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

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

 

Pacman은 하상 Agent0을 할당받고 다른 Agent들은 번호가 작은 순서대로 움직입니다.

Minimax의 모든 상태는 GameStates로 저장되고, getAction을 통하여 전달되거나 GameState.generateSuccessor를 통하여 생성됩니다. 이번 과제에서는 상태를 단순화하기 위하여 추상화를 사용하지 않습니다.

openClassic 또는 mediumClassic과 같은 큰 사이즈의 게임에서 Pacman은 죽지는 않지만, 힘겹게 게임에서 승리할 것입니다. Pacman은 아무런 성과를 보지 못한 채 주위를 맴돌 수도 있습니다. Pacman은 음식이 바로 옆에 있음에도 불구하고 먹지 않고 주변을 맴돌 수도 있는데, 이는 음식을 먹고 난 후에 어디로 가야 할지를 판단할 수 없기 때문입니다. 만약 이러한 움직임을 보여도 아무런 걱정할 필요가 없습니다. 문제 5에서는 이러한 점들이 깨끗이 해결될 것입니다.

Pacman이 어떻게 움직여도 죽을 것 같다고 판단될 때, 가능한 빠르게 죽어서 게임을 끝내려고 할 것입니다. 왜냐하면 살아있는 시간이 길어지면 지속적으로 페널티를 받아서 점수가 깎이기 때문입니다. 이런 판단이 잘못된 것일 수도 있지만, Pacman은 임의의 유령에 대해서 항상 최악을 가정하고 있습니다.

 

- python pacman.py -p MinimaxAgent -l trappedClassic -a depth=3

 

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

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

 

위와 같은 경우에 Pacman이 가장 가까운 위치의 유령을 향하여 돌진하는 이유를 이해할 수 있어야 할 것입니다.