⌈ 传知代码 ⌋ 强化学习和MCTS实践

💛前情提要💛

本文是传知代码平台中的相关前沿知识与技术的分享~

接下来我们即将进入一个全新的空间，对技术有一个全新的视角~

本文所涉及所有资源均在传知代码平台可获取

以下的内容一定会让你对AI 赋能时代有一个颠覆性的认识哦！！！

以下内容干货满满，跟上步伐吧~

📌导航小助手📌

💡本章重点
🍞一. 概述
🍞二. 实现过程
🍞三.强化学习
🍞四.训练结果
🫓总结

💡本章重点

强化学习和MCTS实践

🍞一. 概述

大家一定惊叹于AlphaGo zero在围棋领域的巨大成功，这种成功来源于强化学习的发展，在这里将以五子棋为例，向大家介绍如何从零开始手搓一个带有计算能力的AI人工智能。

基本的算法与AlphaGo zero差不多，主要是自我博弈强化学习以及蒙特卡洛搜索树(MCTS)。

🍞二. 实现过程

前期准备——棋盘的绘制

在这里，我们采用python中的pygame作为我们的棋盘绘制工具，在此之前我们先需要棋盘、黑色棋子、白色棋子的素材。这部分素材放在了附件中，大家可以任意下载。

我们通过一个Board棋盘类，来囊括所有跟棋盘有关的操作和属性

class Board:def __init__(self, width = 15, height = 15, **kwargs):self.width = width  # 棋盘宽度self.height = height  # 棋盘高度self.winReg = 5  # 5个棋子一条线则获胜self.players = [1, 2]self.states = None  # 棋盘状态self.current_player = Noneself.available = Noneself.last_move = None

这些初始化的属性的作用都在代码中标注了出来。这个棋盘还需要一个初始化函数，用来清空棋盘上的一切

    def init_board(self, start_player=0):# 初始化棋盘self.current_player = self.players[start_player]  # 先手玩家self.available = list(range(self.width * self.height))  # 初始化可用的位置集合self.states = {}  # 初始化棋盘状态self.last_move = -1  # 初始化最后一次的移动位置

棋局的状态

如何保存棋局的状态呢？

我们参考的是AlphaGo Zero中的设置，即使用4个15x15的二值特征平面来描述当前的局面，前两个平面分别表示当前player的棋子位置和对手player的棋子位置，有棋子的位置是1，没棋子的位置是0；第三个平面表示对手player最近一步的落子位置，也就是整个平面只有一个位置是1，其余全部是0；第四个平面表示的是当前player是不是先手player，如果是先手player则整个平面全部为1，否则全部为0

    def update_board_state(self):board_layers = np.zeros((4, self.width, self.height))if self.states:actions, players = np.array(list(zip(*self.states.items())))current_player_moves = actions[players == self.current_player]opponent_moves = actions[players != self.current_player]board_layers[0][current_player_moves // self.width, current_player_moves % self.width] = 1board_layers[1][opponent_moves // self.width, opponent_moves % self.width] = 1board_layers[2][self.last_move // self.width, self.last_move % self.width] = 1if len(self.states) % 2 == 0:board_layers[3][:, :] = 1.0return board_layers[:, ::-1, :]

这里就涉及到我们如何设定棋子在棋盘中的位置了，它有一个二维坐标，但是为了方便我们有时候会把它设置为一个一维的坐标并随时进行转化

    def move_to_location(self, move):h = move // self.widthw = move % self.widthreturn [h, w]def location_to_move(self, location):h = location[0]w = location[1]move = h*self.width+wreturn move

接下来就是判断棋局的胜负与否，这部分是比较简单的，因为在本程序中并不去涉及五子棋的禁手，因此仅仅只需要去判断在落下一个棋子后是否有一个方向存在五连的情况即可，这部分代码为：

def check_winner(self):# 检查是否有赢家# 棋盘上所有已经下过的位置played_positions = set(range(self.width * self.height)) - set(self.available)if len(played_positions) < self.winReg + 2:return False, -1# 遍历每一个已下的位置for pos in played_positions:row = pos // self.widthcol = pos % self.width  # 获取棋子的坐标current_player = self.states[pos]  # 根据移动的位置确定玩家# 检查获胜条件# 水平方向获胜if col in range(self.width - self.winReg + 1) and \len(set(self.states.get(i, -1) for i in range(pos, pos + self.winReg))) == 1:return True, current_player# 垂直方向获胜if row in range(self.height - self.winReg + 1) and \len(set(self.states.get(i, -1) for i in range(pos, pos + self.winReg * self.width, self.width))) == 1:return True, current_player# 对角线方向获胜（左上到右下）if col in range(self.width - self.winReg + 1) and row in range(self.height - self.winReg + 1) and \len(set(self.states.get(i, -1) for i in range(pos, pos + self.winReg * (self.width + 1), self.width + 1))) == 1:return True, current_player# 对角线方向获胜（左下到右上）if col in range(self.winReg - 1, self.width) and row in range(self.height - self.winReg + 1) and \len(set(self.states.get(i, -1) for i in range(pos, pos + self.winReg * (self.width - 1), self.width - 1))) == 1:return True, current_playerreturn False, -1

绘制棋盘

使用pygame库对棋盘进行绘制，其主要核心工作量为将我们棋盘贴到背景上，事实监控我们的鼠标的点击动作，如果点在对应的位置，便尝试落子，将我们的棋子贴纸贴在对应的位置上，并对棋盘重新进行绘制。

使用Game_UI作为带有UI的棋盘类，其首先需要实现的方法是贴背景

pygame.init()
self.__ui_chessboard = pygame.image.load(IMAGE_PATH+"chessboard.jpg").convert()
self.__screen.blit(self.__ui_chessboard, (0, 0))

棋子同样也可以使用同样的方式贴上去。但是在此之前必须先监测我们鼠标动作

mouse_button = pygame.mouse.get_pressed()

鼠标的点击动作会返回一个具体的坐标值，我们在落子之前就必须要将这个坐标值进行转换。

    def trapping(self):i, j = None, None# 获取鼠标按键状态mouse_button = pygame.mouse.get_pressed()# 如果左键被按下if mouse_button[0]:x, y = pygame.mouse.get_pos()# 将像素坐标转换为棋盘坐标i, j = self.coordinate_transform_pixel2map(x, y)if i is not None and j is not None:loc = i * self.N + j# 获取当前位置的棋子状态piece_status = self.board.states.get(loc, -1)player1, player2 = self.board.players# 检查当前位置是否已有棋子if piece_status == player1 or piece_status == player2:# 如果有，则不允许落子return Falseelse:# 获取当前玩家current_player = self.board.current_playerlocation = [i, j]# 将坐标转换为移动move = self.board.location_to_move(location)# 执行落子self.board.do_move(move)# 如果需要显示if self.is_shown:# 根据当前玩家选择棋子颜色if current_player == player1:self.__screen.blit(self.__ui_piece_black, (x, y))else:self.__screen.blit(self.__ui_piece_white, (x, y))return Truereturn False

最终在不考虑继续落子的情况下我们可以得到一个初步的界面

在这里插入图片描述

🍞三.强化学习

强化学习是当下非常热门的一个技术，能够实现一个智能体完全从无到有的一个学习过程。在我们完成这个程序之后我们将会看到，我们并没有给该智能体任何的人工的数据，智能体自发的从自我博弈中学习到了游戏的规则，游戏的技巧。

现代强化学习的思路主要是值网络与策略网络，前者告诉我们在当前的棋盘下，每一步的价值是多少，而后者告诉我们基于这些已经计算的价值，如何去下才能保证我们未来的收益最高。

在这里插入图片描述
一般来说同一个的动作（操作）因为随机效应可能会演化为不同的环境效应，但是对于棋盘来说，每一步落子后的棋局都是固定。现在我们定义一个策略价值网络，这个网络能够输出策略和价值，是一个较为简单的卷积神经网络，需要注意的是卷积层对于策略和价值来说是公用的，因为卷积层提取的是棋盘的特征，这个特征不管对于策略还是价值来说理论上都是一样的。

class Net(nn.Module):def __init__(self, board_width, board_height):super(Net, self).__init__()self.board_width = board_widthself.board_height = board_heightself.conv1 = nn.Conv2d(in_channels=4, out_channels=32, kernel_size=3, stride=1, padding=1)self.conv2 = nn.Conv2d(in_channels=32, out_channels=64, kernel_size=3, stride=1, padding=1)self.conv3 = nn.Conv2d(in_channels=64, out_channels=128, kernel_size=3, stride=1, padding=1)self.act_conv1 = nn.Conv2d(in_channels=128, out_channels=4, kernel_size=1, stride=1, padding=0)self.act_fc1 = nn.Linear(4*self.board_width*self.board_height, self.board_width*self.board_height)self.val_conv1 = nn.Conv2d(in_channels=128, out_channels=2, kernel_size=1, padding=0)self.val_fc1 = nn.Linear(2*self.board_height*self.board_width, 64)self.val_fc2 = nn.Linear(64, 1)def forward(self, inputs):x = F.relu(self.conv1(inputs))x = F.relu(self.conv2(x))x = F.relu(self.conv3(x))x_act = F.relu(self.act_conv1(x))x_act = x_act.view(x_act.shape[0], -1)x_act = F.log_softmax(self.act_fc1(x_act), dim=1)x_val = F.relu(self.val_conv1(x))x_val = x_val.view(x_val.shape[0], -1)x_val = F.relu(self.val_fc1(x_val))x_val = torch.tanh(self.val_fc2(x_val))return x_act, x_val

训练

接下来就是如何去训练这两个网络，对于了解过强化学习过程的朋友来说这个过程十分简单。对于价值网络，我们采用蒙特卡洛方法进行训练，这种训练方法需要采集一整局的棋局数据和结果，公式的原因大家可以参考强化学习的资料

在这里插入图片描述

其中Gt表示当前操作后后续所有的收益的总和，由于棋局的收益为是否胜利，因此G代表该状态下后续赢得总数目，现在棋局的价值对应于该棋局后本方能够赢的棋局数目，赢得越多那么代表现在得棋局状态应该是更加有利得，也更加有价值，这其实很符合人的直觉。因此该网络得损失函数为

value_loss_func = nn.MSELoss(reduction="mean")
value_loss = value_loss_func(value, winner_batch)

对于策略网络而言较为复杂，这将涉及到本文的另一个核心的技术——蒙特卡洛树搜索。

蒙特卡洛树搜索

上面我们已经提到，对于值网络而言我们要将对应状态下的价值与此刻后胜利的局数相拟合，但是可惜的是，由于棋局的可能性实在是太丰富，所以我们无法做到遍历所有的棋局从而确定这个值，因此蒙特卡洛树搜索便是一种让我们快速聚焦收敛采用到重要的棋局。

蒙特卡罗树搜索（MCTS）由两部分组成：树结构和搜索算法。树是一种数据结构，由节点和边组成。树的顶端节点称为根节点；一个节点的上一级节点称为父节点，下一级节点称为子节点；没有子节点的节点称为叶节点。除了存储状态和动作信息外，搜索树中的节点还会记录访问次数和奖励估值。在AlphaZero算法中，节点还包含该状态对应的动作概率分布。

综上所述，AlphaZero算法的搜索树中，每个节点包含以下信息：

A：到达该节点所需执行的上一个动作（用于索引其父节点）。
N：节点被访问的次数。初始值为0，表示该节点未被访问过。
W：节点的奖励值之和，用于计算平均奖励。初始值为0。
Q：节点的平均奖励值，通过计算得到，代表该节点的值函数估计。初始值为0。
P：动作A的选取概率。这个值由神经网络根据其父节点的状态计算得到，并存储在该子节点中，便于索引和计算。

在这里插入图片描述

在继续介绍之前，我们先强调一个关键点。由于游戏中存在两个玩家，所以在建立搜索树时，一棵树里会存在两个玩家的视角。节点上的信息要么从黑方玩家的视角进行更新，要么从白方玩家的视角进行更新。例如，在上图中，假设某节点表示的棋盘状态只有一个黑方的棋子，这意味着该轮到白方玩家执行下一步。但需要注意的是，这个节点上的信息是从其父节点（即黑方玩家）的角度来存储的。由于该节点是在父节点扩展子节点的过程中产生的，因此该节点上的A、N、W、Q、P都是由黑方玩家初始化的，并用于黑方视角下的后续更新和使用。因此，只有当黑方玩家选择动作A=5时，才会到达该节点，并将当前信息初始化为N=0、W=0、Q=0、P=0。对每个节点的视角有一个清晰的理解是非常重要的，否则在后续树搜索过程中执行回溯（backup）步骤时，会难以理解整个更新过程。

class TreeNode:def __init__(self, parent, prior_p):self._parent = parentself._children = {}self._n_visits = 0self._Q = 0self._u = 0self._P = prior_p

通常，树搜索方法有四个步骤：选择（Select），扩展（Expand），模拟（Simulate），回溯（Backup），所有这些步骤都是在搜索树中执行的，真正的棋盘上没有落子。也就是智能体在脑子中思考接下来的步骤，所谓走一步，看两步，想三步。具体图示如下

在这里插入图片描述

将这些步骤合在一起便可以对网络进行训练了

    def train_step(self, state_batch, mcts_probs, winner_batch, lr=0.002):state_batch = torch.from_numpy(state_batch).to(self.device)mcts_probs = torch.from_numpy(mcts_probs).to(self.device)winner_batch = torch.from_numpy(winner_batch).to(self.device)for param_group in self.optimizer.param_groups:param_group['lr'] = lrself.optimizer.zero_grad()log_act_probs, value = self.policy_value_net(state_batch)value = value.reshape(-1,)value_loss_func = nn.MSELoss(reduction="mean")value_loss = value_loss_func(value, winner_batch)policy_loss = -torch.mean(torch.sum(mcts_probs*log_act_probs, axis=1))loss = value_loss + policy_lossloss.backward()self.optimizer.step()entropy = -torch.mean(torch.sum(torch.exp(log_act_probs)*log_act_probs, axis=1))return loss.detach().cpu().numpy(), entropy.detach().cpu().numpy()

实现人机交互只需要人与电脑一步一步下即可，游戏主题在人类下棋回合时监听鼠标点击并落子，AI回合针对人类落子形成得新状态通过蒙特卡洛树搜索得到下一步的结果

from gobang.game import Board, Game_UI
from gobang.mcts import MCTSPlayer
from gobang.model import PolicyValueNetclass Human:def __init__(self):self.player = None  def set_player_ind(self, person_id):self.player = person_id  def main():width, height = 15, 15model_file = 'dist/best_policy.model'try:board = Board(width=width, height=height, n_in_row=5)game = Game_UI(board, is_shown=1)best_policy = PolicyValueNet(width, height, model_file=model_file)mcts_player = MCTSPlayer(best_policy.policy_value_fn, c_puct=5, n_playout=400)human = Human()game.start_play_mouse(human, mcts_player, start_player=1)except KeyboardInterrupt:print('\n\rex-quit')if __name__ == "__main__":main()