Reinforcement Learning và tictactoe

- Phạm Duy Tùng

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