Python蒙特卡洛树搜索算法实现的黑白棋AI系统

资源下载地址：https://download.csdn.net/download/sheziqiong/85836329
资源下载地址：https://download.csdn.net/download/sheziqiong/85836329

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

AI 需要完成的功能：

1. 在当前棋盘状态下，选择一个合法且在算法上最优的落子位置，作为返回值

2. 搜索及决策时间不超过一分钟，若无合法位置则返回 None

3. 在游戏结束（即双方均无合法落子位置）时，尽量最大化己方与对方的棋子数量差

设计思想

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, 更新访问过的信息以及胜负/奖励分数信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在搜索过程中，每一次“采样”都有四个步骤：选择，扩展，模拟和反向传播：

1. 其中选择主要受到 UCB 函数中 C 值的影响
2. 扩展完全随机
3. 模拟时由于黑白棋合法落子位置与当前局面的相关性非常大，没有找到随机以外的 合适方式进行落子（基于当前局面的贪心甚至不如随机算法）
4. 反向传播时更新的收益分数也是可以人为影响算法效益的部分。由于 board.py 提 供了分数差的信息，可以用分数差的相关函数作为奖励收益（此处采用了分数差*k， k 为人为规定的系数）

但是根据 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

实验结果

资源下载地址：https://download.csdn.net/download/sheziqiong/85836329
资源下载地址：https://download.csdn.net/download/sheziqiong/85836329