博弈树搜索算法井字棋代码

以下是基于博弈树搜索算法的井字棋代码示例：

import copy

# 定义棋盘大小
BOARD_SIZE = 3

# 定义玩家和电脑的棋子
PLAYER = 'X'
COMPUTER = 'O'

# 定义博弈树搜索算法的深度
SEARCH_DEPTH = 5

# 初始化棋盘
def init_board():
    board = []
    for i in range(BOARD_SIZE):
        row = []
        for j in range(BOARD_SIZE):
            row.append('-')
        board.append(row)
    return board

# 打印棋盘
def print_board(board):
    for row in board:
        print(' '.join(row))

# 判断当前棋盘状态（胜利、平局或未结束）
def get_game_status(board):
    for i in range(BOARD_SIZE):
        # 检查行
        if board[i][0] != '-' and len(set(board[i])) == 1:
            return board[i][0]
        # 检查列
        if board[0][i] != '-' and len(set([board[j][i] for j in range(BOARD_SIZE)])) == 1:
            return board[0][i]
    # 检查对角线
    if board[0][0] != '-' and len(set([board[i][i] for i in range(BOARD_SIZE)])) == 1:
        return board[0][0]
    if board[0][BOARD_SIZE-1] != '-' and len(set([board[i][BOARD_SIZE-1-i] for i in range(BOARD_SIZE)])) == 1:
        return board[0][BOARD_SIZE-1]
    # 检查平局
    if all([cell != '-' for row in board for cell in row]):
        return 'Tie'
    # 未结束
    return None

# 计算当前棋盘得分
def get_score(board):
    # 如果玩家获胜，则得分为-10
    if get_game_status(board) == PLAYER:
        return -10
    # 如果电脑获胜，则得分为10
    elif get_game_status(board) == COMPUTER:
        return 10
    # 平局得分为0
    else:
        return 0

# 实现博弈树搜索算法
def minimax(board, depth, is_maximizing):
    # 判断是否达到搜索深度或者当前棋盘状态已经结束
    game_status = get_game_status(board)
    if depth == 0 or game_status is not None:
        return get_score(board)
    # 如果当前是电脑的回合
    if is_maximizing:
        best_score = float('-inf')
        for i in range(BOARD_SIZE):
            for j in range(BOARD_SIZE):
                if board[i][j] == '-':
                    # 模拟电脑下棋
                    new_board = copy.deepcopy(board)
                    new_board[i][j] = COMPUTER
                    # 递归搜索
                    score = minimax(new_board, depth-1, False)
                    # 更新最优得分
                    best_score = max(best_score, score)
        return best_score
    # 如果当前是玩家的回合
    else:
        best_score = float('inf')
        for i in range(BOARD_SIZE):
            for j in range(BOARD_SIZE):
                if board[i][j] == '-':
                    # 模拟玩家下棋
                    new_board = copy.deepcopy(board)
                    new_board[i][j] = PLAYER
                    # 递归搜索
                    score = minimax(new_board, depth-1, True)
                    # 更新最优得分
                    best_score = min(best_score, score)
        return best_score

# 实现电脑下棋
def computer_move(board):
    best_score = float('-inf')
    best_move = None
    for i in range(BOARD_SIZE):
        for j in range(BOARD_SIZE):
            if board[i][j] == '-':
                # 模拟电脑下棋
                new_board = copy.deepcopy(board)
                new_board[i][j] = COMPUTER
                # 计算当前得分
                score = minimax(new_board, SEARCH_DEPTH, False)
                # 更新最优得分和最优下法
                if score > best_score:
                    best_score = score
                    best_move = (i, j)
    # 执行最优下法
    board[best_move[0]][best_move[1]] = COMPUTER
    print(f"电脑下棋 ({best_move[0]}, {best_move[1]})")
    print_board(board)

# 实现玩家下棋
def player_move(board):
    while True:
        try:
            row = int(input("请输入行号（从1开始）：")) - 1
            col = int(input("请输入列号（从1开始）：")) - 1
            if row < 0 or row >= BOARD_SIZE or col < 0 or col >= BOARD_SIZE or board[row][col] != '-':
                print("请输入合法的行号和列号！")
                continue
            board[row][col] = PLAYER
            print_board(board)
            break
        except ValueError:
            print("请输入合法的行号和列号！")

# 实现井字棋游戏
def play_game():
    board = init_board()
    print("游戏开始！")
    print_board(board)
    while True:
        player_move(board)
        if get_game_status(board) is not None:
            break
        computer_move(board)
        if get_game_status(board) is not None:
            break
    game_status = get_game_status(board)
    if game_status == 'Tie':
        print("平局！")
    elif game_status == PLAYER:
        print("恭喜你获胜！")
    else:
        print("很遗憾，你输了。")

# 启动游戏
play_game()

在此示例中，我们定义了一个 `minimax()` 函数来实现博弈树搜索算法，并将搜索深度设为了 5。同时，我们还定义了 `computer_move()` 和 `player_move()` 函数来模拟电脑和玩家下棋的过程。最后，我们通过 `play_game()` 函数来实现整个井字棋游戏的流程。