Return 通过更改此伪代码也可以移动

Question

有没有办法重写这个修改后的伪代码，使其 returns 既是一步又是得分？找到 here。这是 Alpha-Beta 算法，它是 Minimax 算法的优化版本，两者都用于寻找完美信息游戏中的最佳着法，例如 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

最小化与最大化非常相似，所以只会做一部分：

  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}

Answer 2

只是最大化部分b/c两者相似

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

Return 通过更改此伪代码也可以移动

Return move as well by changing this pseudocode

javascript

python

c

pseudocode

alpha-beta-pruning