α-β剪枝算法井字棋

以下是使用Alpha-Beta剪枝算法实现井字棋的示例代码：

# 定义玩家和电脑的标记
player = "X"
computer = "O"

# 初始化棋盘
board = [" " for i in range(9)]

# 打印棋盘
def print_board():
    row1 = "|".join(board[0:3])
    row2 = "|".join(board[3:6])
    row3 = "|".join(board[6:9])
    print(row1)
    print("-" * 5)
    print(row2)
    print("-" * 5)
    print(row3)

# 判断是否有空位
def has_space():
    return " " in board

# 判断是否有获胜者
def has_winner():
    # 判断行
    for i in range(0, 9, 3):
        if board[i] == board[i+1] == board[i+2] != " ":
            return True
    # 判断列
    for i in range(3):
        if board[i] == board[i+3] == board[i+6] != " ":
            return True
    # 判断对角线
    if board[0] == board[4] == board[8] != " " or board[2] == board[4] == board[6] != " ":
        return True
    return False

# 评估函数
def evaluate():
    if has_winner():
        if player == "X":
            return 0
        else:
            return 2
    else:
        return 1

# 极小化极大算法
def minimax(alpha, beta, depth, is_maximizing):
    if has_winner():
        return evaluate()
    elif not has_space():
        return evaluate()
    elif depth == 0:
        return 1

    if is_maximizing:
        best_score = -float("inf")
        for i in range(9):
            if board[i] == " ":
                board[i] = computer
                score = minimax(alpha, beta, depth-1, False)
                board[i] = " "
                best_score = max(score, best_score)
                alpha = max(alpha, score)
                if beta <= alpha:
                    break
        return best_score
    else:
        best_score = float("inf")
        for i in range(9):
            if board[i] == " ":
                board[i] = player
                score = minimax(alpha, beta, depth-1, True)
                board[i] = " "
                best_score = min(score, best_score)
                beta = min(beta, score)
                if beta <= alpha:
                    break
        return best_score

# 电脑下棋
def computer_move():
    best_score = -float("inf")
    best_move = None
    for i in range(9):
        if board[i] == " ":
            board[i] = computer
            score = minimax(-float("inf"), float("inf"), 5, False)
            board[i] = " "
            if score > best_score:
                best_score = score
                best_move = i
    board[best_move] = computer

# 玩家下棋
def player_move():
    valid_move = False
    while not valid_move:
        move = input("请输入你的下棋位置(1-9): ")
        try:
            move = int(move) - 1
            if move >= 0 and move <= 8 and board[move] == " ":
                board[move] = player
                valid_move = True
            else:
                print("无效的位置，请重新输入！")
        except:
            print("无效的输入，请重新输入！")

# 游戏循环
while True:
    print_board()
    player_move()
    if has_winner():
        print_board()
        print("你赢了！")
        break
    elif not has_space():
        print_board()
        print("平局！")
        break
    computer_move()
    if has_winner():
        print_board()
        print("电脑赢了！")
        break
    elif not has_space():
        print_board()
        print("平局！")
        break

在这个示例中，我们使用了极小化极大算法和Alpha-Beta剪枝算法来实现井字棋游戏。玩家使用X标记，电脑使用O标记。玩家和电脑轮流下棋，直到有一方获胜或者平局。在每次电脑下棋时，我们使用Alpha-Beta剪枝算法来遍历博弈树，以提高搜索效率。