Search code examples
javascriptpythoncpseudocodealpha-beta-pruning

Return move as well by changing this pseudocode


Is there a way of rewriting this modified pseudocode so that it returns a move as well as a score? Found here. This is the Alpha-Beta algorithm that is an optimised version of the Minimax algorithm, both of which are used to find the optimal move in perfect information games, like 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

Solution

  • Just the Maximizing Part b/c both are similar

    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