1. 首页首页
  2. 编程基础编程基础

基于MCTS的黑白棋（翻转棋、苹果棋）ai算法介绍，附源码、运行图

编程基础 • • 阅读 15

基于MCTS的黑白棋（翻转棋、苹果棋）ai算法介绍，附源码、运行图以黑白棋 翻转棋 苹果棋 为例对 MCTS 算法进行说明 minialphago

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

参考文章：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
今天的文章 基于MCTS的黑白棋（翻转棋、苹果棋）ai算法介绍，附源码、运行图分享到此就结束了，感谢您的阅读。
编程小号
上一篇 2024-12-15 21:11
下一篇 2024-12-15 21:06

相关推荐

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/86891.html