資源下載地址：https://download.csdn.net/download/sheziqiong/85836329
資源下載地址：https://download.csdn.net/download/sheziqiong/85836329

利用給出的 board.py，使用蒙特卡洛樹搜索算法來完成黑白棋 AI。

AI 需要完成的功能：

在當(dāng)前棋盤狀態(tài)下，選擇一個(gè)合法且在算法上最優(yōu)的落子位置，作為返回值

搜索及決策時(shí)間不超過一分鐘，若無合法位置則返回 None

在游戲結(jié)束（即雙方均無合法落子位置）時(shí)，盡量最大化己方與對(duì)方的棋子數(shù)量差

設(shè)計(jì)思想

While (time_is_enough): For (node = root; all son_node.visited in node.sons; node = choson_son) Choson_son = the son with max UCB of node# Selection，從根往下，選擇一個(gè)兒子沒有被完全訪問過的節(jié)點(diǎn)Expand_Candidate = x if ((x in node.sons) and (not x.visited))Node_to_expand = random.choice(Expand_Candidate)# Expansion，隨機(jī)選擇一個(gè)沒有被訪問過的兒子節(jié)點(diǎn)Leaf = nodeFor (node = Node_to_sxpand; node has son; node = random.choice(node.sons)) Leaf = node # Simulation，隨機(jī)選擇兒子節(jié)點(diǎn)直到葉子節(jié)點(diǎn) For (node = Leaf; node != root; node = node.father) Update(node) # Back Propagation, 更新訪問過的信息以及勝負(fù)/獎(jiǎng)勵(lì)分?jǐn)?shù)信息

在搜索過程中，每一次“采樣”都有四個(gè)步驟：選擇，擴(kuò)展，模擬和反向傳播：

其中選擇主要受到 UCB 函數(shù)中 C 值的影響

擴(kuò)展完全隨機(jī)

模擬時(shí)由于黑白棋合法落子位置與當(dāng)前局面的相關(guān)性非常大，沒有找到隨機(jī)以外的 合適方式進(jìn)行落子（基于當(dāng)前局面的貪心甚至不如隨機(jī)算法）

反向傳播時(shí)更新的收益分?jǐn)?shù)也是可以人為影響算法效益的部分。由于 board.py 提 供了分?jǐn)?shù)差的信息，可以用分?jǐn)?shù)差的相關(guān)函數(shù)作為獎(jiǎng)勵(lì)收益（此處采用了分?jǐn)?shù)差*k， k 為人為規(guī)定的系數(shù)）

但是根據(jù) UCB 的 score 函數(shù)組成，其實(shí)能發(fā)現(xiàn) k 如果只是作為乘上去的系數(shù)，本質(zhì)上就是 C，不過添加一個(gè) k 可以方便調(diào)整也更直觀而已。

最后就是搜索次數(shù)可以對(duì)搜索效果產(chǎn)生影響了，由于給出了一分鐘的落子時(shí)限，雖然在測(cè)試時(shí)使用的 25s 采樣時(shí)間效果已經(jīng)不錯(cuò)了，但在提交的時(shí)候應(yīng)該還是會(huì)頂著時(shí)間上限吧（笑）

代碼內(nèi)容

================================================================ //UCB1：def UCB1(self, color, board_in):""":param color: 當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的顏色:param board_in: 當(dāng)前棋盤狀態(tài):return : 根據(jù)采樣結(jié)果，對(duì) AI 方最有利的落子位置"""board = deepcopy(board_in)score_act = Noneact = Noneaction_list = list(board.get_legal_actions(color))rec_sum = 0 # 記錄這個(gè)節(jié)點(diǎn)的總分（用來算 select 的子節(jié)點(diǎn)）for action in action_list:play_board = deepcopy(board)play_board._move(action, color)tmp_key = tuple(np.ravel(play_board._board))# 計(jì)算該 action 后對(duì)應(yīng)的棋盤的 key 值if self.rec.get((color, tmp_key)):# 訪問過則繼續(xù)計(jì)算總分rec_sum += self.rec.get((color, tmp_key))for action in action_list:play_board = deepcopy(board)play_board._move(action, color)tmp_key = tuple(np.ravel(play_board._board))score_tmp = (self.scr.get((color, tmp_key)) / self.rec.get((color, tmp_key)) + self.C * math.sqrt(math.log(rec_sum) / self.rec.get((color, tmp_key))))# 計(jì)算鍵值 以及積分if score_act == None:score_act, act = (score_tmp, action)else:if score_act < score_tmp:score_act, act = (score_tmp, action)# 更新積分最高的子節(jié)點(diǎn)return act ==================================================================== //選擇：def Select(self, board):""" :param board: 輸入需要被搜索的棋盤:return: color 是 select 到最后的那個(gè)節(jié)點(diǎn)已經(jīng)落子的棋子顏色, act 是上一個(gè) 落子的位置, tmpkey 是這個(gè)棋盤的狀態(tài)"""color = self.colorwhile(True):# 一直 select 直到有一個(gè)節(jié)點(diǎn)沒有完全被擴(kuò)展action_list = list(board.get_legal_actions(color))if len(action_list) == 0:return None, None, Noneall_explored = True # 這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)是否全部訪問過non_vis_son = [] # 記錄沒有訪問過的兒子節(jié)點(diǎn)rec_sum = 0 # 記錄這個(gè)節(jié)點(diǎn)的總分（用來算 select 的子節(jié)點(diǎn)）for action in action_list:play_board = deepcopy(board)play_board._move(action, color)tmp_key = tuple(np.ravel(play_board._board))# 計(jì)算該 action 后對(duì)應(yīng)的棋盤的 key 值if not self.rec.get((color, tmp_key)):# 沒有訪問過則記錄 該子節(jié)點(diǎn) 以及更新節(jié)點(diǎn)未訪問信息all_explored = Falsenon_vis_son.append((action, tmp_key))else:# 訪問過則繼續(xù)計(jì)算總分rec_sum += self.rec.get((color, tmp_key))if all_explored:# 如果全部訪問過，則在該節(jié)點(diǎn)中選擇分?jǐn)?shù)最高的兒子act = self.UCB1(color, board)else:# 有未訪問節(jié)點(diǎn)，則隨機(jī)返回一個(gè)未訪問節(jié)點(diǎn)，作為 extend 的對(duì)象act, tmp_key = (random.choice(non_vis_son))board._move(act, color)return (color, act, tmp_key)# 到這里的時(shí)候應(yīng)該是要 select 下一個(gè)節(jié)點(diǎn)了board._move(act, color)tmp_key = tuple(np.ravel(board._board))# 落子，更新新棋盤的 key 值self.vis.add((color, tmp_key))# 記錄路徑上的節(jié)點(diǎn)信息color = "X" if color == "O" else "O"# 切換顏色 ==================================================================== //擴(kuò)展：def Expand(self, board, color, act, tmpkey):""":param board: 當(dāng)前要擴(kuò)展的棋盤:param color: 當(dāng)前已經(jīng)落子的棋子顏色:param act: 當(dāng)前已經(jīng)落子的位置:param tmpkey: 當(dāng)前棋盤狀態(tài):return: 返回乘上系數(shù)后得到的分差"""game_state, scr_diff = self.Simulate(board, color)self.rec[(color, tmpkey)] = 1# 記錄該節(jié)點(diǎn)下的訪問次數(shù)+1if (game_state == 0 and self.color == "O") or (game_state == 1 and self.color == "X"):scr_diff = - scr_diff# 把 scr_diff 改成（AI-對(duì)方）的分差，可以為負(fù)scr_diff *= 0.4# 加一個(gè)系數(shù)if color == self.color:# 如果當(dāng)前決策節(jié)點(diǎn)的顏色是 AI 的顏色，則加上分差，否則減去分差self.scr[(color, tmpkey)] = scr_diffelse:self.scr[(color, tmpkey)] = - scr_diffreturn scr_diff ==================================================================== //模擬：def Simulate(self, board, player):"""用隨機(jī)來模擬下棋過程:param board: 當(dāng)前棋盤狀態(tài):param player: 當(dāng)前剛完成落子的玩家:return: (winner, 分?jǐn)?shù)差), 其中 winner 是 0 黑棋， 1 白棋， 2 平局"""while(True):player = "X" if player == "O" else "O"# 切換執(zhí)棋方legal_actions = list(board.get_legal_actions(player))if len(legal_actions) == 0:if self.game_over(board):return board.get_winner()# 0 黑棋， 1 白棋， 2 平局# 后面還有個(gè)分?jǐn)?shù)差的參數(shù)break else:continueif len(legal_actions) == 0:action = Noneelse:action = random.choice(legal_actions)# 用隨機(jī)落子來模擬if action is None:continueelse:board._move(action, player)if self.game_over(board):return board.get_winner() ==================================================================== //Back Propagation：def BackPropagate(self, scr_diff):""":param scr_diff: 乘上系數(shù)的 AI 與對(duì)手的分?jǐn)?shù)差"""for (color, key) in self.vis:self.rec[(color, key)] += 1if color == self.color: # 如果當(dāng)前決策節(jié)點(diǎn)的顏色是 AI 的顏色，則加上分差，否則減去分差self.scr[(color, key)] += scr_diffelse:self.scr[(color, key)] -= scr_diff ==================================================================== //UCTS 的主要部分：def MCTS_choice(self, board_input):""":param board_input: 輸入當(dāng)前棋盤:return: 返回落子坐標(biāo)樹的狀態(tài)節(jié)點(diǎn)用 rec 和 scr 兩個(gè) dict 來存儲(chǔ)，存下了（當(dāng)前落子方，棋盤狀態(tài)）： （訪問次數(shù)，合計(jì)分?jǐn)?shù)）的狀態(tài)"""starttime = datetime.datetime.now()count = 0while True: count += 1currenttime = datetime.datetime.now()if (currenttime - starttime).seconds > 3 or count > 1000:break board = deepcopy(board_input)color = "X" if self.color == "O" else "O"# color 是對(duì)方的顏色self.vis = set() # 記錄樹上搜索過的路徑，方便更新color, act, tmpkey = self.Select(board) # color 是 select 到最后的那個(gè)節(jié)點(diǎn)已經(jīng)落子的棋子顏色# act 是上一個(gè)落子的位置# tmpkey 是這個(gè)棋盤的狀態(tài)if color == None:# 如果沒有可以落子的地方，進(jìn)入下一輪嘗試continue scr_diff = self.Expand(board, color, act, tmpkey)# Expand 得到當(dāng)前擴(kuò)展節(jié)點(diǎn)的分?jǐn)?shù)，并用于 bpself.BackPropagate(scr_diff)print(count)return self.UCB1(self.color, board_input)

實(shí)驗(yàn)結(jié)果

資源下載地址：https://download.csdn.net/download/sheziqiong/85836329
資源下載地址：https://download.csdn.net/download/sheziqiong/85836329

總結(jié)

以上是生活随笔為你收集整理的Python蒙特卡洛树搜索算法实现的黑白棋AI系统的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。