博弈树解决井字棋实例代码

下面是一个使用博弈树解决井字棋问题的示例代码。这个代码使用了 alpha-beta 剪枝算法来加速搜索。

import math

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

# 定义玩家和电脑的标记
player = 1
computer = -1

# 定义博弈树节点类
class Node:
    def __init__(self, board, player):
        self.board = board
        self.player = player
        self.children = []

    # 判断当前节点是否为终止节点
    def is_terminal(self):
        # 如果棋盘已满或者有一方获胜，则为终止节点
        return self.is_full() or self.get_winner() != 0

    # 判断棋盘是否已满
    def is_full(self):
        for i in range(3):
            for j in range(3):
                if self.board[i][j] == 0:
                    return False
        return True

    # 判断当前节点的胜者
    def get_winner(self):
        # 判断行
        for i in range(3):
            if self.board[i][0] == self.board[i][1] == self.board[i][2] != 0:
                return self.board[i][0]

        # 判断列
        for j in range(3):
            if self.board[0][j] == self.board[1][j] == self.board[2][j] != 0:
                return self.board[0][j]

        # 判断对角线
        if self.board[0][0] == self.board[1][1] == self.board[2][2] != 0:
            return self.board[0][0]
        if self.board[0][2] == self.board[1][1] == self.board[2][0] != 0:
            return self.board[0][2]

        # 没有胜者
        return 0

    # 生成子节点
    def generate_children(self):
        for i in range(3):
            for j in range(3):
                if self.board[i][j] == 0:
                    new_board = [[self.board[row][col] for col in range(3)] for row in range(3)]
                    new_board[i][j] = self.player
                    self.children.append(Node(new_board, -self.player))

    # 评估当前节点的价值
    def evaluate(self):
        winner = self.get_winner()
        if winner == player:
            return -1
        elif winner == computer:
            return 1
        else:
            return 0

# 定义 alpha-beta 剪枝搜索函数
def alpha_beta(node, alpha, beta):
    if node.is_terminal():
        return node.evaluate()

    if node.player == computer:
        value = -math.inf
        for child in node.children:
            value = max(value, alpha_beta(child, alpha, beta))
            alpha = max(alpha, value)
            if alpha >= beta:
                break
        return value
    else:
        value = math.inf
        for child in node.children:
            value = min(value, alpha_beta(child, alpha, beta))
            beta = min(beta, value)
            if alpha >= beta:
                break
        return value

# 电脑走棋函数
def computer_move():
    root = Node(board, computer)
    root.generate_children()
    best_value = -math.inf
    best_move = None
    for child in root.children:
        value = alpha_beta(child, -math.inf, math.inf)
        if value > best_value:
            best_value = value
            best_move = child.board
    return best_move

# 主程序循环
while not Node(board, player).is_terminal():
    # 玩家走棋
    print("当前棋盘：")
    for row in board:
        print(row)
    row = int(input("请输入行数："))
    col = int(input("请输入列数："))
    if board[row][col] != 0:
        print("该位置已有棋子，请重新输入！")
        continue
    board[row][col] = player

    # 判断游戏是否结束
    if Node(board, player).is_terminal():
        break

    # 电脑走棋
    print("电脑正在思考......")
    board = computer_move()

# 输出游戏结果
print("最终棋盘：")
for row in board:
    print(row)
winner = Node(board, player).get_winner()
if winner == player:
    print("你赢了！")
elif winner == computer:
    print("电脑赢了！")
else:
    print("平局！")

这段代码可以让电脑和玩家轮流下棋，直到游戏结束。在每个回合开始时，程序会打印当前的棋盘，并提示玩家输入下棋的位置。如果该位置已有棋子，则会提示玩家重新输入。玩家下完棋子后，程序会判断游戏是否结束，如果结束则输出游戏结果；否则，程序会让电脑思考并下棋。最后，程序会输出游戏最终的棋盘以及游戏结果。