基于MCTS的黑白棋ai

人工智能课程最近布置了这样的一份作业，完成后把注释还算详细的代码分享出来，供大家借鉴参考。如果你也是左职钟老师的学生，为保证完成地不过于相似，还请结合自己的理解进行修改。欢迎大家来捉虫

参考文章：python使用蒙特卡洛树(MCTS)算法实现黑白棋miniAlphaGo for Reversi_黑白棋(mini alphago) 1 实验介绍 1.1 实验背景 黑白棋 (reversi),也叫-CSDN博客

1.实验内容与要求

1.1 实验内容

黑白棋(Reversi)，也叫苹果棋，翻转棋，是一个经典的策略性游戏。一般棋子双面为黑白两色，故称“黑白棋”。因为行棋之时将对方棋子翻转，变为己方棋子，故又称“翻转棋”(Reversi)。棋子双面为红、绿色的称为“苹果棋”。它使用8x8的棋盘,由两人执黑子和白子轮流下棋，最后子多方为胜方。随着网络的普及，黑白棋作为一种最适合在网上玩的棋类游戏正在逐渐流行起来。中国主要的黑白棋游戏站点有Yahoo游戏、中国游戏网、联众游戏等。

游戏规则：

棋局开始时黑棋位于e4和d5，白棋位于d4和e5。

1. 黑方先行，双方交替下棋。

2. 一步合法的棋步包括：在一个空格新落下一个棋子，并且翻转对手一个或多个棋子。

3. 新落下的棋子与棋盘上已有的同色棋子间，对方被夹住的所有棋子都要翻转过来。可以是横着夹，竖着夹，或是斜着夹。夹住的位置上必须全部是对手的棋子，不能有空格。

4. 一步棋可以在数个（横向，纵向，对角线）方向上翻棋，任何被夹住的棋子都必须被翻转过来，棋手无权选择不去翻某个棋子。

5. 除非至少翻转了对手的一个棋子，否则就不能落子。如果一方没有合法棋步，也就是说不管他下到哪里，都不能至少翻转对手的一个棋子，那他这一轮只能弃权，而由他的对手继续落子直到他有合法棋步可下。

6. 如果一方至少有一步合法棋步可下，他就必须落子，不得弃权。

7. 棋局持续下去，直到棋盘填满或者双方都无合法棋步可下。

8. 如果某一方落子时间超过1分钟，则判该方失败。

1.2. 实验要求

1. a)使用MCTS算法实现Mini AlphaGo for Reversi, 有能力的同学可以采用最大最小算法进行对比.
2. b)MCTS算法部分需要自己实现，尽量不使用现成的包，工具或者接口.实验报告不能直接复制、粘贴网上内容，请理清思路，转化为自身知识.珍惜每一次训练机会
3. c)在博弈过程中，Mini AlphaGo每一步所花费的时间以及总时间需要显示出来.
4. d)需要有简单的图形界面用于人机博弈交互.
5. e) 可使用Python语言，也可以使用其他编程语言实现.

2.概念理解

在初次接触，并且尝试编写代码时，最大且最直接的问题往往是，MCTS算法是什么？和翻转棋有什么关系？在本文中，将尽力解释这两点。

2.1 核心思想

一位杰出的棋手往往能够根据对手的上一步选择，分析出对手后几步的动向。同样的，若要实现一个具备一定实力的ai，也需要预判对手随后的操作，而后做出最稳妥的选择

2.2 数据结构

落子具有先后顺序，并且一方落完之后，另一方有多种落子可能。因此本程序采用树状结构，每一个节点代表一种个落子可能，“节点间的父子关系”表征“落子的先后顺序“，”一个父节点可能具备多个子节点“表征”一方落子后另一方的多种落子可能“。

2.3 MCTS算法对树的操作

MCTS算法常被分为”选择“、”拓展“、”模拟“、”反向传播“四个部分，接下来将介绍各个部分对节点树的操作。

2.3.1 选择

当我有多个落子位置可选时，我会希望选择胜率最大的位置。而当对手有多个落子位置可选时，他同样会希望选择到他胜率最大，也就是我胜率最小的位置。但我要如何确定这个胜率？

1.遍历棋盘的所有情况，然后计算胜场？算力不够

2.在已有棋盘落子+此处落子的基础上，进行一定场次的随机模拟（2.3.3将会对随机模拟做出更详细的介绍），每次随机模拟中双方都在符合规则的前提下随机落子，然后计算胜率？有一定的参考价值，并且”模拟“阶段就是这么做的，但这显然没有考虑到对局中敌我的主观能动性，参考价值较为有限。

事实上，选择阶段就是在第二种胜率计算方法的基础上增加”主观能动性“的因素。使得胜率更具备参考意义。

由于无法遍历所有情况，所以通过随机落子来计算一个参考概率是很有必要的。但是，只要我在随机落子之前进行越多步的非随机落子——贴近敌我行动可能的非随机落子，那么在此之后通过随机落子计算出的胜率，就包含更多的对”敌我主观能动性“的考量。

我们通过一个例子来讲解

对于这一棵树，A是当前的棋盘。B层是黑方（我们假设此时是黑方回合，假设成白方其实也同理~）在此回合可以落子的位置，此处我们假设只有3处可以落子，命名为B1,B2,B3。编号之下的百分比数字是通过多场随机落子计算出的胜率。C层是在黑方落子后，白方的可落子位置（如黑方落子B1,之后白方符合规则的落点则为C1,C2），名称下的数字仍然是胜率（黑方的胜率），且同样为通过多场随机模拟落子计算出的结果。

可以注意到，到这里仍然全是随机值，接下来我们要往其中添加主观能动性。

首先，白方会希望黑方胜率尽可能小。

这意味着，根据当前的胜率信息，当黑方落子B1时，白方大概率落子C2；黑方B2时，白方C4；黑方B3时，白方C5。

那么，在C2的基础上进行的模拟对局就比C1上更加符合未来可能发生的情况，同理，C4比C3更符合，C5比C6更符合。

而在B1的基础上进行的模拟对局，可能会进入C1，因此通过B1模拟计算得到的胜率也会更多得受一些“未来小概率才会出现的情况”干扰，因此通过B1模拟得出的胜率的现实指导意义要弱于从C2模拟。同理，B2弱于C4 , B3弱于C5。

接下来是判断C2,C4,C6哪个在未来有更大概率发生。

这需要用到黑方的选择偏好：

黑方会希望黑方胜率尽可能大。

因此根据目前的信息，黑方更有可能走B1，即C2在未来有更大概率发生。

初学者看到这里可能会产生一个疑惑：既然都确定走B1了，还有什么模拟下去的必要吗？C层的信息也没用上啊？

答案就在着重标记的”目前“二字里。

由于概率是随机模拟得到的，无论是哪个节点，再多模拟几次可能值都会产生变动。并且目前的B1可能仍在很大程度上受C1影响（当然也可以让B1值直接等于C2，最大最小算法似乎就是直接将子节点的值赋给父节点），因此要进行更多次模拟，而且是更贴近未来可能的模拟，即基于C2的模拟。而后根据新模拟的场数与胜利数重新调整B1与C2的胜率。

在这样的调整后，B1的胜率未必还是B层中的最高者。但无论怎样，在每一次的调整中，总是选择B层中的最大值，以及其对应C子节点中的最小值作为基础，开始新的模拟。直到一定的调整次数之后，选择最终胜率最高的落点位置，作为结果。

以上为ucb公式中常数c为0的情况。uba公式的作用是给节点评分，评分的依据是节点的胜率以及其对父节点的影响比例。当c不为0时，整体的流程仍是相同的，不过是我们做出选择的依据从胜率变成了ucb公式给出的评分

由于”选择“阶段既处理还未被MCTS算法调整过的树，还处理已经被MCTS算法调整过的树。因此在上面的论述中，其实还包括了”模拟“以及”反向传播“两个过程，并且大致介绍了MCTS整个算法的思想

提取并总结一下，选择阶段的作用是：选择出一条未来更可能发生的路径（在例子中，目前该路径为B1C2,但在实际应用时并不一定只有两层，还可以不断向下拓展，甚至穷举完所有可能）。

而拓展、模拟、反向传播三个阶段则是通过这条路径，对第一级子节点的胜率进行调整，参入对敌我动向的分析，使该胜率更可信。

最终就能通过各个可落子位置的较可信的胜率，确定落子方案。这就是MCTS算法在翻转棋上的应用原理。

2.3.2 拓展

这里继续使用上面的例子。

目前而言，其实不只B层的胜率是随机、不完全可信的，C层的胜率同样也是通过随机落子对局计算出来的，也不完全正确。在选择阶段，我们确定了路径[B1-C2] , 现在我们希望C2的胜率也能参入对敌我动向的分析，怎么办呢？

给C2也加上子节点——这就是”拓展“的含义

我们假设C2之后黑方有3个可落子位置，由于3个位置都有可能落子，因此需要将3个位置全都作为子节点接到C2之后，我们将其编号为D1，D2，D3。

2.3.3 模拟

对敌我动向的分析需要使用各个节点的胜率作为依据，因此在得到D1，D2，D3后，首要任务是计算出一个参考胜率。计算方法是进行多局随机模拟。

随机模拟：

在一回合内可选的落子位置往往有多处，随机模拟即为：在目前的基础上（在D1开始的随机模拟的基础即为 棋盘上已经有了棋子+于B1落黑子+于C2落白子+于D1落黑子，回合转至白方）继续对局，之后交战的两方在其回合都是无策略地随机选一处落子，直到游戏结束。

然后将各自多局随机模拟中的胜率作为参考胜率赋值给D1，D2，D3

由于D层可能接着扩展E层，为了调整胜率方便，往往是记录对局数与胜利数，而不是仅记录胜率。

2.3.4 反向传播

D1的模拟既是在D1自己的基础上，同时也是在C2，B1的基础上进行的，因此不仅要将对局数与胜利数赋值给D1自生，还需要修改C2，B1的对局数与胜利数，实现对C2，B1胜率的调整。D2，D3同理。

2.3.5 循环

C1拓展出了D层，D又可以拓展出E层，同理后面还有F，G层。在ai确定落子位置之前，往往不会只执行一次”选择“→”拓展”→”模拟”→”反向传播”，而是会在”反向传播“后再次对修改后的树执行选择操作，不断循环。而循环的具体次数，可根据性能与智能要求做出自己的调整。次数越多ai越强，次数越少ai越快。

3.具体实现

3.1 棋盘逻辑

3.1.1 UI界面

棋盘主要为一个tkinter Canvas，通过监听鼠标左键的点击事件，根据鼠标对于窗口的相对点击位置确认鼠标点击的单元格，接着再判断点击单元格是否可以落子，若可以落子则更新棋盘、画面、计算ai落子位置；若不可落子则直接结束该点击事件，等待下一次点击。

class ReversiBoard(Tk.Canvas):
    # 创建了Reversi类继承Tk.Canvas，负责棋盘部分
    # 定义棋盘单元格的大小、边距
    cell_size = 54 #单元格大小
    margin = 20 #边框
    board = rvs.getInitialBoard() #棋盘的情况
    validBoard = True #棋盘是否能够继续
    isPayerTurn = True #是否玩家先手
    step = []   #记录操作的数组

    # 构造函数
    def __init__(self, master):
        cwidth = rvs.BOARD_SIZE * self.cell_size + 2*self.margin #计算单元格宽度
        #设置Canvas属性
        Tk.Canvas.__init__(self, master, bd=1, bg='#e4c8a9', width=cwidth, height=cwidth,cursor="hand2")
        self.bind("<1>", self.put_stones) #绑定实际按put_stones到鼠标左键
        # 绘制棋盘
        for i in range(rvs.BOARD_SIZE):
            for j in range(rvs.BOARD_SIZE):
                if((i+j)%2==0):
                    bcolor = "#c1914f" #给相间的单元格添加不同的颜色
                else:
                    bcolor = "#cba470"
                x0 = i * self.cell_size + self.margin
                y0 = j * self.cell_size + self.margin
                self.create_rectangle(x0, y0, x0 + self.cell_size, y0 + self.cell_size, fill=bcolor, width=1)

        self.refresh(rvs.PLAYER_NUM) #显示落子
        if(not self.isPayerTurn): #判断ai先后手
            rvs.PLAYER_NUM = 1
            rvs.COMPUTER_NUM = -1
            self.AI_move()

3.1.2 数据结构

整个棋盘由一个8*8的数字二维数组board表征，其中board[i][j]表征棋盘第i+1行，j+1列对应的单元格，其可能值有0——表示空，-1——黑子，1——白子。

def getInitialBoard(): # 初始化棋盘数组
    board = {}

    for i in range(0, BOARD_SIZE):
        board[i] = {}

        for j in range(0, BOARD_SIZE):
            board[i][j] = 0

    board[BOARD_SIZE / 2 - 1][BOARD_SIZE / 2 - 1] = WHITE_NUM
    board[BOARD_SIZE / 2][BOARD_SIZE / 2] = WHITE_NUM

    board[BOARD_SIZE / 2 - 1][BOARD_SIZE / 2] = BLACK_NUM
    board[BOARD_SIZE / 2][BOARD_SIZE / 2 - 1] = BLACK_NUM

    return board

3.1.3 检测可落子位置

遍历棋盘每一个位置，检测其是否值为0，且相邻对方棋子，且沿着相邻对方棋子方向前进最终会遇到一个自己的棋子

def possible_positions(board, tile): # 返回一个颜色棋子可落子位置
    positions = []
    for i in range(0, BOARD_SIZE):
        for j in range(0, BOARD_SIZE):
            if board[i][j] != 0:
                continue
            if isok(board, tile, i, j):
                positions.append((i, j))
    return positions

def isOnBoard(x, y): #检测对应位置是否在棋盘
    return x >= 0 and x <= 7 and y >= 0 and y <= 7

def isok(board,tile,i,j): #检测该位置是否可以落子
    change = -tile
    if(board[i][j]!=0):
        return False
    for xdirection, ydirection in direction:
        x, y = i, j
        x += xdirection
        y += ydirection
        if isOnBoard(x, y) and board[x][y] == change: #该点朝一dirction方向相邻一个棋子，且相邻的棋子为可以被翻转的数字
            # 一直走到出界或不是对方棋子的位置
            while board[x][y] == change:
                x += xdirection
                y += ydirection
                if not isOnBoard(x, y):
                    break
            # 出界了，则直接进行下一个方向的查找
            if not isOnBoard(x, y):
                continue
            # 是自己的棋子，中间的所有棋子都要翻转
            if board[x][y] == tile:
                return True
    return False

3.1.4 翻转

从落点位置向八个方向拓展，检测其是否相邻对方棋子，且沿着相邻对方棋子方向前进最终会遇到一个自己的棋子, 如果是，则将经过的对方棋子翻转。

def updateBoard(board, tile, i, j):
    direction = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]
    change = -tile
    need_turn = [] # 要被翻转的棋子
    for xdirection, ydirection in direction:
        x, y = i, j
        x += xdirection
        y += ydirection
        if isOnBoard(x, y) and board[x][y] == change: #该点朝一dirction方向相邻一个棋子，且相邻的棋子为可以被翻转的数字
            # 一直走到出界或不是对方棋子的位置
            while board[x][y] == change:
                x += xdirection
                y += ydirection
                if not isOnBoard(x, y):
                    break
            # 出界了，则直接进行下一个方向的查找
            if not isOnBoard(x, y):
                continue
            # 是自己的棋子，中间的所有棋子都要翻转
            if board[x][y] == tile:
                while True:
                    x -= xdirection
                    y -= ydirection
                    # 回到了起点则结束
                    if x == i and y == j:
                        break
                    # 需要翻转的棋子
                    need_turn.append([x, y])
    # 翻转棋子
    board[i][j] = tile
    for x, y in need_turn:
        board[x][y] = tile
    return len(need_turn)

3.1.5 判断胜负

当双方可落点位置数都为0时，遍历棋盘，计算双方棋子的数量，数量多者胜利。

def eval_board(tep_board): #比较二者的棋子数目，判断胜负
    tileNum,negTilenum = countTile(tep_board,playerNum)
    if tileNum > negTilenum:
        #tile代表的棋胜
        return True
        #tile代表的棋负
    return False

3.2 MCTS相关

3.2.1 首次扩展&模拟

本阶段用于初始化mcts树，扩展出第一层子节点，并进行一定场数的模拟，根据模拟结果修改结点的模拟总次数与模拟胜利次数。以此使之后的第一次mcts循环中的选择阶段具有选择的依据，并且可以避免除以0的异常情况。

global PATHROOT #节点树
if len(PATHROOT) == 0:
    PATHROOT = expand(board,playerNum)
    for index, rootChild in enumerate(PATHROOT):
        current_board =  copy.deepcopy(board) #current_board记录在某处落子后的棋盘
        parent, t_playout, reward, t_childrens = rootChild
        updateBoard(current_board, playerNum, parent[0] , parent[1]) #对落子于此处的棋盘进行随机落子，使得能对其使用ucb算法（避免除以0的情况）
        t_playout =10
        reward = 0
        for i in range(1,21):
            current_board2 = copy.deepcopy(current_board) #current_board2是用来进行随机落点判断胜负的临时表盘
            isWon = find_playout(current_board2, -playerNum) #tile表示下一步谁执行
            if(isWon):
                reward+=1
        PATHROOT[index] = (parent,t_playout,reward,t_childrens)

3.2.2 MCTS循环

选择

选择阶段首先根据uba算法计算第一层级各个结点的估值，而后选择估值最高者，遍历其一级子结点以计算各结点的uba估值，选择估值最小的结点。像这样不断深入，交替选择最大或最小值，直到达到叶子结点。记录下这一路每次选择的结果

def find_path(root):
    current_path = []
    child = root
    parent_playout = 0
    for item in child: #计算父节点遍历过的次数
        name, nplayout, reward, childrens = item
        parent_playout+=nplayout
    isMCTSTurn = True

    while True:
        if len(child) == 0: #无可落子的位置,直接结束
            break
        maxidxlist = [0]
        cidx = 0
        if isMCTSTurn:
            maxval = -1
        else:
            maxval = 2

        for n_tuple in child:  #对每一个可落子的位置进行最大最小搜索
            #实现最大最小搜索，电脑选择最大值，玩家选择最小值
            if isMCTSTurn:
                #ucb返回各个结点的值，之后就依靠这个值来进行最大最小算法
                cval = ucb(n_tuple, parent_playout)

                if cval >= maxval:
                    # 获取子结点中值最大的一项,并记录其id(即cidx)
                    if cval == maxval:
                        maxidxlist.append(cidx)
                    else:
                        maxidxlist = [cidx]
                        maxval = cval
            else:
                cval = ucb(n_tuple, parent_playout)

                if cval <= maxval:
                    #获取子节点中值最小的一项
                    if cval == maxval:
                        maxidxlist.append(cidx)
                    else:
                        maxidxlist = [cidx]
                        maxval = cval

            cidx += 1

        # 从最值结点中随机选择一处落子
        maxidx = maxidxlist[random.randrange(0, len(maxidxlist))]
        parent, t_playout, reward, t_childrens = child[maxidx]
        current_path.append(parent)
        parent_playout = t_playout
        # 选择子节点进入下一次循环
        child = t_childrens
        isMCTSTurn = not (isMCTSTurn)

    # 返回根据最大最小规则选择出来的一条路径
    return current_path

扩展

拷贝带落点棋盘到一临时棋盘，根据”选择”阶段获得的结点集，在临时棋盘上完成多次落点，完成落点后，检测临时棋盘的下一回合可落点位置，将这些可落点位置更新到结点树中

#扩展结点,返回tep_board的子节点数组
def expand(tep_board, tile):
    positions = possible_positions(tep_board, tile)
    result = []
    for temp in positions:
        result.append((temp, 0, 0, []))
    return result

单词模拟

对”扩展“阶段得到的每一可落点位置，在临时棋盘的基础上，于该位置落子。随后双方继续在此基础上不断地随机落子（符合规则的随机），直到游戏结束。如此进行多局后，将对局数与胜利数更新到该可落点位置在树中对应的节点。

def find_playout(tep_board, tile, depth=0): #对tep_board进行了系列随机落点后，返回最终结果胜负
    def eval_board(tep_board): #比较二者的棋子数目，判断胜负
        tileNum,negTilenum = countTile(tep_board,playerNum)
        if tileNum > negTilenum:
            #tile代表的棋胜
            return True
            #tile代表的棋负
        return False

    while(depth<120):#进行最多120次循环后返回结果
        turn_positions = possible_positions(tep_board, tile)
        if len(turn_positions) == 0: #如果没位置下棋，切换到对手回合
            tile = -tile
            neg_turn_positions = possible_positions(tep_board, tile)

            if len(neg_turn_positions) == 0: #对方也没位置下棋，结束游戏
                return eval_board(tep_board)
            else:
                turn_positions = neg_turn_positions

        temp = turn_positions[random.randrange(0, len(turn_positions))] # 随机放置一个棋子
        updateBoard(tep_board, tile, temp[0], temp[1])
        # 转换轮次
        tile = -tile
        depth+=1

    return eval_board(tep_board)

拓展&模拟&反向传播

根据”模拟”阶段的对局数与胜利数，更新可落点位置在树中对应的节点的所有祖先节点。

#扩展与模拟过程
child = PATHROOT
randomTime = 0 #进行随机落子的盘数
rewardSum = 0 #胜利总次数
for temp in current_path:
    #遍历最佳路径
    idx = 0
    for n_tuple in child:
        #找到最佳路径中此节点对应的子节点
        parent, t_playout, reward, t_childrens = n_tuple
        if temp[0] == parent[0] and temp[1] == parent[1]:
            break
        idx += 1

    if temp[0] == parent[0] and temp[1] == parent[1]:
        if len(t_childrens) == 0:
            #找到路径的叶子结点，进行拓展
            tempStartTime = time.time()
            t_childrens = expand(current_board, tile) #扩展过程
            tempEndTime = time.time()
            expendTime += tempEndTime-tempStartTime
            randomTime = len(t_childrens) *10 #进行随机落子的盘数
            rewardSum = 0 #胜利总次数
            tempStartTime = time.time() #模拟过程
            for index, rootChild in enumerate(t_childrens):#对落子于此处的棋盘进行随机落子，使得能对其使用ucb算法（避免除以0的情况）
                child_board =  copy.deepcopy(current_board) #current_board记录在某处落子后的棋盘
                child_parent, child_playout, reward, child_childrens = rootChild
                tempTile = tile
                tempNegTile = -tempTile
                updateBoard(child_board, tempTile, child_parent[0] , child_parent[1])
                child_playout =10
                reward = 0
                for i in range(1,21):
                    current_board2 = copy.deepcopy(child_board) #current_board2是用来进行随机落点判断胜负的临时表盘
                    simulationTimes+=1
                    isWon = find_playout(current_board2, tempNegTile) #tile表示下一步谁执行
                    if(isWon):
                        reward+=1
                rewardSum+=reward
                t_childrens[index] = (child_parent,child_playout,reward,child_childrens)
            tempEndTime = time.time()
            simulationTime += tempEndTime-tempStartTime
        #应用修改到本体
        child[idx] = (parent, t_playout, reward, t_childrens)
    #继续处理子结点
    child = t_childrens

if randomTime!=0:
    tempStartTime = time.time() #反向传播过程
    child = PATHROOT
    for temp in current_path:
        #遍历最佳路径
        idx = 0
        for n_tuple in child:
            #找到最佳路径中此节点对应的子节点
            parent, t_playout, reward, t_childrens = n_tuple
            if temp[0] == parent[0] and temp[1] == parent[1]:
                break
            idx += 1

        if temp[0] == parent[0] and temp[1] == parent[1]:
            #找到了对应的结点，修改场数与胜利数
            t_playout += randomTime
            reward += rewardSum

            #应用修改到本体
            child[idx] = (parent, t_playout, reward, t_childrens)
        #继续处理子结点
        child = t_childrens
    tempEndTime = time.time()
    BackTime += tempEndTime-tempStartTime

返回结果

遍历树的第一层节点，选择胜率最高的节点对应的落点位置返回。

for n_tuple in PATHROOT:
    parent, t_playout, reward, t_childrens = n_tuple

    if (t_playout > 0) and (reward / t_playout > max_avg_reward):
        mt_result = parent
        max_avg_reward = reward / t_playout
return mt_result

4.运行结果

5.完整原码

5.1 game.py

import MCTS as rvs
import tkinter as Tk
import time
import tkinter.messagebox
total=[]
class ReversiBoard(Tk.Canvas):
    # 创建了Reversi类继承Tk.Canvas，负责棋盘部分
    # 定义棋盘单元格的大小、边距
    cell_size = 54 #单元格大小
    margin = 20 #边框
    board = rvs.getInitialBoard() #棋盘的情况
    validBoard = True #棋盘是否能够继续
    isPayerTurn = True #是否玩家先手
    step = []   #记录操作的数组

    # 构造函数
    def __init__(self, master):
        cwidth = rvs.BOARD_SIZE * self.cell_size + 2*self.margin #计算单元格宽度
        #设置Canvas属性
        Tk.Canvas.__init__(self, master, bd=1, bg='#e4c8a9', width=cwidth, height=cwidth,cursor="hand2")
        self.bind("<1>", self.put_stones) #绑定实际按put_stones到鼠标左键
        # 绘制棋盘
        for i in range(rvs.BOARD_SIZE):
            for j in range(rvs.BOARD_SIZE):
                if((i+j)%2==0):
                    bcolor = "#c1914f" #给相间的单元格添加不同的颜色
                else:
                    bcolor = "#cba470"
                x0 = i * self.cell_size + self.margin
                y0 = j * self.cell_size + self.margin
                self.create_rectangle(x0, y0, x0 + self.cell_size, y0 + self.cell_size, fill=bcolor, width=1)

        self.refresh(rvs.PLAYER_NUM) #显示落子
        if(not self.isPayerTurn): #判断ai先后手
            rvs.PLAYER_NUM = 1
            rvs.COMPUTER_NUM = -1
            self.AI_move()

    def put_stones(self, event):  #  在界面上放置棋子
        # 是否游戏结束
        if self.validBoard == False:
            #游戏结束
            self.validBoard = True
            #重新生成棋盘
            self.board = rvs.getInitialBoard()
            self.isPayerTurn = True

            #清除操作记录
            for numid in self.step:
                self.delete(numid)
            self.step = []
            self.refresh(rvs.PLAYER_NUM)
            return

        # 电脑轮次
        if not (self.isPayerTurn):
            return
        # 玩家轮次
        x = self.canvasx(event.x)
        y = self.canvasy(event.y)
        # 根据点击位置确定格子
        i = int((x-self.margin) / self.cell_size)
        j = int((y-self.margin) / self.cell_size)
        if self.board[i][j] != 0 or not rvs.isok(self.board, rvs.PLAYER_NUM, i, j): #点击位置不符合规则，直接返回
            return

        rvs.updateBoard(self.board, rvs.PLAYER_NUM, i, j)
        rvs.updatePathRoot(i,j) #记录落点位置
        self.refresh(rvs.COMPUTER_NUM) #更新棋盘界面
        isPayerTurn = False
        self.after(100, self.AI_move)

    def AI_move(self):
        while True:
            #获取此时人类以及机器可以落子的结点
            mcts_possibility = len(rvs.possible_positions(self.board, rvs.COMPUTER_NUM))
            #判断机器是否有棋可下
            if mcts_possibility == 0:
                break
            start= time.time()
            # 根据mcts算法获取落子位置
            stone_pos = rvs.mctsNextPosition(self.board,0.7,rvs.COMPUTER_NUM)
            end =time.time()
            one_time=end-start
            print("落子位置", stone_pos)
            print("总落子时间为",format(one_time, '.4f'),"s")
            total.append(one_time)
            rvs.updateBoard(self.board, rvs.COMPUTER_NUM, stone_pos[0], stone_pos[1])
            rvs.updatePathRoot(stone_pos[0],stone_pos[1]) #更新pathRoot
            self.refresh(rvs.PLAYER_NUM)

            player_possibility = len(rvs.possible_positions(self.board, rvs.PLAYER_NUM))
            mcts_possibility = len(rvs.possible_positions(self.board, rvs.COMPUTER_NUM))

            #判断人类是否有棋可下
            if  player_possibility > 0 or mcts_possibility == 0:
                break

        player_possibility = len(rvs.possible_positions(self.board, rvs.PLAYER_NUM))
        if player_possibility == 0 and mcts_possibility == 0:
            self.showResult()
            self.validBoard = False

        self.isPayerTurn = True

    def showResult(self):
        player_stone,mcts_stone = rvs.countTile(self.board,rvs.PLAYER_NUM)

        if player_stone > mcts_stone:
            tkinter.messagebox.showinfo('游戏结束', "你获胜了")

        elif player_stone == mcts_stone:
            tkinter.messagebox.showinfo('游戏结束', "平局")

        else:
            tkinter.messagebox.showinfo('游戏结束', "你失败了")
        print("ai整局用时",sum(total))

    def refresh(self,tile): #刷新整个棋盘
        self.delete("probale")
        for i in range(rvs.BOARD_SIZE):
            for j in range(rvs.BOARD_SIZE):
                x0 = i * self.cell_size + self.margin
                y0 = j * self.cell_size + self.margin

                if self.board[i][j] == 0:
                    continue
                if self.board[i][j] == rvs.BLACK_NUM:
                    bcolor = "#000000"
                if self.board[i][j] == rvs.WHITE_NUM:
                    bcolor = "#ffffff"
                self.create_oval(x0 + 8, y0 + 8, x0 + self.cell_size - 8, y0 + self.cell_size - 8, fill=bcolor, width=0)
        if tile == rvs.PLAYER_NUM:
            probale = rvs.possible_positions(self.board,tile) #显示可落子位置
            bcolor = "#ffcc33"
            for pos in probale:
                x0 = pos[0] * self.cell_size + self.margin
                y0 = pos[1] * self.cell_size + self.margin
                self.create_oval(x0 + 18, y0 + 18, x0 + self.cell_size-18, y0 + self.cell_size - 18, fill=bcolor, width=0,tags="probale")

class Reversi(Tk.Frame):
    # 创建了Reversi类继承Tk.Frame，负责整个窗口
    def __init__(self, master=None):
        Tk.Frame.__init__(self, master,bg="#51150b")
        self.master.title("黑白棋")
        # ReversiBoard为自定义的棋盘类，放置在窗口中
        self.f_board = ReversiBoard(self)
        self.f_board.pack(padx=20, pady=20)

if __name__ == '__main__':
    app = Reversi()
    app.pack()
    app.mainloop()

5.2 MCTS.py

import random
import math
import time
import copy

BOARD_SIZE = 8 #棋盘行数与列数
PLAYER_NUM = -1 #在board中代表玩家的数字
COMPUTER_NUM = 1 #在board中代表带电脑的数字
MAX_THINK_TIME = 5  #电脑的最大思考时间
direction = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]
BLACK_NUM = -1 #代表黑棋的数字
WHITE_NUM = 1 #代表白棋的数字
PATHROOT = [] #节点树

def getInitialBoard(): # 初始化棋盘数组
    board = {}

    for i in range(0, BOARD_SIZE):
        board[i] = {}

        for j in range(0, BOARD_SIZE):
            board[i][j] = 0

    board[BOARD_SIZE / 2 - 1][BOARD_SIZE / 2 - 1] = WHITE_NUM
    board[BOARD_SIZE / 2][BOARD_SIZE / 2] = WHITE_NUM

    board[BOARD_SIZE / 2 - 1][BOARD_SIZE / 2] = BLACK_NUM
    board[BOARD_SIZE / 2][BOARD_SIZE / 2 - 1] = BLACK_NUM

    return board

# 返回棋子数
def countTile(board,tile):
    stones = 0
    negstones = 0
    for i in range(0, BOARD_SIZE):
        for j in range(0, BOARD_SIZE):
            if board[i][j] == tile:
                stones+=1
            elif board[i][j] == -tile:
                negstones+=1

    return stones,negstones

def possible_positions(board, tile): # 返回一个颜色棋子可落子位置
    positions = []
    for i in range(0, BOARD_SIZE):
        for j in range(0, BOARD_SIZE):
            if board[i][j] != 0:
                continue
            if isok(board, tile, i, j):
                positions.append((i, j))
    return positions

def isOnBoard(x, y): #检测对应位置是否在棋盘
    return x >= 0 and x <= 7 and y >= 0 and y <= 7

def isok(board,tile,i,j): #检测该位置是否可以落子
    change = -tile
    if(board[i][j]!=0):
        return False
    for xdirection, ydirection in direction:
        x, y = i, j
        x += xdirection
        y += ydirection
        if isOnBoard(x, y) and board[x][y] == change: #该点朝一dirction方向相邻一个棋子，且相邻的棋子为可以被翻转的数字
            # 一直走到出界或不是对方棋子的位置
            while board[x][y] == change:
                x += xdirection
                y += ydirection
                if not isOnBoard(x, y):
                    break
            # 出界了，则直接进行下一个方向的查找
            if not isOnBoard(x, y):
                continue
            # 是自己的棋子，中间的所有棋子都要翻转
            if board[x][y] == tile:
                return True
    return False

# 是否是合法走法，如果合法返回需要翻转的棋子列表
def updateBoard(board, tile, i, j):
    change = -tile
    need_turn = [] # 要被翻转的棋子
    for xdirection, ydirection in direction:
        x, y = i, j
        x += xdirection
        y += ydirection
        if isOnBoard(x, y) and board[x][y] == change: #该点朝一dirction方向相邻一个棋子，且相邻的棋子为可以被翻转的数字
            # 一直走到出界或不是对方棋子的位置
            while board[x][y] == change:
                x += xdirection
                y += ydirection
                if not isOnBoard(x, y):
                    break
            # 出界了，则直接进行下一个方向的查找
            if not isOnBoard(x, y):
                continue
            # 是自己的棋子，中间的所有棋子都要翻转
            if board[x][y] == tile:
                while True:
                    x -= xdirection
                    y -= ydirection
                    # 回到了起点则结束
                    if x == i and y == j:
                        break
                    # 需要翻转的棋子
                    need_turn.append([x, y])
    # 翻转棋子
    board[i][j] = tile
    for x, y in need_turn:
        board[x][y] = tile
    return len(need_turn)

def updatePathRoot(i,j):
    global PATHROOT
    for n_tuple in PATHROOT:
        #找到最佳路径中此节点对应的子节点
        parent, t_playout, reward, t_childrens = n_tuple
        if i == parent[0] and j == parent[1]:
            PATHROOT = t_childrens
            break

# 蒙特卡洛树搜索
def mctsNextPosition(board,ucb_c,playerNum): #棋盘、ucb公式中常数c的值
    def ucb(node_tuple, t): #t为进行循环的次数
        #  返回各个结点用于进行ucb算法的值
        name, nplayout, reward, childrens = node_tuple #四个值分别对应 落点位置、模拟对局次数 、赢的次数、子节点

        if nplayout == 0: #避免意外情况
            nplayout = 1

        if t == 0:#避免意外情况
            t = 1
        #reward 是赢的次数 nplayout是模拟对局次数,cval是常数
        return (reward / nplayout) + ucb_c * math.sqrt(math.log(t) / nplayout)

    def find_playout(tep_board, tile, depth=0): #对tep_board进行了系列随机落点后，返回最终结果胜负
        def eval_board(tep_board): #比较二者的棋子数目，判断胜负
            tileNum,negTilenum = countTile(tep_board,playerNum)
            if tileNum > negTilenum:
                #tile代表的棋胜
                return True
                #tile代表的棋负
            return False

        while(depth<120):#进行最多120次递归后返回结果
            turn_positions = possible_positions(tep_board, tile)
            if len(turn_positions) == 0: #如果没位置下棋，切换到对手回合
                tile = -tile
                neg_turn_positions = possible_positions(tep_board, tile)

                if len(neg_turn_positions) == 0: #对方也没位置下棋，结束游戏
                    return eval_board(tep_board)
                else:
                    turn_positions = neg_turn_positions

            temp = turn_positions[random.randrange(0, len(turn_positions))] # 随机放置一个棋子
            updateBoard(tep_board, tile, temp[0], temp[1])
            # 转换轮次
            tile = -tile
            depth+=1

        return eval_board(tep_board)

    #扩展结点,返回tep_board的子节点数组
    def expand(tep_board, tile):
        positions = possible_positions(tep_board, tile)
        result = []
        for temp in positions:
            result.append((temp, 0, 0, []))
        return result

    def find_path(root):
        current_path = []
        child = root
        parent_playout = 0
        for item in child: #计算父节点遍历过的次数
            name, nplayout, reward, childrens = item
            parent_playout+=nplayout
        isMCTSTurn = True

        while True:
            if len(child) == 0: #无可落子的位置,直接结束
                break
            maxidxlist = [0]
            cidx = 0
            if isMCTSTurn:
                maxval = -1
            else:
                maxval = 2

            for n_tuple in child:  #对每一个可落子的位置进行最大最小搜索
                #实现最大最小搜索，电脑选择最大值，玩家选择最小值
                if isMCTSTurn:
                    #ucb返回各个结点的值，之后就依靠这个值来进行最大最小算法
                    cval = ucb(n_tuple, parent_playout)

                    if cval >= maxval:
                        # 获取子结点中值最大的一项,并记录其id(即cidx)
                        if cval == maxval:
                            maxidxlist.append(cidx)
                        else:
                            maxidxlist = [cidx]
                            maxval = cval
                else:
                    cval = ucb(n_tuple, parent_playout)

                    if cval <= maxval:
                        #获取子节点中值最小的一项
                        if cval == maxval:
                            maxidxlist.append(cidx)
                        else:
                            maxidxlist = [cidx]
                            maxval = cval

                cidx += 1

            # 从最值结点中随机选择一处落子
            maxidx = maxidxlist[random.randrange(0, len(maxidxlist))]
            parent, t_playout, reward, t_childrens = child[maxidx]
            current_path.append(parent)
            parent_playout = t_playout
            # 选择子节点进入下一次循环
            child = t_childrens
            isMCTSTurn = not (isMCTSTurn)

        # 返回根据最大最小规则选择出来的一条路径
        return current_path

    global PATHROOT #节点树
    if len(PATHROOT) == 0:
        PATHROOT = expand(board,playerNum)
        for index, rootChild in enumerate(PATHROOT):
            current_board =  copy.deepcopy(board) #current_board记录在某处落子后的棋盘
            parent, t_playout, reward, t_childrens = rootChild
            updateBoard(current_board, playerNum, parent[0] , parent[1]) #对落子于此处的棋盘进行随机落子，使得能对其使用ucb算法（避免除以0的情况）
            t_playout =10
            reward = 0
            for i in range(1,21):
                current_board2 = copy.deepcopy(current_board) #current_board2是用来进行随机落点判断胜负的临时表盘
                isWon = find_playout(current_board2, -playerNum) #tile表示下一步谁执行
                if(isWon):
                    reward+=1
            PATHROOT[index] = (parent,t_playout,reward,t_childrens)
    #记时，防止循环时间过长
    start_time = time.time()
    slectTime = 0 #选择过程耗费的时间
    expendTime = 0#扩展过程耗费的时间
    simulationTime = 0 #模拟过程耗费的时间
    BackTime = 0 #回溯过程耗费的时间

    simulationTimes = 0
    looptime = 0

    for loop in range(0, 30): #总的遍历
        looptime += 1
        current_board =  copy.deepcopy(board) #current_board记录在某处落子后的棋盘
        # 思考最大时间限制
        if (time.time() - start_time) >= MAX_THINK_TIME:
            break

        # current_path是一个放置棋子的位置列表，根据此列表进行后续操作
        tempStartTime = time.time() #选择过程
        current_path = find_path(PATHROOT) # find_path返回:ucb算法基于root蕴含的信息,获取的最佳路径(从头结点开始的，最佳子节点在各级child数组中的index数组)，
        tempEndTime = time.time()
        slectTime += tempEndTime-tempStartTime

        tile = playerNum
        for temp in current_path:
            #将通过ucb算法得到的路径整合到一个初始棋盘中
            updateBoard(current_board, tile, temp[0], temp[1]) #最终current_board为根据路径落子得到的棋盘
            tile = -tile

        #扩展与模拟过程
        child = PATHROOT
        randomTime = 0 #进行随机落子的盘数
        rewardSum = 0 #胜利总次数
        for temp in current_path:
            #遍历最佳路径
            idx = 0
            for n_tuple in child:
                #找到最佳路径中此节点对应的子节点
                parent, t_playout, reward, t_childrens = n_tuple
                if temp[0] == parent[0] and temp[1] == parent[1]:
                    break
                idx += 1

            if temp[0] == parent[0] and temp[1] == parent[1]:
                if len(t_childrens) == 0:
                    #找到路径的叶子结点，进行拓展
                    tempStartTime = time.time()
                    t_childrens = expand(current_board, tile) #扩展过程
                    tempEndTime = time.time()
                    expendTime += tempEndTime-tempStartTime
                    randomTime = len(t_childrens) *10 #进行随机落子的盘数
                    rewardSum = 0 #胜利总次数
                    tempStartTime = time.time() #模拟过程
                    for index, rootChild in enumerate(t_childrens):#对落子于此处的棋盘进行随机落子，使得能对其使用ucb算法（避免除以0的情况）
                        child_board =  copy.deepcopy(current_board) #current_board记录在某处落子后的棋盘
                        child_parent, child_playout, reward, child_childrens = rootChild
                        tempTile = tile
                        tempNegTile = -tempTile
                        updateBoard(child_board, tempTile, child_parent[0] , child_parent[1])
                        child_playout =10
                        reward = 0
                        for i in range(1,21):
                            current_board2 = copy.deepcopy(child_board) #current_board2是用来进行随机落点判断胜负的临时表盘
                            simulationTimes+=1
                            isWon = find_playout(current_board2, tempNegTile) #tile表示下一步谁执行
                            if(isWon):
                                reward+=1
                        rewardSum+=reward
                        t_childrens[index] = (child_parent,child_playout,reward,child_childrens)
                    tempEndTime = time.time()
                    simulationTime += tempEndTime-tempStartTime
                #应用修改到本体
                child[idx] = (parent, t_playout, reward, t_childrens)
            #继续处理子结点
            child = t_childrens

        if randomTime!=0:
            tempStartTime = time.time() #反向传播过程
            child = PATHROOT
            for temp in current_path:
                #遍历最佳路径
                idx = 0
                for n_tuple in child:
                    #找到最佳路径中此节点对应的子节点
                    parent, t_playout, reward, t_childrens = n_tuple
                    if temp[0] == parent[0] and temp[1] == parent[1]:
                        break
                    idx += 1

                if temp[0] == parent[0] and temp[1] == parent[1]:
                    #找到了对应的结点，修改场数与胜利数
                    t_playout += randomTime
                    reward += rewardSum

                    #应用修改到本体
                    child[idx] = (parent, t_playout, reward, t_childrens)
                #继续处理子结点
                child = t_childrens
            tempEndTime = time.time()
            BackTime += tempEndTime-tempStartTime

    max_avg_reward = -1
    mt_result = (0, 0)
    for n_tuple in PATHROOT:
        parent, t_playout, reward, t_childrens = n_tuple

        if (t_playout > 0) and (reward / t_playout > max_avg_reward):
            mt_result = parent
            max_avg_reward = reward / t_playout
    print("选择阶段用时"+ str(slectTime))
    print("扩展阶段用时"+ str(expendTime))
    print("循环次数为"+ str(looptime))
    print("模拟次数为"+ str(simulationTimes))
    print("模拟阶段用时"+ str(simulationTime))
    print("回溯阶段用时"+ str(BackTime))

    return mt_result