이 의사 코드를 변경하여 돌아 가기 move

Question

이 수정 된 의사 코드를 다시 작성하여 점수뿐만 아니라 이동을 반환 할 수 있습니까? 발견 된 here. 이는 Minimax 알고리즘의 최적화 된 버전 인 Alpha-Beta 알고리즘이며 Tic-Tac-Toe과 같은 완벽한 정보 게임에서 최적의 이동을 찾는 데 사용됩니다.

function alphabeta(node, α, β, maximizingPlayer) 
     if node is a terminal node 
      return the value of node 
     if maximizingPlayer 
      v = -∞ 
      for each child of node 
       v = max(v, alphabeta(child, α, β, FALSE)) 
       α = max(α, v) 
       if β ≤ α 
        break 
      return v 
     else 
      v = ∞ 
      for each child of node 
      v = min(v, alphabeta(child, α, β, TRUE)) 
       β = min(β, v) 
       if β ≤ α 
        break 
      return v 

Answer 1

그냥 극대화 파트 B 모두가 당신의 그리스 문자 하나를 들어

function alphabeta(node, a, b, maximizingPlayer) 
    if node is a terminal node 
     return valueOfNode, None 
    if maximizingPlayer 
     v = -∞ 
     for each move in node.possible_moves() 
      child = play(move, TRUE) #True/False respresents if it should make an "x" or an "o" on the board 
      temp_max, _ = alphabeta(child, a, b, FALSE) # "_" means disregard the value 
      if temp_max > v: 
       v = temp_max 
       best_move = move 
      a = max(a, v) 
      if b <= a: 
       break 
     return v, best_move 

Answer 2

최소화 최대화 정말 비슷합니다, 그래서 그냥 한 부분 수행합니다

function alphabeta(node, α, β, maximizingPlayer) 
     if node is a terminal node 
      return { value: value of node, node : node} 
     if maximizingPlayer 
      v = -∞ 
      bestNode = None 
      for each child of node 
       localMax = alphabeta(child, α, β, FALSE) 
       if localMax.value > v 
        v = localMax.value 
        bestNode = localMax.node 

       α = max(α, v) 
       if β ≤ α 
        break 
      return {value : v, node: bestNode}