資源下載地址：https://download.csdn.net/download/sheziqiong/85836329
資源下載地址：https://download.csdn.net/download/sheziqiong/85836329
利用給出的 board.py，使用蒙特卡洛樹搜索算法來完成黑白棋 AI。
AI 需要完成的功能：
在當前棋盤狀態下，選擇一個合法且在算法上最優的落子位置，作為返回值
搜索及決策時間不超過一分鐘，若無合法位置則返回 None
在游戲結束（即雙方均無合法落子位置）時，盡量最大化己方與對方的棋子數量差
設計思想
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，從根往下，選擇一個兒子沒有被完全訪問過的節點
Expand_Candidate = x if ((x in node.sons) and (not x.visited))
Node_to_expand = random.choice(Expand_Candidate)
# Expansion，隨機選擇一個沒有被訪問過的兒子節點
Leaf = node
For (node = Node_to_sxpand; node has son; node =
random.choice(node.sons))
Leaf = node
# Simulation，隨機選擇兒子節點直到葉子節點
For (node = Leaf; node != root; node = node.father)
Update(node)
# Back Propagation, 更新訪問過的信息以及勝負/獎勵分數信息
在搜索過程中，每一次“采樣”都有四個步驟：選擇，擴展，模擬和反向傳播：
但是根據 UCB 的 score 函數組成，其實能發現 k 如果只是作為乘上去的系數，本質上就是 C，不過添加一個 k 可以方便調整也更直觀而已。
最後就是搜索次數可以對搜索效果產生影響了，由於給出了一分鐘的落子時限，雖然在測試時使用的 25s 采樣時間效果已經不錯了，但在提交的時候應該還是會頂著時間上限吧（笑）
代碼內容
================================================================
//UCB1：
def UCB1(self, color, board_in):
""" :param color: 當前節點對應的顏色 :param board_in: 當前棋盤狀態 :return : 根據采樣結果，對 AI 方最有利的落子位置 """
board = deepcopy(board_in)
score_act = None
act = None
action_list = list(board.get_legal_actions(color))
rec_sum = 0 # 記錄這個節點的總分（用來算 select 的子節點）
for action in action_list:
play_board = deepcopy(board)
play_board._move(action, color)
tmp_key = tuple(np.ravel(play_board._board))
# 計算該 action 後對應的棋盤的 key 值
if self.rec.get((color, tmp_key)):
# 訪問過則繼續計算總分
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))
))
# 計算鍵值 以及積分
if score_act == None:
score_act, act = (score_tmp, action)
else:
if score_act < score_tmp:
score_act, act = (score_tmp, action)
# 更新積分最高的子節點
return act
====================================================================
//選擇：
def Select(self, board):
""" :param board: 輸入需要被搜索的棋盤 :return: color 是 select 到最後的那個節點已經落子的棋子顏色, act 是上一個 落子的位置, tmpkey 是這個棋盤的狀態 """
color = self.color
while(True):
# 一直 select 直到有一個節點沒有完全被擴展
action_list = list(board.get_legal_actions(color))
if len(action_list) == 0:
return None, None, None
all_explored = True # 這個節點的子節點是否全部訪問過
non_vis_son = [] # 記錄沒有訪問過的兒子節點
rec_sum = 0 # 記錄這個節點的總分（用來算 select 的子節點）
for action in action_list:
play_board = deepcopy(board)
play_board._move(action, color)
tmp_key = tuple(np.ravel(play_board._board))
# 計算該 action 後對應的棋盤的 key 值
if not self.rec.get((color, tmp_key)):
# 沒有訪問過則記錄 該子節點 以及更新節點未訪問信息
all_explored = False
non_vis_son.append((action, tmp_key))
else:
# 訪問過則繼續計算總分
rec_sum += self.rec.get((color, tmp_key))
if all_explored:
# 如果全部訪問過，則在該節點中選擇分數最高的兒子
act = self.UCB1(color, board)
else:
# 有未訪問節點，則隨機返回一個未訪問節點，作為 extend 的對象
act, tmp_key = (random.choice(non_vis_son))
board._move(act, color)
return (color, act, tmp_key)
# 到這裡的時候應該是要 select 下一個節點了
board._move(act, color)
tmp_key = tuple(np.ravel(board._board))
# 落子，更新新棋盤的 key 值
self.vis.add((color, tmp_key))
# 記錄路徑上的節點信息
color = "X" if color == "O" else "O"
# 切換顏色
====================================================================
//擴展：
def Expand(self, board, color, act, tmpkey):
""" :param board: 當前要擴展的棋盤 :param color: 當前已經落子的棋子顏色 :param act: 當前已經落子的位置 :param tmpkey: 當前棋盤狀態 :return: 返回乘上系數後得到的分差 """
game_state, scr_diff = self.Simulate(board, color)
self.rec[(color, tmpkey)] = 1
# 記錄該節點下的訪問次數+1
if (game_state == 0 and self.color == "O") or (game_state == 1 and
self.color == "X"):
scr_diff = - scr_diff
# 把 scr_diff 改成（AI-對方）的分差，可以為負
scr_diff *= 0.4
# 加一個系數
if color == self.color:
# 如果當前決策節點的顏色是 AI 的顏色，則加上分差，否則減去分差
self.scr[(color, tmpkey)] = scr_diff
else:
self.scr[(color, tmpkey)] = - scr_diff
return scr_diff
====================================================================
//模擬：
def Simulate(self, board, player):
""" 用隨機來模擬下棋過程 :param board: 當前棋盤狀態 :param player: 當前剛完成落子的玩家 :return: (winner, 分數差), 其中 winner 是 0 黑棋， 1 白棋， 2 平局 """
while(True):
player = "X" if player == "O" else "O"
# 切換執棋方
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 平局
# 後面還有個分數差的參數
break
else:
continue
if len(legal_actions) == 0:
action = None
else:
action = random.choice(legal_actions)
# 用隨機落子來模擬
if action is None:
continue
else:
board._move(action, player)
if self.game_over(board):
return board.get_winner()
====================================================================
//Back Propagation：
def BackPropagate(self, scr_diff):
""" :param scr_diff: 乘上系數的 AI 與對手的分數差 """
for (color, key) in self.vis:
self.rec[(color, key)] += 1
if color == self.color:
# 如果當前決策節點的顏色是 AI 的顏色，則加上分差，否則減去分差
self.scr[(color, key)] += scr_diff
else:
self.scr[(color, key)] -= scr_diff
====================================================================
//UCTS 的主要部分：
def MCTS_choice(self, board_input):
""" :param board_input: 輸入當前棋盤 :return: 返回落子坐標 樹的狀態節點用 rec 和 scr 兩個 dict 來存儲，存下了（當前落子方，棋盤狀態）： （訪問次數，合計分數）的狀態 """
starttime = datetime.datetime.now()
count = 0
while True:
count += 1
currenttime = 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 是對方的顏色
self.vis = set()
# 記錄樹上搜索過的路徑，方便更新
color, act, tmpkey = self.Select(board)
# color 是 select 到最後的那個節點已經落子的棋子顏色
# act 是上一個落子的位置
# tmpkey 是這個棋盤的狀態
if color == None:
# 如果沒有可以落子的地方，進入下一輪嘗試
continue
scr_diff = self.Expand(board, color, act, tmpkey)
# Expand 得到當前擴展節點的分數，並用於 bp
self.BackPropagate(scr_diff)
print(count)
return self.UCB1(self.color, board_input)
資源下載地址：https://download.csdn.net/download/sheziqiong/85836329
資源下載地址：https://download.csdn.net/download/sheziqiong/85836329
