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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
| import math
import copy
import random
import numpy as np
class GoNode:
def __init__(self, color, steps, remove_nodes={}):
self.color = color
self.steps = steps
self.remove_nodes = remove_nodes
def __hash__(self) -> int:
return hash(self.color) + hash(self.steps)
def __eq__(self, other):
if isinstance(other, self.__class__):
return self.color == other.color and self.steps == other.steps
else:
return False
class Board:
def __init__(self, n):
self.matrix = [[GoNode(0, 0) for i in range(n)] for j in range(n)]
self.__n = n
self.__stop_nodes = {}
self.latest_color = -1
self.latest_steps = 0
def __str__(self):
out_str = ""
for i in range(self.__n):
for j in range(self.__n):
out_str += str(self.matrix[i][j].color)
return out_str
def step(self, x, y):
if self.matrix[x][y].color != 0:
return False, None
_, latest_node = self.__get_latest_node()
if (
latest_node is not None
and len(latest_node.remove_nodes) == 1
and list(latest_node.remove_nodes.keys())[0] == (x, y)
):
return False, None
self.latest_color *= -1
self.latest_steps += 1
self.matrix[x][y] = GoNode(self.latest_color, self.latest_steps)
result_liberties = self.__cal_liberties(x, y, self.latest_color, {}, {})
result_remove = self.__remove_dead_node(x, y, self.latest_color, {})
remove_num = len(result_remove)
if len(result_liberties[1]) == 0 and not remove_num > 0:
self.latest_color *= -1
self.latest_steps -= 1
self.matrix[x][y] = GoNode(0, 0)
return False, None
if remove_num > 0:
self.matrix[x][y].remove_nodes = result_remove
return True, remove_num
def step_back(self):
if self.latest_steps > 0:
self.latest_color *= -1
self.latest_steps -= 1
(x, y), latest_node = self.__get_latest_node()
if latest_node is not None:
if latest_node in self.__stop_nodes:
del self.__stop_nodes[latest_node]
else:
self.matrix[x][y] = GoNode(0, 0)
for (rx, ry), node in latest_node.remove_nodes.items():
self.matrix[rx][ry] = node
def step_none(self):
self.latest_color *= -1
self.latest_steps += 1
self.__stop_nodes[GoNode(0, self.latest_steps)] = 1
def get_winner(self):
black, white = self.get_result()
white += 3.75
if black > white:
return 1
elif black < white:
return -1
else:
return 0
def get_result(self):
board_matrix = self.__get_pure_board()
score_black = np.sum(board_matrix == 1)
score_white = np.sum(board_matrix == -1)
score_black_empty = 0
score_white_empty = 0
empties = zip(*np.where(board_matrix == 0))
cache_result = {}
for empty in empties:
visited = {}
result_spread = self.__get_spread_result(
board_matrix, empty[0], empty[1], visited, cache_result
)
cache_result[empty] = result_spread
if result_spread == (True, False):
score_black_empty += 1
elif result_spread == (False, True):
score_white_empty += 1
return score_black + score_black_empty, score_white + score_white_empty
def get_legal_positions(self):
legal_positions = []
for i in range(self.__n):
for j in range(self.__n):
if self.__is_legal(i, j):
legal_positions.append((i, j))
return legal_positions
def __get_pure_board(self):
pure_matrix = np.zeros((self.__n, self.__n))
for i in range(self.__n):
for j in range(self.__n):
pure_matrix[i][j] = self.matrix[i][j].color
return pure_matrix
def __get_spread_result(self, board_matrix, i, j, visited, cache_result):
if (i, j) in cache_result:
return cache_result[(i, j)]
visited[(i, j)] = True
candidate_pos = [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
result = [False, False]
for x, y in candidate_pos:
if x < 0 or x >= self.__n or y < 0 or y >= self.__n or visited.get((x, y), False):
continue
if board_matrix[x][y] == 1:
result[0] = True
elif board_matrix[x][y] == -1:
result[1] = True
else:
ret = self.__get_spread_result(
board_matrix, x, y, visited, cache_result
)
result[0] |= ret[0]
result[1] |= ret[1]
return tuple(result)
def __cal_liberties(self, x, y, color, chess_checked={}, territory_checked={}):
chess_checked[(x, y)] = 1
candidates_pos = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
for nx, ny in candidates_pos:
if nx < 0 or nx >= self.__n or ny < 0 or ny >= self.__n:
continue
if self.matrix[nx][ny].color == 0 and (nx, ny) not in territory_checked:
territory_checked[(nx, ny)] = 1
elif self.matrix[nx][ny].color != 0:
if self.matrix[nx][ny].color == color and (nx, ny) not in chess_checked:
result = self.__cal_liberties(
nx, ny, color, chess_checked, territory_checked
)
chess_checked = {**chess_checked, **result[0]}
territory_checked = {**territory_checked, **result[1]}
return chess_checked, territory_checked
def __remove_dead_node(self, x, y, color, chess_checked={}):
waitRemove = {}
chess_checked[(x, y)] = 1
candidates_pos = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
for nx, ny in candidates_pos:
if nx < 0 or nx >= self.__n or ny < 0 or ny >= self.__n:
continue
if self.matrix[nx][ny].color != 0 and (nx, ny) not in chess_checked:
if self.matrix[nx][ny].color != color:
result_liberties = self.__cal_liberties(
nx, ny, self.matrix[nx][ny].color, {}, {}
)
if len(result_liberties[0]) > 0 and len(result_liberties[1]) == 0:
waitRemove = {**waitRemove, **result_liberties[0]}
result_remove = {}
for rx, ry in waitRemove:
result_remove[(rx, ry)] = self.matrix[rx][ry]
self.matrix[rx][ry] = GoNode(0, 0)
return result_remove
def __get_latest_node(self):
pos = (None, None)
latest_node = None
for i in range(self.__n):
for j in range(self.__n):
node = self.matrix[i][j]
if node.color == 0:
continue
if latest_node is None:
latest_node = node
pos = (i, j)
elif node.steps > latest_node.steps:
latest_node = node
pos = (i, j)
for node in self.__stop_nodes:
if node.steps > latest_node.steps:
latest_node = node
return pos, latest_node
def __is_legal(self, x, y):
is_success, _ = self.step(x, y)
if not is_success:
return False
self.step_back()
return True
class TreeNode:
def __init__(self, board: Board, father, pos_from_father):
self.board = board
self.child = []
self.father = father
self.value = 0
self.times = 0
self.pos_from_father = pos_from_father
def uct_score(self, iter, color, c=2):
if self.times == 0:
return float("inf")
if color == 1:
return self.value / self.times + c * math.sqrt(math.log(iter) / self.times)
else:
return (
1 - self.value / self.times + c * math.sqrt(math.log(iter) / self.times)
)
def expand(self):
legal_pos = self.board.get_legal_positions()
for x, y in legal_pos:
new_board = copy.deepcopy(self.board)
new_board.step(x, y)
self.child.append(TreeNode(new_board, self, (x, y)))
def select(self, iter, color):
max_uct_score = self.child[0].uct_score(iter, color)
select_node = self.child[0]
for i in range(1, len(self.child)):
child_uct_score = self.child[i].uct_score(iter, color)
if child_uct_score > max_uct_score:
max_uct_score = child_uct_score
select_node = self.child[i]
return select_node
def rollout(self):
rollout_board = copy.deepcopy(self.board)
board_map = {}
while True:
legal_pos = rollout_board.get_legal_positions()
if str(rollout_board) in board_map or len(legal_pos) == 0:
return rollout_board.get_winner()
random_pos = random.choice(legal_pos)
rollout_board.step(random_pos[0], random_pos[1])
board_map[str(rollout_board)] = 1
def update(self, value):
self.value += value
self.times += 1
def is_leaf_node(self, ):
return len(self.child) == 0
def is_done(self):
legal_pos = self.board.get_legal_positions()
return len(legal_pos) == 0
class MCTS:
def __init__(self, board, max_iter=1):
self.root = TreeNode(copy.deepcopy(board), None, None)
self.max_iter = max_iter
def run(self):
for i in range(self.max_iter):
if i % 10 == 0:
print(f"Current iter: {i}")
cur_node = self.root
while not cur_node.is_leaf_node():
cur_node = cur_node.select(i, cur_node.board.latest_color * -1)
is_done = cur_node.is_done()
if not is_done:
cur_node.expand()
cur_node = cur_node.select(i, cur_node.board.latest_color * -1)
winner = cur_node.rollout()
else:
winner = cur_node.board.get_winner()
while(cur_node.father != None):
cur_node.update(winner)
cur_node = cur_node.father
cur_node.update(winner)
def opt_step(self):
max_times = 0
opt_pos = None
for node in self.root.child:
if node.times > max_times:
max_times = node.times
opt_pos = node.pos_from_father
return opt_pos[0], opt_pos[1]
|