Alpha-Beta剪枝算法在井字棋AI中可以提供正确的最优移动。下面是一个使用Alpha-Beta剪枝算法的井字棋AI示例代码:
def minimax(board, depth, alpha, beta, maximizing_player):
if depth == 0 or board.is_game_over():
return evaluate(board)
if maximizing_player:
max_eval = float('-inf')
for move in board.get_valid_moves():
board.make_move(move)
eval = minimax(board, depth - 1, alpha, beta, False)
board.undo_move(move)
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break
return max_eval
else:
min_eval = float('inf')
for move in board.get_valid_moves():
board.make_move(move)
eval = minimax(board, depth - 1, alpha, beta, True)
board.undo_move(move)
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break
return min_eval
def get_best_move(board, depth):
best_move = None
max_eval = float('-inf')
alpha = float('-inf')
beta = float('inf')
for move in board.get_valid_moves():
board.make_move(move)
eval = minimax(board, depth - 1, alpha, beta, False)
board.undo_move(move)
if eval > max_eval:
max_eval = eval
best_move = move
return best_move
在上面的代码中,minimax函数使用递归的方式实现了Alpha-Beta剪枝算法。在每个递归层次中,根据当前玩家是最大化还是最小化玩家,选择最大或最小的评估值,并更新alpha和beta的值来进行剪枝。
get_best_move函数使用minimax函数来找到最佳移动。它遍历所有合法的移动,并计算每个移动的评估值,然后选择评估值最大的移动作为最佳移动。
这样,使用Alpha-Beta剪枝算法的井字棋AI可以提供正确的最优移动。