博弈树搜索算法井字棋python

下面是一个简单的井字棋博弈树搜索算法的Python实现：

# 井字棋博弈树搜索算法

# 定义空格、X和O
EMPTY = 0
PLAYER_X = 1
PLAYER_O = 2

# 定义井字棋棋盘
board = [[EMPTY, EMPTY, EMPTY],
         [EMPTY, EMPTY, EMPTY],
         [EMPTY, EMPTY, EMPTY]]

# 判断当前局面是否是终局
def is_terminal(board):
    for i in range(3):
        if board[i][0] == board[i][1] == board[i][2] != EMPTY: # 判断行是否相同
            return True
        if board[0][i] == board[1][i] == board[2][i] != EMPTY: # 判断列是否相同
            return True
    if board[0][0] == board[1][1] == board[2][2] != EMPTY: # 判断对角线是否相同
        return True
    if board[0][2] == board[1][1] == board[2][0] != EMPTY: # 判断对角线是否相同
        return True
    for i in range(3):
        for j in range(3):
            if board[i][j] == EMPTY:
                return False # 如果有空格，则当前局面不是终局
    return True # 如果所有格子都被占据了，当前局面是终局

# 计算当前局面的得分
def evaluate(board):
    for i in range(3):
        if board[i][0] == board[i][1] == board[i][2] == PLAYER_X: # 如果玩家X连成了一条线
            return 1
        if board[0][i] == board[1][i] == board[2][i] == PLAYER_X: # 如果玩家X连成了一条线
            return 1
        if board[i][0] == board[i][1] == board[i][2] == PLAYER_O: # 如果玩家O连成了一条线
            return -1
        if board[0][i] == board[1][i] == board[2][i] == PLAYER_O: # 如果玩家O连成了一条线
            return -1
    if board[0][0] == board[1][1] == board[2][2] == PLAYER_X: # 如果玩家X连成了一条线
        return 1
    if board[0][2] == board[1][1] == board[2][0] == PLAYER_X: # 如果玩家X连成了一条线
        return 1
    if board[0][0] == board[1][1] == board[2][2] == PLAYER_O: # 如果玩家O连成了一条线
        return -1
    if board[0][2] == board[1][1] == board[2][0] == PLAYER_O: # 如果玩家O连成了一条线
        return -1
    return 0 # 如果没有玩家连成一条线，返回0

# 获取可行的下一步操作
def get_actions(board):
    actions = []
    for i in range(3):
        for j in range(3):
            if board[i][j] == EMPTY:
                actions.append((i, j))
    return actions

# 构建井字棋博弈树
def build_game_tree(board, player):
    node = {}
    node['board'] = board
    if is_terminal(board):
        node['value'] = evaluate(board)
        return node
    if player == PLAYER_X:
        best_value = -float('inf')
        for action in get_actions(board):
            new_board = [row[:] for row in board] # 复制棋盘
            new_board[action[0]][action[1]] = PLAYER_X
            child_node = build_game_tree(new_board, PLAYER_O)
            if child_node['value'] > best_value:
                best_value = child_node['value']
                node['best_action'] = action
            if best_value == 1: # alpha-beta剪枝
                break
    else:
        best_value = float('inf')
        for action in get_actions(board):
            new_board = [row[:] for row in board] # 复制棋盘
            new_board[action[0]][action[1]] = PLAYER_O
            child_node = build_game_tree(new_board, PLAYER_X)
            if child_node['value'] < best_value:
                best_value = child_node['value']
                node['best_action'] = action
            if best_value == -1: # alpha-beta剪枝
                break
    node['value'] = best_value
    return node

# 打印棋盘
def print_board(board):
    print('---' * 3)
    for i in range(3):
        print('|', end=' ')
        for j in range(3):
            if board[i][j] == EMPTY:
                print(' ', end=' ')
            elif board[i][j] == PLAYER_X:
                print('X', end=' ')
            else:
                print('O', end=' ')
            print('|', end=' ')
        print()
        print('---' * 3)

# 主函数
def main():
    print('当前棋盘状态：')
    print_board(board)
    while not is_terminal(board):
        if len(get_actions(board)) == 9: # 如果是第一步，玩家X随意下
            row = int(input('请选择下棋的行（0到2）：'))
            col = int(input('请选择下棋的列（0到2）：'))
            board[row][col] = PLAYER_X
        else:
            game_tree = build_game_tree(board, PLAYER_O)
            action = game_tree['best_action']
            print('电脑下棋：', action)
            board[action[0]][action[1]] = PLAYER_O
        print('当前棋盘状态：')
        print_board(board)
    score = evaluate(board)
    if score == 1:
        print('恭喜你，你赢了！')
    elif score == -1:
        print('很遗憾，你输了！')
    else:
        print('平局！')

if __name__ == '__main__':
    main()

运行上述代码，程序会提示你选择下棋的行和列。如果你选择玩家X，那么你需要手动输入行和列；如果你选择电脑玩家O，那么程序会计算出最佳下棋位置并自动下棋。当游戏结束时，程序会显示胜负结果。