蒙特卡洛树求解五子棋

蒙特卡洛树求解五子棋

蒙特卡洛树搜索（Monte Carlo Tree Search，简称MCTS）是一种基于模拟的搜索算法，常用于解决决策过程中的优化问题，特别是在那些具有庞大搜索空间且难以用传统方法（如动态规划）有效解决的问题中。MCTS通过从初始状态开始，模拟多个可能的游戏或决策过程，逐步构建搜索树，并利用随机采样来估计各状态或动作的价值，以此来指导搜索过程。蒙特卡洛树搜索的核心思想是利用随机模拟（即蒙特卡洛方法）来估计节点的价值，蒙特卡洛树搜索因其简单高效的特点，在游戏AI领域（如围棋程序AlphaGo）和其他决策优化问题中得到了广泛应用。它通过逐步构建搜索树并利用随机模拟来优化决策，特别适合处理那些难以用精确数学模型描述的问题。

注意：本文用到了PyTorch库，gym强化学习环境库，需要提前安装。

• gym环境安装：https://github.com/Farama-Foundation/Gymnasium
• gym环境介绍文档：https://gymnasium.farama.org/environments/classic_control/mountain_car/
• pytorch官网：https://pytorch.org/

本文所使用的python版本为3.11.8

step1：gym创建五子棋环境

如何利用gym构建自己的环境，可以参考官方地址（创建你自己的环境）：https://gymnasium.farama.org/tutorials/gymnasium_basics/environment_creation/

下面我们简单设计了一个五子棋环境：

import numpy as np  
import gymnasium as gym  
from gymnasium import spaces  
import matplotlib.pyplot as plt  
  
class GomokuEnv(gym.Env):  
    '''
    五子棋强化学习交互环境
    '''
    metadata = {'render.modes': ['human']}  
  
    def __init__(self, board_size=15, win_length=5, player=1):  
        '''
        board_size为棋盘尺寸
        win_length为获胜条件，即连续多少个棋子连成一线
        '''
        self.board_size = board_size  # 棋盘尺寸
        self.win_length = win_length  # 获胜长度
        self.board = np.zeros((board_size, board_size))  # 创建棋盘
        self.current_player = 1  # 1 for player 1, -1 for player 2  
        self.done = False  # 判断游戏是否结束
        self.winner = None  # 获胜者
        self.player = player  # 玩家
  
        # Define action and observation spaces  
        self.action_space = spaces.Discrete(board_size * board_size)  
        self.observation_space = spaces.Box(low=0, high=1, shape=(board_size, board_size), dtype=np.int8)  
  
    def step(self, action):  
        # Convert action into 2D board coordinates  
        x, y = divmod(action, self.board_size)  
        # Place a stone for the current player  
        self.board[x, y] = self.current_player  
        # Check for winning condition or draw  
        self.winner = self._check_winner()  
        if self.winner:  
            self.done = True  
            if self.winner == 0:  # Draw  
                reward = 0  
            else:  # Winner  
                reward = 1 if self.winner == self.player else -1  
        else:  
            reward = 0  
            # Switch player  
            self.current_player *= -1  
  
        return self.board, reward, self.done, {}  
  
    def reset(self):  
        self.board = np.zeros((self.board_size, self.board_size))  
        self.current_player = 1  
        self.done = False  
        self.winner = None  
        return self.board  
  
    def render(self, mode='human'):  
        if mode == 'human':  
            plt.imshow(self.board, cmap='binary')  
            plt.show()  
  
    def _check_winner(self):  
        directions = [(0, 1), (1, 0), (1, 1), (1, -1)]  # Horizontal, Vertical, Diagonal \ and /  
        for x in range(self.board_size):  
            for y in range(self.board_size):  
                if self.board[x, y] == 0:  
                    continue  
                for dx, dy in directions:  
                    count = 1  
                    for i in range(1, self.win_length):  
                        nx, ny = x + dx * i, y + dy * i  
                        if 0 <= nx < self.board_size and 0 <= ny < self.board_size and self.board[nx, ny] == self.board[x, y]:  
                            count += 1  
                        else:  
                            break  
                    if count == self.win_length:  
                        return self.board[x, y]  
        # Check for draw  
        if np.all(self.board != 0):  
            return 0  
        return None 

  
    def close(self):  
        pass

让我们简单看看该环境的用法吧。

import numpy as np
import gymnasium as gym  

# 创建一个五子棋环境
env = GomokuEnv()

# 随机策略
def random_action(observation):
    board_size = observation.shape[1] 
    empty_cells = np.argwhere(observation == 0)
    indices = [y * board_size + x for y, x in empty_cells]
    return np.random.choice(indices)

# 模拟两个玩家进行一局游戏
winner1 = []
winner2 = []
for i in range(2):
    observation = env.reset()
    while True:
        action = random_action(observation)
        observation, reward, done, _ = env.step(action)
        if done:
            if reward == 1:
                winner1.append(i)
            elif reward == -1:
                winner2.append(i)
            break

import matplotlib.pyplot as plt
%matplotlib inline
from IPython import display
plt.imshow(observation) 

step2：蒙特卡洛树

蒙特卡洛树搜索（Monte Carlo Tree Search，简称MCTS）是一种基于概率和统计理论方法的计算技术，它使用随机数（或更常见的伪随机数）来解决多种计算问题。这种搜索算法通过构造符合一定规则的随机数来模拟实际物理过程，以求得问题的近似解。蒙特卡洛树搜索的核心思想是使用随机数来模拟复杂问题的不确定性，并通过大量模拟实验来获取问题的近似解。它从一个初始状态开始，通过模拟游戏或物理过程的各种可能走法，构建一个搜索树。这个搜索树的每个节点代表一个可能的状态，而边则表示从一个状态到另一个状态的可能转移。在搜索过程中，蒙特卡洛树搜索会评估每个节点的价值，这通常是通过模拟从该节点开始到游戏结束的过程，并计算获胜的概率或其他相关指标来实现的。

蒙特卡洛树搜索通常包括以下四个主要步骤：

1. 选择（Selection）：从根节点开始，根据一定的策略（如UCB1算法）选择子节点，直到到达一个尚未扩展的叶节点。这个过程中，算法会倾向于选择那些具有较大潜在价值的节点。
2. 扩展（Expansion）：在选定的叶节点上创建一个或多个新的子节点，以扩展搜索树的范围。这些新的子节点代表了从当前状态出发的可能后续状态。
3. 模拟（Simulation）：从扩展后的叶节点开始，进行随机模拟直到游戏结束。这个过程也被称为rollout或playout，其目的是评估当前状态的潜在价值。模拟的结果将被用来更新搜索树中相关节点的信息。
4. 反向传播（Backpropagation）：将模拟的结果从叶节点开始逐层向上传播到根节点，更新沿途所有节点的统计信息。这个过程有助于算法更好地了解每个状态的价值，并在后续搜索中做出更明智的决策。

对于五子棋游戏，由于其状态空间较大，可以执行选择、模拟和反向传播步骤。在选择步骤中，我们按照一定的规则选择下一步棋的位置；在模拟过程中，我们随机下棋，完成一局游戏；在反向传播过程中，我们根据游戏结果更新搜索树中每个节点的信息。通过不断重复这个过程，我们可以逐渐优化我们的搜索策略，从而提高在五子棋游戏中的表现。

在选择过程中，我们会选择如下情形作为节点：

我们选择我方及敌方有可能出现的上述情形点位置进行落子，包括直连及斜连的所有情况。

• 首先，当判断敌方或我方落子可能出现win的情况时，优先选择落子，不进行蒙特卡洛搜索过程；
• 当没有以上状况时，选择合适的落子位置，进行蒙特卡洛搜索过程。

在程序设计中，不难发现，寻找节点需要寻找当前棋盘上已经落子区域的所有邻接点位置，只是不同的邻接点位置，其落子效果不同形成的情形不同，这交给后续的模拟过程去完成。我们需要做的是找到所有落子点，判断是否可以让自己或对方获胜，如果可以，则优先选择落子，否则进行后续的蒙特卡洛搜索过程。

首先，参照五子棋的规则，我们定义一个函数来检查棋盘上是否有玩家获胜。函数check_winner接受一个二维数组board作为输入，该数组表示当前棋盘的状态。数组中的每个元素代表棋盘上的一个格子，其中0表示空格，1表示一方，-1表示另一方。函数的返回值是一个整数，表示获胜的玩家，如果没有人获胜，则返回0。

函数首先定义了一个列表directions，用于存储检查获胜方向的顺序。然后，使用random.shuffle()函数打乱directions的顺序，避免总是先检查水平方向。

接下来，遍历棋盘上的每个格子，如果格子为空，则跳过该格子。对于每个非空格子，检查其周围8个方向上是否有连续的相同颜色的棋子，如果有，则将计数器加1。如果计数器大于等于5，则表示该玩家获胜，返回该玩家的颜色。

遍历完棋盘上的所有格子后，如果没有找到获胜的玩家，则返回0。

import copy
import random
def check_winner(board):
    '''检查棋盘是否有玩家获胜，并返回获胜的玩家'''
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    # 打乱方向顺序，避免总是先检查水平方向
    random.shuffle(directions)
    for x in range(board.shape[0]):
        for y in range(board.shape[1]):
            if board[x, y] == 0:
                continue
            for dx, dy in directions:
                count = 1
                for i in range(1, 5):
                    nx, ny = x + dx * i, y + dy * i
                    if 0 <= nx < board.shape[0] and 0 <= ny < board.shape[1] and board[nx, ny] == board[x, y]:
                        count += 1
                    else:
                        break
                if count >= 5:
                    return board[x, y]
    return 0

设计一个用于找到五子棋游戏所有可能落子位置的函数。五子棋是一种两人对弈的棋类游戏，棋盘为15x15的网格，每个格子可以放置黑子或白子。

函数find_possible_moves接受一个二维数组board作为输入，该数组表示当前棋盘的状态。数组中的每个元素代表棋盘上的一个格子，其中0表示空格，1表示黑子，-1表示白子。函数返回一个列表possible_moves，其中包含所有可能的落子位置，每个位置表示为一个元组(x, y)。

函数首先定义了一个空列表possible_moves，用于存储所有可能的落子位置。然后定义了一个列表directions，用于存储方向。接着使用random.shuffle()函数打乱directions的顺序，避免总是先检查水平方向。

接下来，遍历棋盘上的每个格子，如果格子为空，则检查其周围8个方向上是否有棋子，如果有，则将该格子添加到possible_moves列表中。

遍历完棋盘上的所有格子后，如果没有找到可能的落子位置，则返回棋盘上所有空的位置。

def find_possible_moves(board):
    '''找到所有可能的落子位置，board为棋盘，board为np二维数组'''
    possible_moves = []
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    random.shuffle(directions)
    for x in range(board.shape[0]):
        for y in range(board.shape[1]):
            if board[x, y] == 0:
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < board.shape[0] and 0 <= ny < board.shape[1] and board[nx, ny] != 0:
                        possible_moves.append((x, y))
                        break
    if len(possible_moves) == 0:
        for x in range(board.shape[0]):
            for y in range(board.shape[1]):
                if board[x, y] == 0:
                    possible_moves.append((x, y))
    return possible_moves

下方设计一个落子评估代码，评估在一个棋盘上，某个玩家在某个位置落子后的得分情况：

1. 定义函数和参数：

   • score_move 是一个函数，它有三个参数：board（棋盘），player（当前玩家），move（落子位置）。

2. 初始化一些变量：

   • directions 是一个包含8个方向的列表，用于检查落子后在各个方向上的情况。这8个方向分别是：右、左、下、上、右下、左下、右上、左上。
   • 使用 random.shuffle(directions) 随机打乱这些方向，这是为了让评估过程更加随机，不那么容易被对手预测。
   • score 初始化为0，这是用来记录最终得分的。
   • x, y 是从 move 中解包出来的，表示落子的具体坐标。

3. 遍历每个方向：

   • 对于 directions 列表中的每个方向 (dx, dy)，都进行以下几步检查：

     1. 初始化临时变量和计数器：

        • temp_check1 和 temp_check2 用于标记是否已经开始记录空白和对手棋子的数量。
        • count 初始化为1，表示当前玩家的棋子数量（因为落子位置肯定有一个当前玩家的棋子）。
        • blank 和 opponent 分别记录空白位置和对手棋子的数量。

     2. 沿当前方向检查5个位置：

        • 使用一个循环，从1到5，沿当前方向逐步检查。
        • nx, ny 是当前检查位置的坐标。
        • 如果当前位置在棋盘范围内，并且是当前玩家的棋子，且还没有开始记录空白（temp_check1 为0），则增加 count。
        • 如果当前位置是空白，则增加 blank，并且设置 temp_check1 为1，表示开始记录空白了。
        • 如果当前位置是对手的棋子，则增加 opponent，并且设置 temp_check2 为1，表示开始记录对手的棋子了。

     3. 根据检查结果更新得分：

        • 如果 count 大于等于5，说明当前玩家形成了长连或五连，加10000分。
        • 如果 count 等于4，并且至少有一个空白，说明是活四，加1000分。
        • 如果 count 等于3，并且至少有一个空白，说明是活三，加100分。
        • 如果 count 等于2，并且至少有一个空白，说明是活二，加10分。
        • 如果 count 等于1，并且至少有一个空白，说明是活一，加1分。
        • 对于对手的情况也类似，只是分数有所不同。

4. 返回最终得分：

   • 遍历完所有方向后，返回 score，即当前落子位置的评估得分。

简单来说，函数就是通过检查当前玩家在某个位置落子后，在各个方向上形成的连续棋子情况，以及对手的连续棋子情况，来计算出一个得分，用于评估这个落子位置的好坏。

def score_move(board, player, move):
    '''评估落子位置的得分，board为棋盘，player为当前玩家，move为落子位置'''
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    random.shuffle(directions)
    score = 0
    x, y = move
    for dx, dy in directions:
        temp_check1 = 0
        temp_check2 = 0
        count = 1
        blank = 0
        opponent = 0
        for i in range(1, 5):
            nx, ny = x + dx * i, y + dy * i
            if 0 <= nx < board.shape[0] and 0 <= ny < board.shape[1] and board[nx, ny] == player and temp_check1 == 0:
                count += 1
            else:
                temp_check1 = 1
                if 0 <= nx < board.shape[0] and 0 <= ny < board.shape[1] and board[nx, ny] == 0:
                    blank += 1
            
            if 0 <= nx < board.shape[0] and 0 <= ny < board.shape[1] and board[nx, ny] == -player and temp_check2 == 0:
                opponent += 1
            else:
                temp_check2 = 1
            
        if count >= 5:
            # 长连或五连情况
            score += 10000
        elif count == 4 and blank >= 1:
            # 活四
            score += 1000
        elif count == 3 and blank >= 1:
            # 活三
            score += 100
        elif count == 2 and blank >= 1:
            # 活二
            score += 10
        elif count == 1 and blank >= 1:
            # 活一
            score += 1
        elif opponent >= 4:
            # 对方长连或五连情况
            score += 10000  # 必须进行落子
        elif opponent == 3 and blank >= 1:
            # 对方活三
            score += 1000
        elif opponent == 2 and blank >= 1:
            # 对方活二
            score += 10
        elif opponent == 1 and blank >= 1:
            # 对方活一
            score += 1
    
    return score

def score_possible_moves(board, player, possible_moves):
    '''评估所有可能落子位置的得分，board为棋盘，possible_moves为所有可能落子位置'''
    scores = []
    for move in possible_moves:
        scores.append(score_move(board, player, move))
    return scores

下边实现一个随机策略来模拟蒙特卡洛搜索过程，用于决定在一个棋盘上的落子位置：

1. 准备阶段：

   • 首先，使用 copy.deepcopy(board) 复制一份当前棋盘 board，得到 temp_board。这是为了避免直接修改原始棋盘。
   • 然后，通过 find_possible_moves(temp_board) 函数找出所有可能的落子位置，存储在 possible_moves 列表中。

2. 检查立即获胜的机会：

   • 遍历 possible_moves 列表中的每个位置 (move_x, move_y)。
   • 对于每个位置，先假设当前玩家 start_player 落子，然后检查是否获胜。如果获胜，则立即返回 start_player。
   • 如果没有获胜，则假设对手落子（用 -start_player 表示），再检查是否对手获胜。如果对手获胜，则立即返回 -start_player。
   • 如果都没有获胜，则将该位置重置为空白（0）。

3. 随机模拟对局：

   • 进入一个无限循环，模拟对局过程。
   • 每次循环开始时，都重新找出当前棋盘上的可能落子位置 possible_moves。
   • 如果 possible_moves 为空，说明棋盘已满或无法继续落子，此时返回 start_player（可能表示当前玩家因棋盘状态无法分出胜负而默认获胜，具体含义需根据上下文判断）。
   • 如果 possible_moves 的数量大于等于 num_check（这里 num_check 被设置为3，但注意这个值在代码中没有直接定义，可能是个遗漏或应该在函数外部定义），则对这些位置进行评分和排序。
   • 使用 score_possible_moves(temp_board, start_player, possible_moves) 函数为每个可能的位置评分，然后根据分数从高到低排序。
   • 选择得分最高的前 num_check 个位置作为接下来的候选落子位置。
   • 从候选位置中随机选择一个位置 (move_x, move_y)，假设当前玩家落子。
   • 检查当前玩家是否获胜。如果获胜，则返回 start_player。
   • 如果没有获胜，则继续找出对手的可能落子位置，并进行类似的评分、排序和随机选择过程，但这次是为对手落子。
   • 检查对手是否获胜。如果对手获胜，则返回 -start_player。

4. 循环继续：

   • 不断重复上述过程，直到某一方获胜或达到其他结束条件（但在提供的代码中，只有获胜条件能终止循环）。

def random_policy(board, start_player):
    '''随机策略，返回一个随机的蒙特卡洛搜索结果'''
    temp_board = copy.deepcopy(board)
    possible_moves = find_possible_moves(temp_board)
    # 当某位置落子后，start_player获胜，则返回该位置
    for move_x, move_y in possible_moves:
        temp_board[move_x, move_y] = start_player
        if check_winner(temp_board) == start_player:
            return start_player
        temp_board[move_x, move_y] = -start_player
        if check_winner(temp_board) == -start_player:
            return -start_player
        temp_board[move_x, move_y] = 0
        num_check = 3

    while True:
        possible_moves = find_possible_moves(temp_board)
        if len(possible_moves) == 0:
            return start_player
        if len(possible_moves) >= num_check:
            # 此时我们对possible_moves进行排序，选择得分较高的位置，然后重置possible_moves
            scores = score_possible_moves(temp_board, start_player, possible_moves)
            possible_moves = [move for _, move in sorted(zip(scores, possible_moves), reverse=True)]
            # 选择得分最高的几个位置
            possible_moves = possible_moves[:num_check]
        move_x, move_y = random.choice(possible_moves)
        temp_board[move_x, move_y] = start_player
        if check_winner(temp_board) == start_player:
            return start_player
        possible_moves = find_possible_moves(temp_board)
        if len(possible_moves) == 0:
            return -start_player
        if len(possible_moves) >= num_check:
            # 此时我们对possible_moves进行排序，选择得分较高的位置，然后重置possible_moves
            scores = score_possible_moves(temp_board, -start_player, possible_moves)
            possible_moves = [move for _, move in sorted(zip(scores, possible_moves), reverse=True)]
            # 选择得分最高的几个位置
            possible_moves = possible_moves[:num_check]
        move_x, move_y = random.choice(possible_moves)
        temp_board[move_x, move_y] = -start_player  # 对手落子
        if check_winner(temp_board) == -start_player:
            return -start_player

下方设计一个给定的棋盘（board）上找到当前玩家（player）最合适的落子位置的函数：

1. 确定对手：

   • 首先，根据当前玩家（player）的值来确定对手（opponent）。如果当前玩家是1，那么对手就是-1；反之，如果当前玩家是-1，那么对手就是1。

2. 检查棋盘是否为空：

   • 使用np.all(board == 0)来检查棋盘是否完全为空。如果是，那么直接返回某个默认位置，这里假设是(7, 7)。这可能是个特殊情况，比如棋盘初始化时的一步。

3. 找出所有可能的落子位置：

   • 通过调用find_possible_moves(board)函数来找出当前棋盘上所有可能的落子位置，存储在possible_moves列表中。

4. 检查立即获胜或失败的位置：

   • 遍历possible_moves列表中的每个位置(move_x, move_y)。
   • 对于每个位置，先假设当前玩家落子，然后检查是否获胜。如果获胜，则立即返回该位置。
   • 如果没有获胜，则假设对手落子，再检查是否对手获胜。如果对手获胜，说明这个位置对当前玩家不利，但也返回该位置（否则不这样下，有可能对手直接获胜）。
   • 如果都没有获胜，则将该位置重置为空白。

5. 对多个可能位置进行评分和筛选：

   • 如果possible_moves列表中的位置数量大于3，那么对这些位置进行评分。
   • 使用score_possible_moves(board, player, possible_moves)函数为每个可能的位置评分。
   • 根据分数从高到低对位置进行排序，并选择得分最高的前3个位置作为接下来的候选落子位置。

6. 蒙特卡洛搜索：

   • 对于筛选后的possible_moves列表中的每个位置，进行蒙特卡洛搜索来评估其优劣。
   • 蒙特卡洛搜索是通过多次随机模拟对局来进行的。这里设置了num_simulations次模拟，默认是50次。
   • 在每次模拟中，使用random_policy(temp_board, player)函数来随机选择一个落子位置，并模拟对局结果。
   • 根据模拟结果更新每个位置的得分。如果当前玩家获胜，则对应位置的得分加1；如果对手获胜，则得分减1。

7. 返回最优位置：

   • 最后，根据得分最高的位置索引，从possible_moves列表中返回该位置作为当前玩家的最佳落子位置。

def find_correct_moves(board, player):
    '''找到合适的落子位置，board为棋盘，player为当前玩家，board为np二维数组，player为1或-1'''
    if player == 1:
        opponent = -1
    else:
        opponent = 1
    # 检查是否棋盘为空
    if np.all(board == 0):
        return (7, 7)

    possible_moves = find_possible_moves(board) # 找到所有可能的落子位置
    if len(possible_moves) == 0:
        return None

    temp_board = copy.deepcopy(board)
    for move_x, move_y in possible_moves:
        temp_board[move_x, move_y] = player
        if check_winner(temp_board) == player:
            return (move_x, move_y)
        temp_board[move_x, move_y] = opponent
        if check_winner(temp_board) == opponent:
            return (move_x, move_y)
        temp_board[move_x, move_y] = 0
    
    if len(possible_moves) > 3:
        # 当有多个落子位置时，我们选择得分最高的几个位置
        scores = score_possible_moves(board, player, possible_moves)
        possible_moves = [move for _, move in sorted(zip(scores, possible_moves), reverse=True)]
        # 选择得分最高的几个位置
        possible_moves = possible_moves[:3]
    # 进行蒙特卡洛搜索
    scores = np.zeros(len(possible_moves))
    num_simulations = 50
    for i in range(scores.shape[0]):
        temp_board = copy.deepcopy(board)
        for _ in range(num_simulations):
            # 随机模拟
            result = random_policy(temp_board, player)
            if result == player:
                scores[i] += 1
            elif result == opponent:
                scores[i] -= 1
    return possible_moves[np.argmax(scores)]

接下来我们用蒙特卡洛树搜索的策略来对战随机策略，让我们看看效果如何。

# 测试程序
import numpy as np
import gymnasium as gym  
import matplotlib.pyplot as plt
%matplotlib inline
from IPython import display
import time

def show_state(board, step=0, info=""):
    plt.figure(3)
    plt.clf()
    plt.imshow(board)
    plt.axis('off')
    display.clear_output(wait=True)
    display.display(plt.gcf())

# 创建一个五子棋环境
env = GomokuEnv(player=-1)

# 随机策略
def random_action_possible(observation):
    positions = find_possible_moves(observation)
    if len(positions) == 0:
        return None
    x, y = random.choice(positions)
    return x * env.board_size + y

observation = env.reset()
while True:
    action = random_action_possible(observation)
    observation, reward, done, _ = env.step(action)
    show_state(env.board)
    time.sleep(0.1)
    if done:
        print("Game over, 对手赢了")
    action_player_x, action_player_y = find_correct_moves(env.board, env.player)
    action_player = action_player_x * env.board.shape[1] + action_player_y
    observation, reward, done, _ = env.step(action_player)
    if done:
        print("Game over, 玩家赢了")
    show_state(env.board)
    time.sleep(0.1)
    if done:
        break

可以看到，蒙特卡洛树搜索的策略在对抗随机策略时，胜率基本为100%，能够有效地找到最佳落子位置。读者可以尝试调整蒙特卡洛树搜索的参数，如模拟次数和搜索深度，以进一步提高策略的胜率。