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ờ
def __init__(self, p1, p2):
self.board = np.zeros((BOARD_ROWS, BOARD_COLS))
self.p1 = p1
self.p2 = p2
self.isEnd = False
self.boardHash = None
# init p1 plays first
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.
# Trả về danh sách các nước có thể đi
def availablePositions(self):
positions = []
for i in range(BOARD_ROWS):
for j in range(BOARD_COLS):
if self.board[i, j] == 0:
positions.append((i, j)) # need to be tuple
return positions
# Cập nhật lại lên bàn cờ vị trí của người chơi đặt quân
def updateState(self, position):
self.board[position] = self.playerSymbol
# switch to another player
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
def winner(self):
# Kiểm tra theo dòng
for i in range(BOARD_ROWS):
if sum(self.board[i, :]) == 3:
self.isEnd = True
return 1
if sum(self.board[i, :]) == -3:
self.isEnd = True
return -1
# kiểm tra theo cột
for i in range(BOARD_COLS):
if sum(self.board[:, i]) == 3:
self.isEnd = True
return 1
if sum(self.board[:, i]) == -3:
self.isEnd = True
return -1
# kiểm tra theo đường chéo chính và theo đường chéo phụ
diag_sum1 = sum([self.board[i, i] for i in range(BOARD_COLS)]) # đường chéo chính
diag_sum2 = sum([self.board[i, BOARD_COLS - i - 1] for i in range(BOARD_COLS)]) # đường chéo phụ
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
if diag_sum == 3:
self.isEnd = True
if diag_sum1 == 3 or diag_sum2 == 3:
return 1
else:
return -1
# Kiểm tra xem còn nước đi hay không
if len(self.availablePositions()) == 0:
self.isEnd = True
return 0
# not end
self.isEnd = False
return None
# only when game ends
def giveReward(self):
result = self.winner()
# backpropagate reward
if result == 1:
self.p1.feedReward(1)
self.p2.feedReward(0)
elif result == -1:
self.p1.feedReward(0)
self.p2.feedReward(1)
else:
self.p1.feedReward(0.1)
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
def __init__(self, name, exp_rate=0.2):
self.name = name
self.states = [] # record all positions taken
self.lr = 0.2
self.exp_rate = exp_rate
self.decay_gamma = 0.9
self.states_value = {} # state -> value
Chọn nước đi
def chooseAction(self, positions, current_board, symbol):
randValue = np.random.uniform(0, 1)
value_max = value = -999
if randValue> self.exp_rate:
for p in positions:
next_board = current_board.copy()
next_board[p] = symbol
next_boardHash = self.getHash(next_board)
value = -999 if self.states_value.get(next_boardHash) is None else self.states_value.get(next_boardHash)
# print("value", value)
if value >= value_max:
value_max = value
action = p
if value_max == -999 :
# take random action
idx = np.random.choice(len(positions))
action = positions[idx]
# print("{} takes action {}".format(self.name, action))
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(St) + \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.
# at the end of game, backpropagate and update states value
def feedReward(self, reward):
for st in reversed(self.states):
if self.states_value.get(st) is None:
self.states_value[st] = 0
self.states_value[st] += self.lr * (self.decay_gamma * reward - self.states_value[st])
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 …
def play(self, rounds=100):
for i in range(rounds):
if i % 1000 == 0:
print("Rounds {}".format(i))
while not self.isEnd:
# Player 1
positions = self.availablePositions()
p1_action = self.p1.chooseAction(positions, self.board, self.playerSymbol)
# take action and upate board state
self.updateState(p1_action)
board_hash = self.getHash()
self.p1.addState(board_hash)
# check board status if it is end
win = self.winner()
if win is not None:
# self.showBoard()
# ended with p1 either win or draw
self.giveReward()
self.p1.reset()
self.p2.reset()
self.reset()
break
else:
# Player 2
positions = self.availablePositions()
p2_action = self.p2.chooseAction(positions, self.board, self.playerSymbol)
self.updateState(p2_action)
board_hash = self.getHash()
self.p2.addState(board_hash)
win = self.winner()
if win is not None:
# self.showBoard()
# ended with p2 either win or draw
self.giveReward()
self.p1.reset()
self.p2.reset()
self.reset()
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
def chooseAction(self, positions):
while True:
row = int(input("Input your action row:"))
col = int(input("Input your action col:"))
action = (row, col)
if action in positions:
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
# play with human
def play2(self):
while not self.isEnd:
# Player 1
positions = self.availablePositions()
p1_action = self.p1.chooseAction(positions, self.board, self.playerSymbol)
# take action and upate board state
self.updateState(p1_action)
self.showBoard()
# check board status if it is end
win = self.winner()
if win is not None:
if win == 1:
print(self.p1.name, "wins!")
else:
print("tie!")
self.reset()
break
else:
# Player 2
positions = self.availablePositions()
p2_action = self.p2.chooseAction(positions)
self.updateState(p2_action)
self.showBoard()
win = self.winner()
if win is not None:
if win == -1:
print(self.p2.name, "wins!")
else:
print("tie!")
self.reset()
break
Mã nguồn hoàn chỉnh của chương trình
import numpy as np
import pickle
BOARD_ROWS = 3
BOARD_COLS = 3
class State:
def __init__(self, p1, p2):
self.board = np.zeros((BOARD_ROWS, BOARD_COLS))
self.p1 = p1
self.p2 = p2
self.isEnd = False
self.boardHash = None
# init p1 plays first
self.playerSymbol = 1
# get unique hash of current board state
def getHash(self):
self.boardHash = str(self.board.reshape(BOARD_COLS * BOARD_ROWS))
return self.boardHash
def winner(self):
# row
for i in range(BOARD_ROWS):
if sum(self.board[i, :]) == 3:
self.isEnd = True
return 1
if sum(self.board[i, :]) == -3:
self.isEnd = True
return -1
# col
for i in range(BOARD_COLS):
if sum(self.board[:, i]) == 3:
self.isEnd = True
return 1
if sum(self.board[:, i]) == -3:
self.isEnd = True
return -1
# diagonal
diag_sum1 = sum([self.board[i, i] for i in range(BOARD_COLS)])
diag_sum2 = sum([self.board[i, BOARD_COLS - i - 1] for i in range(BOARD_COLS)])
diag_sum = max(abs(diag_sum1), abs(diag_sum2))
if diag_sum == 3:
self.isEnd = True
if diag_sum1 == 3 or diag_sum2 == 3:
return 1
else:
return -1
# tie
# no available positions
if len(self.availablePositions()) == 0:
self.isEnd = True
return 0
# not end
self.isEnd = False
return None
def availablePositions(self):
positions = []
for i in range(BOARD_ROWS):
for j in range(BOARD_COLS):
if self.board[i, j] == 0:
positions.append((i, j)) # need to be tuple
return positions
def updateState(self, position):
self.board[position] = self.playerSymbol
# switch to another player
self.playerSymbol = -1 if self.playerSymbol == 1 else 1
# only when game ends
def giveReward(self):
result = self.winner()
# backpropagate reward
if result == 1:
self.p1.feedReward(1)
self.p2.feedReward(0)
elif result == -1:
self.p1.feedReward(0)
self.p2.feedReward(1)
else:
self.p1.feedReward(0.1)
self.p2.feedReward(0.5)
# board reset
def reset(self):
self.board = np.zeros((BOARD_ROWS, BOARD_COLS))
self.boardHash = None
self.isEnd = False
self.playerSymbol = 1
def play(self, rounds=100):
for i in range(rounds):
if i % 1000 == 0:
print("Rounds {}".format(i))
while not self.isEnd:
# Player 1
positions = self.availablePositions()
p1_action = self.p1.chooseAction(positions, self.board, self.playerSymbol)
# take action and upate board state
self.updateState(p1_action)
board_hash = self.getHash()
self.p1.addState(board_hash)
# check board status if it is end
win = self.winner()
if win is not None:
# self.showBoard()
# ended with p1 either win or draw
self.giveReward()
self.p1.reset()
self.p2.reset()
self.reset()
break
else:
# Player 2
positions = self.availablePositions()
p2_action = self.p2.chooseAction(positions, self.board, self.playerSymbol)
self.updateState(p2_action)
board_hash = self.getHash()
self.p2.addState(board_hash)
win = self.winner()
if win is not None:
# self.showBoard()
# ended with p2 either win or draw
self.giveReward()
self.p1.reset()
self.p2.reset()
self.reset()
break
# play with human
def play2(self):
while not self.isEnd:
# Player 1
positions = self.availablePositions()
p1_action = self.p1.chooseAction(positions, self.board, self.playerSymbol)
# take action and upate board state
self.updateState(p1_action)
self.showBoard()
# check board status if it is end
win = self.winner()
if win is not None:
if win == 1:
print(self.p1.name, "wins!")
else:
print("tie!")
self.reset()
break
else:
# Player 2
positions = self.availablePositions()
p2_action = self.p2.chooseAction(positions)
self.updateState(p2_action)
self.showBoard()
win = self.winner()
if win is not None:
if win == -1:
print(self.p2.name, "wins!")
else:
print("tie!")
self.reset()
break
def showBoard(self):
# p1: x p2: o
for i in range(0, BOARD_ROWS):
print('-------------')
out = '| '
for j in range(0, BOARD_COLS):
token = ""
if self.board[i, j] == 1:
token = 'x'
if self.board[i, j] == -1:
token = 'o'
if self.board[i, j] == 0:
token = ' '
out += token + ' | '
print(out)
print('-------------')
class Player:
def __init__(self, name, exp_rate=0.3):
self.name = name
self.states = [] # record all positions taken
self.lr = 0.3
self.exp_rate = exp_rate
self.decay_gamma = 0.9
self.states_value = {} # state -> value
def getHash(self, board):
boardHash = str(board.reshape(BOARD_COLS * BOARD_ROWS))
return boardHash
def chooseAction(self, positions, current_board, symbol):
randValue = np.random.uniform(0, 1)
value_max = value = -999
if randValue> self.exp_rate:
for p in positions:
next_board = current_board.copy()
next_board[p] = symbol
next_boardHash = self.getHash(next_board)
value = -999 if self.states_value.get(next_boardHash) is None else self.states_value.get(next_boardHash)
# print("value", value)
if value >= value_max:
value_max = value
action = p
if value_max == -999 :
# take random action
idx = np.random.choice(len(positions))
action = positions[idx]
# print("{} takes action {}".format(self.name, action))
return action
# append a hash state
def addState(self, state):
self.states.append(state)
# at the end of game, backpropagate and update states value
def feedReward(self, reward):
for st in reversed(self.states):
if self.states_value.get(st) is None:
self.states_value[st] = 0
self.states_value[st] += self.lr * (self.decay_gamma * reward - self.states_value[st])
reward = self.states_value[st]
def reset(self):
self.states = []
def savePolicy(self):
fw = open('policy_' + str(self.name), 'wb')
pickle.dump(self.states_value, fw)
fw.close()
def loadPolicy(self, file):
fr = open(file, 'rb')
self.states_value = pickle.load(fr)
fr.close()
class HumanPlayer:
def __init__(self, name):
self.name = name
def chooseAction(self, positions):
while True:
row = int(input("Input your action row:"))
col = int(input("Input your action col:"))
action = (row, col)
if action in positions:
return action
# append a hash state
def addState(self, state):
pass
# at the end of game, backpropagate and update states value
def feedReward(self, reward):
pass
def reset(self):
pass
if __name__ == "__main__":
# training
p1 = Player("p1")
p2 = Player("p2")
st = State(p1, p2)
print("training...")
st.play(100000)
p1.savePolicy()
# play with human
p1 = Player("computer", exp_rate=0)
p1.loadPolicy("policy_p1")
p2 = HumanPlayer("human")
st = State(p1, p2)
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
Nếu bạn thấy nội dung của bài viết thật sự hữu ích và bạn muốn đóng góp cho blog để có thêm nhiều bài viết chất lượng hơn nữa, các bạn có thể ủng hộ blog bằng một cốc trà hoặc một cốc cà phê nhỏ qua https://nhantien.momo.vn/7abl2tSivGa hoặc paypal.me/tungduypham. Sự ủng hộ của các bạn là nguồn động viên quý giá để chúng tôi có thêm động lực và chia sẻ nhiều điều mà chúng tôi tìm hiểu được đến với cộng đồng. Trân trọng cảm ơn.
