Tic Tac Toe의 Simplify MiniMax 알고리즘

Question

완벽하게 작동하는 Tic Tac Toe 게임이 있지만 가지고있는 MiniMax 알고리즘을 변경할 수있는 방법이 있습니다. 따라서 어떤면에서는 더 간단하고 심지어 단락 된 경우도 있습니다.

def maximized_move(self,gameinstance): 
    ''' Find maximized move'''  
    bestscore = None 
    bestmove = None 
    for m in gameinstance.get_free_positions(): 
     gameinstance.mark(self.marker,m) 

     if gameinstance.is_gameover(): 
      score = self.get_score(gameinstance) 
     else: 
      move_position,score = self.minimized_move(gameinstance) 

     gameinstance.revert_last_move() 

     if bestscore == None or score > bestscore: 
      bestscore = score 
      bestmove = m 
    return bestmove, bestscore 
def minimized_move(self,gameinstance): 
    ''' Find the minimized move''' 
    bestscore = None 
    bestmove = None 
    for m in gameinstance.get_free_positions(): 
     gameinstance.mark(self.opponentmarker,m) 

     if gameinstance.is_gameover(): 
      score = self.get_score(gameinstance) 
     else: 
      move_position,score = self.maximized_move(gameinstance) 

     gameinstance.revert_last_move() 

     if bestscore == None or score < bestscore: 
      bestscore = score 
      bestmove = m 
    return bestmove, bestscore 

Answer 1

당신이 알파 베타 가지 치기 봐보세요/최적화 최소 최대 속도를 높이기 위해 찾고 있다면 - 같은 너 한테하지만 최적의 바로 가기

누군가가 이미 당신을 위해 이런 짓을했다고 생각

Answer 2

과를 ... 참조 위키피디아 약 Negamax, "two-player 게임의 제로섬 속성에 의존하는 minimax 검색의 변종 형태."

frayn에서

: 탐색의 속도에 만족

SEARCHING_FUNCTION { 
    Decrease depth by 1 
    Loop through all moves 
    Play move 
    if (depth = 0) move_score = static_position_score 
    else move_score = - Opponent's_best_move_score  
    if (move_score > best_move_score) then (best_move = move)   
    Undo Move  
    End of Loop 
    Return best_move_score 
} END