Adversarial search: minimax and alpha-beta pruning
In a two-player, turn-taking game with perfect information, such as tic-tac-toe, one player's gain is the other's loss. Minimax search assumes both players play optimally. The maximizing player, X here, picks the move with the highest value, and the minimizing player, O, picks the lowest. Leaf positions are scored +1 if X has won, −1 if O has won, and 0 for a draw, and the scores are passed up the tree.
Python
LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]
nodes = 0
def winner(board):
for a, b, c in LINES:
if board[a] != "." and board[a] == board[b] == board[c]:
return board[a]
return None
def terminal_score(board):
won = winner(board)
if won:
return 1 if won == "X" else -1
return 0 if "." not in board else None
def minimax(board, player):
global nodes
nodes += 1
score = terminal_score(board)
if score is not None:
return score
other = "O" if player == "X" else "X"
scores = [minimax(board[:i] + player + board[i + 1:], other) for i, cell in enumerate(board) if cell == "."]
return max(scores) if player == "X" else min(scores)
def alphabeta(board, player, alpha, beta):
global nodes
nodes += 1
score = terminal_score(board)
if score is not None:
return score
other = "O" if player == "X" else "X"
value = -2 if player == "X" else 2
for i, cell in enumerate(board):
if cell != ".":
continue
child = alphabeta(board[:i] + player + board[i + 1:], other, alpha, beta)
if player == "X":
value = max(value, child)
alpha = max(alpha, value)
else:
value = min(value, child)
beta = min(beta, value)
if alpha >= beta:
break
return value
start = "X...O...."
nodes = 0
plain = minimax(start, "X")
plain_nodes = nodes
nodes = 0
pruned = alphabeta(start, "X", -2, 2)
print(plain, pruned)
print(plain_nodes, nodes)