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
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