Advantages of Reinforcement Learning
Trong khi trong các phương pháp lý thuyết trò chơi nói chung, ví dụ thuật toán min-max, thuật toán luôn giả định chúng ta có một đối thủ hoàn hảo, công việc phải thực hiện là tối đa hóa phần thưởng của mình và giảm thiểu phần thưởng của đối thủ ( tối đa hóa điểm của mình và tối thiểu hóa điểm của đối thủ), trong học củng cố, chúng ta không cần giả định đối thủ của chúng ta là 1 thiên tài xuất chúng, nhưng chung ta vẫn thu được mô hình với kết quả rất tốt.
Bằng cách coi đối thủ là một phần của môi trường mà chúng ta có thể tương tác, sau một số lần lặp lại nhất định, đối thủ có thể lập kế hoạch trước mà không cần chúng ta phải làm gì cả. Ưu điểm của phương pháp này là giảm số lượng không gian tìm kiếm và giảm số phép toán suy luận phải thực hiện, nhưng nó có thể đạt được kỹ năng hiện đại chỉ bằng cách thử và học.
Trong bài viết này, chúng ta sẽ làm các công việc sau:
-
Thứ nhất, huấn luyện mô hình cho 2 máy đấu với nhau mà thu được các trọng số cần thiết.
-
Thứ hai, cho người đánh với máy
Để hình thành bài toán học củng cố Reinforcement Learning , chúng ta cần phải xác định rõ 3 thành phần chính:
-
State
-
Action
-
Reward
Với:
State chính là bàn cờ với các nước đi của các người chơi. Chúng ta sẽ tạo một bàn cờ có kích thước 3x3, giá trị của mỗi ô cờ đều là 0. Vị trí người chơi 1 đặt quân sẽ được gán là 1. Vị trí người chơi 2 đặt quân sẽ được gán là -1.
Action là vị trí người chơi sẽ đi quân khi biết state hiện tại (nghĩa là biết đối thủ đi nước nào, và có những nước nào hiện đang trên bàn cờ).
Reward: mang giá trị 0 hoặc 1. Khi kết thúc game sẽ trả về giá trị cho reward.
Ở phần dưới đây, mình sẽ note lại code và sẽ comment trong code để cho rõ ý
Thiết lập bàn cờ
Khởi tạo bàn cờ
1
2def __init__(self, p1, p2):
3 self.board = np.zeros((BOARD_ROWS, BOARD_COLS))
4 self.p1 = p1
5 self.p2 = p2
6 self.isEnd = False
7 self.boardHash = None
8 # init p1 plays first
9 self.playerSymbol = 1
Chúng ta sẽ tạo một bàn cờ có kích thước 3x3, 2 biến người chơi. Người 1 là người chơi đầu tiên.
1
2# Trả về danh sách các nước có thể đi
3def availablePositions(self):
4 positions = []
5 for i in range(BOARD_ROWS):
6 for j in range(BOARD_COLS):
7 if self.board[i, j] == 0:
8 positions.append((i, j)) # need to be tuple
9 return positions
10
11# Cập nhật lại lên bàn cờ vị trí của người chơi đặt quân
12
13def updateState(self, position):
14 self.board[position] = self.playerSymbol
15 # switch to another player
16 self.playerSymbol = -1 if self.playerSymbol == 1 else 1
Kiểm tra Reward
Sau mỗi nước đi của các kỳ thủ, chúng ta cần 1 hàm để kiểm tra xem kỳ thủ thắng hay thua và trả về kết quả cho reward như đề cập ở trên
1
2def winner(self):
3
4 # Kiểm tra theo dòng
5
6 for i in range(BOARD_ROWS):
7 if sum(self.board[i, :]) == 3:
8 self.isEnd = True
9 return 1
10 if sum(self.board[i, :]) == -3:
11 self.isEnd = True
12 return -1
13 # kiểm tra theo cột
14
15 for i in range(BOARD_COLS):
16 if sum(self.board[:, i]) == 3:
17 self.isEnd = True
18 return 1
19 if sum(self.board[:, i]) == -3:
20 self.isEnd = True
21 return -1
22
23 # kiểm tra theo đường chéo chính và theo đường chéo phụ
24
25 diag_sum1 = sum([self.board[i, i] for i in range(BOARD_COLS)]) # đường chéo chính
26
27 diag_sum2 = sum([self.board[i, BOARD_COLS - i - 1] for i in range(BOARD_COLS)]) # đường chéo phụ
28
29 diag_sum = max(abs(diag_sum1), abs(diag_sum2)) # lấy trị tuyệt đối của các nước đi, nếu bằng 3 nghĩa là có người chơi chiến thắng
30
31 if diag_sum == 3:
32 self.isEnd = True
33 if diag_sum1 == 3 or diag_sum2 == 3:
34 return 1
35 else:
36 return -1
37
38 # Kiểm tra xem còn nước đi hay không
39 if len(self.availablePositions()) == 0:
40 self.isEnd = True
41 return 0
42
43 # not end
44 self.isEnd = False
45 return None
46
47# only when game ends
48def giveReward(self):
49 result = self.winner()
50 # backpropagate reward
51 if result == 1:
52 self.p1.feedReward(1)
53 self.p2.feedReward(0)
54 elif result == -1:
55 self.p1.feedReward(0)
56 self.p2.feedReward(1)
57 else:
58 self.p1.feedReward(0.1)
59 self.p2.feedReward(0.5)
Ở đây có một lưu ý. Khi cờ hòa thì chúng ta cũng xem rằng người đi trước thua, nên hệ số lúc cờ hòa sẽ là 0.1-0.5. Các bạn có thể thiết lập một giá trị khác, ví dụ 0.2-0.5 hoặc 0.5-0.5 tùy thích.
Thiết lập người chơi
Người chơi cần có các phương thức sau:
-
Chọn nước đi dựa trên trạng thái hiện tại của bàn cờ.
-
Lưu lại trạng thái của ván cờ.
-
Cập nhật lại giá trị trạng thái sau mỗi ván.
-
Lưu và load các trọng số lên.
Khởi tạo
1
2def __init__(self, name, exp_rate=0.2):
3 self.name = name
4 self.states = [] # record all positions taken
5 self.lr = 0.2
6 self.exp_rate = exp_rate
7 self.decay_gamma = 0.9
8 self.states_value = {} # state -> value
Chọn nước đi
1
2def chooseAction(self, positions, current_board, symbol):
3 randValue = np.random.uniform(0, 1)
4 value_max = value = -999
5 if randValue> self.exp_rate:
6
7 for p in positions:
8 next_board = current_board.copy()
9 next_board[p] = symbol
10 next_boardHash = self.getHash(next_board)
11 value = -999 if self.states_value.get(next_boardHash) is None else self.states_value.get(next_boardHash)
12 # print("value", value)
13 if value >= value_max:
14 value_max = value
15 action = p
16
17 if value_max == -999 :
18 # take random action
19 idx = np.random.choice(len(positions))
20 action = positions[idx]
21
22 # print("{} takes action {}".format(self.name, action))
23 return action
Cập nhật trạng thái
Chúng ta sẽ cập nhật trạng thái với công thức sau
$$ V(S_t) = V(S_t) + \alpha [V(S_{t+1}) - V(S_t)] $$
Diễn giải ra tiếng việt, giá trị của trạng thái tại thời điểm t bằng giá trị tại thời điểm hiện tại cộng với độ lệch của trạng thái hiện tại và trạng thái tiếp theo nhân với một hệ số học alpha.
1
2# at the end of game, backpropagate and update states value
3def feedReward(self, reward):
4 for st in reversed(self.states):
5 if self.states_value.get(st) is None:
6 self.states_value[st] = 0
7 self.states_value[st] += self.lr * (self.decay_gamma * reward - self.states_value[st])
8 reward = self.states_value[st]
Huấn luyện mô hình
Phần này nằm trong lớp State. Chúng ta sẽ lần lượt đi qua các quá trình luân phiên nhau giữa người chơi 1 và người chơi 2
người chơi chọn nước có thể đi -> cập nhật trạng thái -> kiểm tra thắng/thua -> người chơi chọn nước có thể đi …
1
2def play(self, rounds=100):
3 for i in range(rounds):
4 if i % 1000 == 0:
5 print("Rounds {}".format(i))
6 while not self.isEnd:
7 # Player 1
8 positions = self.availablePositions()
9 p1_action = self.p1.chooseAction(positions, self.board, self.playerSymbol)
10 # take action and upate board state
11 self.updateState(p1_action)
12 board_hash = self.getHash()
13 self.p1.addState(board_hash)
14 # check board status if it is end
15
16 win = self.winner()
17 if win is not None:
18 # self.showBoard()
19 # ended with p1 either win or draw
20 self.giveReward()
21 self.p1.reset()
22 self.p2.reset()
23 self.reset()
24 break
25
26 else:
27 # Player 2
28 positions = self.availablePositions()
29 p2_action = self.p2.chooseAction(positions, self.board, self.playerSymbol)
30 self.updateState(p2_action)
31 board_hash = self.getHash()
32 self.p2.addState(board_hash)
33
34 win = self.winner()
35 if win is not None:
36 # self.showBoard()
37 # ended with p2 either win or draw
38 self.giveReward()
39 self.p1.reset()
40 self.p2.reset()
41 self.reset()
42 break
Sau khi huấn luyện 100 ngàn lần, chúng ta sẽ chơi với máy, chỉ là 1 thay đổi nhỏ trong hàm chooseAction là thay vì lấy nước đi có trọng số lớn nhất, chúng ta sẽ cho người dùng nhập từ bàn phím dòng và cột vào
1
2
3def chooseAction(self, positions):
4 while True:
5 row = int(input("Input your action row:"))
6 col = int(input("Input your action col:"))
7 action = (row, col)
8 if action in positions:
9 return action
Và sửa lại hàm play một chút, bỏ loop 100k lần đi, bỏ gọi hàm cập nhật thưởng và bỏ các hàm reset đi
1
2
3# play with human
4def play2(self):
5 while not self.isEnd:
6 # Player 1
7 positions = self.availablePositions()
8 p1_action = self.p1.chooseAction(positions, self.board, self.playerSymbol)
9 # take action and upate board state
10 self.updateState(p1_action)
11 self.showBoard()
12 # check board status if it is end
13 win = self.winner()
14 if win is not None:
15 if win == 1:
16 print(self.p1.name, "wins!")
17 else:
18 print("tie!")
19 self.reset()
20 break
21
22 else:
23 # Player 2
24 positions = self.availablePositions()
25 p2_action = self.p2.chooseAction(positions)
26
27 self.updateState(p2_action)
28 self.showBoard()
29 win = self.winner()
30 if win is not None:
31 if win == -1:
32 print(self.p2.name, "wins!")
33 else:
34 print("tie!")
35 self.reset()
36 break
Mã nguồn hoàn chỉnh của chương trình
1
2import numpy as np
3import pickle
4
5BOARD_ROWS = 3
6BOARD_COLS = 3
7
8
9class State:
10 def __init__(self, p1, p2):
11 self.board = np.zeros((BOARD_ROWS, BOARD_COLS))
12 self.p1 = p1
13 self.p2 = p2
14 self.isEnd = False
15 self.boardHash = None
16 # init p1 plays first
17 self.playerSymbol = 1
18
19 # get unique hash of current board state
20 def getHash(self):
21 self.boardHash = str(self.board.reshape(BOARD_COLS * BOARD_ROWS))
22 return self.boardHash
23
24 def winner(self):
25 # row
26 for i in range(BOARD_ROWS):
27 if sum(self.board[i, :]) == 3:
28 self.isEnd = True
29 return 1
30 if sum(self.board[i, :]) == -3:
31 self.isEnd = True
32 return -1
33 # col
34 for i in range(BOARD_COLS):
35 if sum(self.board[:, i]) == 3:
36 self.isEnd = True
37 return 1
38 if sum(self.board[:, i]) == -3:
39 self.isEnd = True
40 return -1
41 # diagonal
42 diag_sum1 = sum([self.board[i, i] for i in range(BOARD_COLS)])
43 diag_sum2 = sum([self.board[i, BOARD_COLS - i - 1] for i in range(BOARD_COLS)])
44 diag_sum = max(abs(diag_sum1), abs(diag_sum2))
45 if diag_sum == 3:
46 self.isEnd = True
47 if diag_sum1 == 3 or diag_sum2 == 3:
48 return 1
49 else:
50 return -1
51
52 # tie
53 # no available positions
54 if len(self.availablePositions()) == 0:
55 self.isEnd = True
56 return 0
57 # not end
58 self.isEnd = False
59 return None
60
61 def availablePositions(self):
62 positions = []
63 for i in range(BOARD_ROWS):
64 for j in range(BOARD_COLS):
65 if self.board[i, j] == 0:
66 positions.append((i, j)) # need to be tuple
67 return positions
68
69 def updateState(self, position):
70 self.board[position] = self.playerSymbol
71 # switch to another player
72 self.playerSymbol = -1 if self.playerSymbol == 1 else 1
73
74 # only when game ends
75 def giveReward(self):
76 result = self.winner()
77 # backpropagate reward
78 if result == 1:
79 self.p1.feedReward(1)
80 self.p2.feedReward(0)
81 elif result == -1:
82 self.p1.feedReward(0)
83 self.p2.feedReward(1)
84 else:
85 self.p1.feedReward(0.1)
86 self.p2.feedReward(0.5)
87
88 # board reset
89 def reset(self):
90 self.board = np.zeros((BOARD_ROWS, BOARD_COLS))
91 self.boardHash = None
92 self.isEnd = False
93 self.playerSymbol = 1
94
95 def play(self, rounds=100):
96 for i in range(rounds):
97 if i % 1000 == 0:
98 print("Rounds {}".format(i))
99 while not self.isEnd:
100 # Player 1
101 positions = self.availablePositions()
102 p1_action = self.p1.chooseAction(positions, self.board, self.playerSymbol)
103 # take action and upate board state
104 self.updateState(p1_action)
105 board_hash = self.getHash()
106 self.p1.addState(board_hash)
107 # check board status if it is end
108
109 win = self.winner()
110 if win is not None:
111 # self.showBoard()
112 # ended with p1 either win or draw
113 self.giveReward()
114 self.p1.reset()
115 self.p2.reset()
116 self.reset()
117 break
118
119 else:
120 # Player 2
121 positions = self.availablePositions()
122 p2_action = self.p2.chooseAction(positions, self.board, self.playerSymbol)
123 self.updateState(p2_action)
124 board_hash = self.getHash()
125 self.p2.addState(board_hash)
126
127 win = self.winner()
128 if win is not None:
129 # self.showBoard()
130 # ended with p2 either win or draw
131 self.giveReward()
132 self.p1.reset()
133 self.p2.reset()
134 self.reset()
135 break
136
137
138 # play with human
139 def play2(self):
140 while not self.isEnd:
141 # Player 1
142 positions = self.availablePositions()
143 p1_action = self.p1.chooseAction(positions, self.board, self.playerSymbol)
144 # take action and upate board state
145 self.updateState(p1_action)
146 self.showBoard()
147 # check board status if it is end
148 win = self.winner()
149 if win is not None:
150 if win == 1:
151 print(self.p1.name, "wins!")
152 else:
153 print("tie!")
154 self.reset()
155 break
156
157 else:
158 # Player 2
159 positions = self.availablePositions()
160 p2_action = self.p2.chooseAction(positions)
161
162 self.updateState(p2_action)
163 self.showBoard()
164 win = self.winner()
165 if win is not None:
166 if win == -1:
167 print(self.p2.name, "wins!")
168 else:
169 print("tie!")
170 self.reset()
171 break
172
173
174 def showBoard(self):
175 # p1: x p2: o
176 for i in range(0, BOARD_ROWS):
177 print('-------------')
178 out = '| '
179 for j in range(0, BOARD_COLS):
180 token = ""
181 if self.board[i, j] == 1:
182 token = 'x'
183 if self.board[i, j] == -1:
184 token = 'o'
185 if self.board[i, j] == 0:
186 token = ' '
187 out += token + ' | '
188 print(out)
189 print('-------------')
190
191
192class Player:
193 def __init__(self, name, exp_rate=0.3):
194 self.name = name
195 self.states = [] # record all positions taken
196 self.lr = 0.3
197 self.exp_rate = exp_rate
198 self.decay_gamma = 0.9
199 self.states_value = {} # state -> value
200
201 def getHash(self, board):
202 boardHash = str(board.reshape(BOARD_COLS * BOARD_ROWS))
203 return boardHash
204
205 def chooseAction(self, positions, current_board, symbol):
206 randValue = np.random.uniform(0, 1)
207 value_max = value = -999
208 if randValue> self.exp_rate:
209
210 for p in positions:
211 next_board = current_board.copy()
212 next_board[p] = symbol
213 next_boardHash = self.getHash(next_board)
214 value = -999 if self.states_value.get(next_boardHash) is None else self.states_value.get(next_boardHash)
215 # print("value", value)
216 if value >= value_max:
217 value_max = value
218 action = p
219
220 if value_max == -999 :
221 # take random action
222 idx = np.random.choice(len(positions))
223 action = positions[idx]
224
225 # print("{} takes action {}".format(self.name, action))
226 return action
227
228 # append a hash state
229 def addState(self, state):
230 self.states.append(state)
231
232 # at the end of game, backpropagate and update states value
233 def feedReward(self, reward):
234 for st in reversed(self.states):
235 if self.states_value.get(st) is None:
236 self.states_value[st] = 0
237 self.states_value[st] += self.lr * (self.decay_gamma * reward - self.states_value[st])
238 reward = self.states_value[st]
239
240 def reset(self):
241 self.states = []
242
243 def savePolicy(self):
244 fw = open('policy_' + str(self.name), 'wb')
245 pickle.dump(self.states_value, fw)
246 fw.close()
247
248 def loadPolicy(self, file):
249 fr = open(file, 'rb')
250 self.states_value = pickle.load(fr)
251 fr.close()
252
253
254class HumanPlayer:
255 def __init__(self, name):
256 self.name = name
257
258 def chooseAction(self, positions):
259 while True:
260 row = int(input("Input your action row:"))
261 col = int(input("Input your action col:"))
262 action = (row, col)
263 if action in positions:
264 return action
265
266 # append a hash state
267 def addState(self, state):
268 pass
269
270 # at the end of game, backpropagate and update states value
271 def feedReward(self, reward):
272 pass
273
274 def reset(self):
275 pass
276
277
278if __name__ == "__main__":
279 # training
280 p1 = Player("p1")
281 p2 = Player("p2")
282
283 st = State(p1, p2)
284 print("training...")
285 st.play(100000)
286
287 p1.savePolicy()
288
289 # play with human
290 p1 = Player("computer", exp_rate=0)
291 p1.loadPolicy("policy_p1")
292
293 p2 = HumanPlayer("human")
294
295 st = State(p1, p2)
296 st.play2()
Nguồn
-
Reinforcement Learning: An Introduction phiên bản 2 của Richard S. Sutton and Andrew G. Barto
-
https://towardsdatascience.com/reinforcement-learning-implement-tictactoe-189582bea542
Comments