Dạy Máy Chơi Tictactoe Bằng Deep Learning
Vào ngày 5 tháng 12 năm 2017, Deepmind đã giới thiệu Alphazero với thế giới, một chương trình đánh cờ vua đã đánh bại stockfish chỉ với việc tự đánh cờ với chính nó trong vòng 4 giờ. Ấn tượng với Alphazero nên mình đã viết một AI chơi tictactoe đơn giản dựa trên Deep Q-Learning và nay mình muốn được chia sẻ với các bạn. Trong bài viết này mình sẽ đề cập đến Markov decision process, Q-Learning, Deep Q-Learning và ứng dụng Deep Q-learning vào tictactoe.
1. Markov Decision Process là gì? Bài toán với MDP
Markov Decision Process (MDP) cung cấp một nền tảng toán học cho việc mô hình hóa việc ra quyết định trong các tình huống mà kết quả là một phần ngẫu nhiên và một phần dưới sự điều khiển của một người ra quyết định. Để một bài toán đưa về MDP (markov decision process) thì các state trong bài toán đó phải thỏa mãn markov property: mỗi state chỉ phụ thuộc vào state trước nó. Từ state s chuyển sang state s’ sẽ có xác xuất chuyển đổi được định nghĩa bằng công thức sau.
Mô tả bài toán tictactoe dưới dạng MDP.
Agent: Agent có thể là một chủ thể tương tác với environment thông qua việc quan sát và quyết định hành động dựa trên quan sát đó. Như trong tictactoe thì agent ở đây chính là player. Player có nhiệm vụ là chiến thắng ván đấu, bằng cách xử dụng ký hiệu 'X' và 'O' 2 player thay phiên nhau điền vào những ô còn trống, bên nào điền được 3 ô liên tiếp sẽ là người chiến thắng.
State: Sau mỗi action được agent đưa ra thì environment sẽ trả về 1 state để agent quan sát và đưa ra action tiếp theo. Như trong tictactoe thì mình sẽ biểu diễn state là 1 array có độ dài bằng 9 tương ứng với 9 ô trong bảng 3x3. Vì máy không thể hiểu được ký tự 'X' hoặc 'O' thế nên nên ta quy định ô trống sẽ có giá trị là 0, ô được player X đánh có giá trị là 1 và O là -1.
Action: Mỗi ô trong bàn cờ sẽ tương ứng với 1 action đánh số từ 0 đến 8. với những ô đã được đánh thì action đó coi như không hợp lệ và được bỏ qua.
Reward: Với mỗi action agent đưa ra thì environment sẽ trả về một reward. Ta có thể xem reward là cách mà environment đánh giá mức độ chính xác của agent khi dưa ra action đó, trong xuốt quá trình tương tác với environment thì mục tiêu của agent sẽ là maximum total reward. Trong tictactoe, reward sẽ là +1 khi agent chọn action mà tại đó game kết thúc và agent chiến thắng, -1 khi thua và còn lại reward là 0.
Để agent chọn ra được action thì ta cần có action-value function ký hiệu là qπ(s, a). Action-value function cho biết total reward khi chọn action a tại state s.
γ: discount factor , giá trị này đặc trưng cho độ quan trọng của reward trong tương lai , giá trị càng nhỏ thì càng ít quan trọng.
Vì mục tiêu là agent là maximum total reward thế nên việc còn lại là kiếm ra action-value có giá trị lớn nhất.
Quay lại tictactoe, giả sử hiện tại ta có state.
Lượt kế tiếp là của player O, với từng action trong state đưa qua action-value function thì ta được các value như sau.
Bỏ qua những ô cờ đã được đánh, thấy rằng action tại ô 4 là có giá trị lớn nhất vậy nên action agent sẽ chọn là 4. Ở thực tế thì nước đi này là tốt nên ta có thể nói policy ở state này là tối ưu.
Như vậy là ta đã đưa bài toán về MDP, vậy thì làm sao mà ta có thể tạo ra được action-value function?
Ta có thể tạo ra được action-value function bằng cách giải phương trình bellman tuy nhiên với tictactoe thì số lượng state là quá lớn để tính toán vậy nên thuật toán Q-learning sẽ giúp ta làm việc này.
2. Q-learning là gì?
Q-learning là một model-free, bằng cách lặp đi lặp lại các action và nhận được reward Q-learning có thể tạo ta action-value function. Action-value function trong Q-learning là một look-up table gọi là Q-table được khởi tạo với giá trị bất kỳ.
Với mỗi step trong episode thì agent sẽ chọn ra action bằng epsilon-greedy. Epsilon-greedy là thuật toán lựa chọn action dựa trên giá trị epsilon (0 ≤ epsilon ≤1), đầu tiên thuật toán random một số p(0 ≤ p < 1) nếu p ≤ epsilon thì lựa chọn random action và ngược lại chọn greedy action có value lớn nhất. Giá trị epsilon dùng để cân bằng giữa exploration và exploitation nếu agent chỉ chọn greedy action thì có khả năng nó sẽ bỏ qua các action khác có phần thưởng lớn hơn, còn nếu chỉ toàn chọn random action thì Q-table sẽ hội tụ chậm. Vây trên thực tế thì người ta sẽ khởi tạo epsilon là một còn số lớn như 0.99 chẳng hạn rồi giảm dần giá trị này về một số nhỏ hơn vd như 0.1.
Tiếp đến action được đưa vào environment, environment trả về state kế tiếp và reward, Q-table được update dựa trên công thức
α là learning rate (0 < α ≤ 1).
3. Deep Q-learning
Hạn chế của Q-learning đó là nếu state quá lớn thì sẽ tốn rất nhiều dung lượng để lưu trữ Q-table và làm chậm thời gian học vì trong quá trình học Q-table được truy xuất liên tục vậy nên Deep Q-learning(DQN) ra đời. DQN thừa hưởng toàn bộ từ Q-learning tuy nhiên Q-table được thay thế bằng deep neural network của deep learning (Deep neural network + Q-learning = Deep Q-learning). Để tính action-value ta chỉ việc đưa state vào là input thì neural network lập tức đưa ra ouput là các giá trị action-value
Tuy vậy để tránh tình trạng overfit thì ở đây ta sẽ sử dụng 2 neural network, network chính gọi là action-value network và một network phụ gọi là target action-value network. Một vấn đề nữa với DQN đó chính là catastrophic forgetting, để giảm bớt vấn đề này thì ta sẽ sử dụng 1 lifehack đó là experience replay. Với mỗi step thì ta sẽ có 1 tuple (s, a, r, s’, done) được lưu vào memory với done là flag cho ta biết state s’ có phải terminal state hay không, sau đó sample 1 mini batch và đưa vào train neural network.
Update function cũng khác đôi chút so với Q-learning.
Ta cùng nhìn lại toàn bộ quy trình của thuật toán.
4. Áp dụng DQN vào tictactoe
Giờ bắt tay vô code thôi.
đầu tiên xây dựng tictactoe environment
class Tictactoe_v0:
def __init__(self):
self.board = [0] * 9
self.wining_position = [[0, 1, 2], [3, 4, 5], [6, 7, 8],
[0, 3, 6], [1, 4, 7], [2, 5, 8],
[0, 4, 8], [6, 4, 2]]
self.current_turn = 1
self.player_mark = 1
def reset(self, is_human_first):
self.board = [0] * 9
self.current_turn = 1
self.player_mark = 1 if is_human_first else -1
if not is_human_first:
self.env_act()
return self.board.copy()
def check_win(self):
for pst in self.wining_position:
if str(self.board[pst[0]]) + str(self.board[pst[1]]) + str(self.board[pst[2]]) in ['111', '-1-1-1']:
if self.current_turn == self.player_mark:
return 1, True
return -1, True
if 0 not in self.board:
return 0, True
return 0, False
def env_act(self):
action = random.choice([i for i in range(len(self.board)) if self.board[i] == 0])
for pst in self.wining_position:
com = str(self.board[pst[0]]) + str(self.board[pst[1]]) + str(self.board[pst[2]])
if com.replace('0', '') == str(self.current_turn) * 2:
if self.board[pst[0]] == 0:
action = pst[0]
elif self.board[pst[1]] == 0:
action = pst[1]
else:
action = pst[2]
if self.board[action] != 0:
raise Exception('Invalid action')
self.board[action] = self.current_turn
reward, done = self.check_win()
self.current_turn = self.current_turn * -1
return reward, done
def step(self, action):
if self.board[action] != 0:
raise Exception('Invalid action')
self.board[action] = self.current_turn
reward, done = self.check_win()
self.current_turn = self.current_turn * -1
if done:
return self.board.copy(), reward, done, None
reward, done = self.env_act()
return self.board.copy(), reward, done, NoneImplement epsilon-greedy
class EpsilonGreedy:
def __init__(self, epsilon):
self.epsilon = epsilon
def perform(self, q_value, action_space: list = None):
prob = np.random.sample() # get probability of taking random action
if prob <= self.epsilon: # take random action
if action_space is None: # all action are available
return np.random.randint(len(q_value))
return np.random.choice(action_space)
else: # take greedy action
if action_space is None:
return np.argmax(q_value)
return max([[q_value[a], a] for a in action_space], key=lambda x: x[0])[1]
def decay(self, decay_value, lower_bound):
"""
Adjust the epsilon value by the formula: epsilon = max(decayValue * epsilon, lowerBound).
:param decay_value: Value ratio adjustment (0, 1).
:param lower_bound: Minimum epsilon value.
:return: None
"""
self.epsilon = max(self.epsilon * decay_value, lower_bound)Implement experience replay
class ExperienceReplay:
def __init__(self, e_max: int):
if e_max <= 0:
raise ValueError('Invalid value for memory size')
self.e_max = e_max
self.memory = list()
self.index = 0
def add_experience(self, sample: list):
if len(sample) != 5:
raise Exception('Invalid sample')
if len(self.memory) < self.e_max:
self.memory.append(sample)
else:
self.memory[self.index] = sample
self.index = (self.index + 1) % self.e_max
def sample_experience(self, sample_size: int, cer_mode: bool):
samples = random.sample(self.memory, sample_size)
if cer_mode:
samples[-1] = self.memory[self.index - 1]
# state_samples, action_samples, reward_samples, next_state_samples, done_samples
s_batch, a_batch, r_batch, ns_batch, done_batch = map(np.array, zip(*samples))
return s_batch, a_batch, r_batch, ns_batch, done_batch
def get_size(self):
return len(self.memory)Implement DQN
class DQN(BaseModel):
def __init__(self, discount_factor: float, epsilon: float, e_min: int, e_max: int):
super().__init__(discount_factor, epsilon, e_min, e_max)
self.gamma = discount_factor
self.epsilon_greedy = EpsilonGreedy(epsilon)
self.e_min = e_min
self.exp_replay = ExperienceReplay(e_max)
self.training_network = Sequential()
self.target_network = Sequential()
self.cache = list()
def observe(self, state, action_space: list = None):
q_value = self.training_network.predict(np.array([state])).ravel()
if action_space is not None:
return max([[q_value[a], a] for a in action_space], key=lambda x: x[0])[1]
return np.argmax(q_value)
def observe_on_training(self, state, action_space: list = None) -> int:
q_value = self.training_network.predict(np.array([state])).ravel()
action = self.epsilon_greedy.perform(q_value, action_space)
self.cache.extend([state, action])
return action
def take_reward(self, reward, next_state, done):
self.cache.extend([reward, next_state, done])
self.exp_replay.add_experience(self.cache.copy())
self.cache.clear()
def train_network(self, sample_size: int, batch_size: int, epochs: int, verbose: int = 2, cer_mode: bool = False):
if self.exp_replay.get_size() >= self.e_min:
# state_samples, action_samples, reward_samples, next_state_samples, done_samples
s_batch, a_batch, r_batch, ns_batch, done_batch = self.exp_replay.sample_experience(sample_size, cer_mode)
states, q_values = self.replay(s_batch, a_batch, r_batch, ns_batch, done_batch)
history = self.training_network.fit(states, q_values, epochs=epochs, batch_size=batch_size, verbose=verbose)
return history.history['loss']
def replay(self, states, actions, rewards, next_states, terminals):
q_values = self.target_network.predict(np.array(states)) # get q value at state t by target network
nq_values = self.target_network.predict(np.array(next_states)) # get q value at state t+1 by target network
for i in range(len(states)):
a = actions[i]
done = terminals[i]
r = rewards[i]
if done:
q_values[i][a] = r
else:
q_values[i][a] = r + self.gamma * np.max(nq_values[i])
return states, q_values
def update_target_network(self):
self.target_network.set_weights(self.training_network.get_weights())xây dựng DQN model, mình sử dụng keras để build neural nework.
env = Tictactoe_v0()
agent = DQN(0.7, 1, 4096, 1048576)
op1 = optimizers.RMSprop(learning_rate=0.00025)
agent.training_network.add(Dense(128, activation='relu', input_shape=(9,)))
agent.training_network.add(Dense(128, activation='relu'))
agent.training_network.add(Dense(9, activation='linear'))
agent.training_network.compile(optimizer=op1, loss=losses.mean_squared_error)
op2 = optimizers.RMSprop(learning_rate=0.00025)
agent.target_network.add(Dense(128, activation='relu', input_shape=(9,)))
agent.target_network.add(Dense(128, activation='relu'))
agent.target_network.add(Dense(9, activation='linear'))
agent.target_network.compile(optimizer=op2, loss=losses.mean_squared_error)
agent.update_target_network()Ở đây thì mình chỉ training cho AI đánh trước.
Sau quá trình training thì thực hiện quá trình đánh giá model, mình cho agent đánh với random player và minimax player, mỗi round vậy đánh 1000 trận và nước đi đầu tiên được chọn random, đây là kết quả.
VS MINIMAX PLAYER
| Training times | Wins | Draws | Loses |
| 50000 | 0 | 1000 | 0 |
VS RANDOM PLAYER
| Training times | Wins | Draws | Loses |
| 50000 | 809 | 190 | 1 |
Source code
Khi đánh với Minimax player thì AI đánh hoàn hảo tuy nhiên khi đối thủ là random player thì AI lại mắc lỗi, mình train thêm 100000 episodes nữa kết quả cũng không khả quan hơn nên mình dừng lại. Các bạn có thể xem toàn bộ code của mình tại đây . Đây là toàn bộ kiến thức mà mình tìm hiểu được khi làm project này, mong các bạn góp ý. Có thể kết quả chưa được như mong đợi nhưng mình hy vọng qua bài viết này các bạn có thể tự train cho mình một AI đánh tictactoe.
Cám ơn các bạn đã theo dõi bài viết.
Reference
introduction-deep-q-learning-python
Catastrophic Interference in Connectionist Networks: The Sequential Learning Problem
