Adversarial Search

Pacman algorithm

minimax, alphabeta, expectimax

Adversarial search

적이 있을 때 승리하기 위한 알고리즘, "Game Search" 라고도 함

상대방의 행동을 예측하고 해당 예측을 바탕으로 이익을 최대화하는 게 목적

필요한 요소는 아래와 같다.

• S0, 초기 상태: 시작 시점에서의 게임의 설정
• To_Move(s): 상태 s에서 수를 둘 플레이어
• Actions(s): 상태 s에서 가능한 수들의 집합
• Result(s, a): 상태 s에서 수(동작) a를 취해서 나오는 결과
• Terminal Test: 종료 판정, 게임이 끝난 상태를 'Terminal State'
• Utility(s, p): 효용 함수, 종료 상태 s로 끝난 게임에서 최종 점수

MiniMax Agent

MiniMax Agent는 항상 utility를 최대화하는 player(pacman)와 최소화하는 방향인 opponent(ghost)의 경쟁이다.

Pacman은 현재 상태에서 말단 노드까지 탐색하여 결과를 얻고 backtracking을 통해서 현재 상태까지 돌아와서 다음 행동을 선택한다.

  def Action(self, gameState):

    # Action 함수는 루트 노드의 역할

    # 1. 현재 Pacman이 할 수 있는 모든 행동을 찾는다.
    # 2. 작성한 minimax 함수에 이를 대입하여 탐색한다.
    # 3. Max value를 선택하여 행동한다.

    move = gameState.getLegalActions() # default agent is pacman
    utility = [self.MiniMax(0, 0, gameState.generatePacmanSuccessor(action)) for action in move] # call minimax from root node
    max_value = max(utility)
    Index=[index for index in range(len(utility)) if utility[index]==max_value]
    get_index=random.choice(Index)

    return move[get_index]
    
    # getLegalActions는 agent를 인자로 받는데 default가 pacman
    # 인자로 받은 agent가 할 수 있는 모든 행동을 반환한다.
    # generatePacmanSuccessor(action)은 행동을 했을 때의 상태를 반환한다.

MiniMax 함수 내부에서는 agent에 따른 전략을 선택한다.

  def MiniMax(self,agent, depth, gameState):
    # Terminal Test
    if gameState.isLose() or gameState.isWin() or depth==self.depth:
      return self.evaluationFunction(gameState)
    # Pacman
    # select max value
    if agent==0:
      return max(self.MiniMax(1, depth,gameState.generateSuccessor(0,action)) for action in gameState.getLegalActions())
    # Ghost
    # select min value
    else:
      next_agent=agent+1
      if gameState.getNumAgents()==agent+1:
        next_agent=0
        # one cycle end then increase depth
        depth+=1
      return min(self.MiniMax(next_agent, depth, gameState.generateSuccessor(agent,action)) for action in gameState.getLegalActions(agent))

AlphaBeta pruning

AlphaBeta pruning은 MiniMax 방법의 일종으로 불필요한 탐색을 제거하여 알고리즘 실행속도를 향상시킨다.

불필요한 탐색을 정의하면

Max 전략에서는 임시 최대 값보다 큰 값이 나오면 탐색 종료
Min 전력에서는 임시 최소 값보다 작은 값이 나오면 탐색 종료

# Action 함수에서 호출 할 때
# alpha=-무한대 beta=무한대 초기 값을 준다.

  def AlphaBeta(self, agent, depth, gameState, alpha, beta):
    # Terminal Test
    if gameState.isLose() or gameState.isWin() or depth==self.depth:
      return self.evaluationFunction(gameState)
    # pacman
    if agent==0:
      pacman_actions=gameState.getLegalActions()
      tmp=-math.inf
      for action in pacman_actions:
        tmp=max(tmp, self.AlphaBeta(1,depth,gameState.generatePacmanSuccessor(action), alpha,beta))
        alpha=max(alpha,tmp)
        if tmp>=beta:
          break # pruning the redundant branch
      return tmp
    # ghost
    else:
      ghost_actions=gameState.getLegalActions(agent)
      tmp=math.inf
      next_agent=agent+1
      if gameState.getNumAgents()==agent+1:
        next_agent=0
        # end of one cycle
        depth+=1
      for action in ghost_actions:
        tmp=min(tmp, self.AlphaBeta(next_agent,depth,gameState.generateSuccessor(agent,action), alpha,beta))
        beta=min(beta,tmp)
        if tmp<=alpha:
          break # pruning the redundant branch
      return tmp

Expectimax agent

Expectimax agent는 위의 두 에이전트와는 결정 방식이 다르다.

이 에이전트는 상대방이 항상 최적의 선택을 하지 않는다는 가정을 한다.

팩맨에서는 유령이 확률적으로 비합리적인 선택을 할 수 있음을 의미한다.

Expectimax agent에서는 일반적으로 pruning이 가능하지 않다.
모든 가능성을 고려해야 하므로

 def Expectimax(self, agent, depth, gameState):
    #Terminal Test
    if gameState.isLose() or gameState.isWin() or depth==self.depth:
      return self.evaluationFunction(gameState)

    # max와 min 모두 chance 노드로 부터 선택을 해야 한다.
    # chance node는 (probabilty*value)의 총 합
    # probability는 모두 동일한 것으로 계산하므로 평균을 구하는 것과 같다.

    # pacman
    if agent==0:
      pacman_actions=gameState.getLegalActions()
      actions_num=len(pacman_actions)
      return sum(self.Expectimax(1,depth, gameState.generatePacmanSuccessor(action)) for action in pacman_actions)/(actions_num)
    # Ghost
    else:
      next_agent=agent+1
      ghost_actions=gameState.getLegalActions(agent)
      actions_num=len(ghost_actions)
      if gameState.getNumAgents()==agent+1: # end of one cycle
        next_agent=0
        depth+=1
      return sum(self.Expectimax(next_agent, depth, gameState.generateSuccessor(agent, action))for action in ghost_actions)/(actions_num)

위는 AlphaBeta pruning 에이전트의 실행 화면이다.

Pacman이 모든 먹이를 먹으면서 끝이난다.