OSS 겨울캠프 - Monte Carlo tree search를 배웠다

국민대학교 OSS겨울캠프에 이번에도 참가했다.

이번에는 저번보다 좀 더 고 난이도인 AlphaZero라는 프로젝트를 진행했다. 
원래 AlphaZero는 바둑 AI인데, 바둑은 캠프 기간 내에 하기에 무리라고 판단해서 오목 AI로 바꾸게 되었다. 
다른 좋은 특강들도 많았지만, 가장 메인은 AI 교육 시간이었다.
Monte Carlo tree search (MCTS)라는 학습 방식을 배웠는데 정말 정말 어려웠다. 
어려워서 이해가 안 되면 질문을 해야 되는데, 어디서부터 질문해야 될지 모르겠고 정말 막막했다. 
그래도 주변에 조교님들이 잘 리드해주신 덕분에 겨우 과제를 끝마친 것 같다. 
그리고 나만 어려운 게 아니라 모두가 어려워하는 것 같아서 극복할 수 있게 되었던 것 같다. 

import copy 
from connect5.types import Player, Point, Direction 
from connect5 import zobrist 
import numpy as np 

# 바둑판을 나타내는 클래스 
class Board: 
    # 초기화 메소드 
    def __init__(self, num_rows, num_cols): 
        self.num_rows = num_rows 
        self.num_cols = num_cols 
        self._grid = np.zeros((self.num_rows + 1, self.num_cols + 1), dtype=np.int) 
        self._hash = zobrist.EMPTY_BOARD 

    # 돌을 놓는 메소드 
    def place_stone(self, player, point): 
        assert self.is_on_grid(point) 
        assert self._grid[point.row, point.col] == 0 
        self._grid[point.row, point.col] = player 

    # 좌표가 바둑판 내에 존재하는지 확인하는 메소드 
    def is_on_grid(self, point): 
        return 1 <= point.row <= self.num_rows and \ 
            1 <= point.col <= self.num_cols 

    # 바둑판 내 위치에 있는 돌의 색깔(흑돌, 백돌, 빈돌)을 반환하는 메소드 
    def get(self, point): 
        stone_color = self._grid[point.row, point.col] 
        return stone_color 
     
    # 해시 값을 가져오는 메소드 
    def zobrist_hash(self): 
        return self._hash 

# 행동을 나타내는 클래스 
class Move: 
    # 초기화 메소드 
    def __init__(self, point=None): 
        assert (point is not None) 
        self.point = point 

    # 돌을 놓는 행동을 수행하는 메소드 
    @classmethod 
    def play(cls, point): 
        return Move(point=point) 

    # 행동 정보를 출력하는 메소드 
    def __str__(self): 
        return '(r %d, c %d)' % (self.point.row, self.point.col) 

# 게임 상태를 나타내는 클래스 
class GameState: 
    # 초기화 메소드 
    def __init__(self, board, next_player, previous, move): 
        self.board = board 
        self.next_player = next_player 
        self.previous_state = previous 
        if self.previous_state is None: 
            self.previous_states = frozenset() 
        else: 
            self.previous_states = frozenset(previous.previous_states | 
            {(previous.next_player, previous.board.zobrist_hash())}) 
        self.winner = None 

    # 돌을 놓는 행동을 적용하는 메소드 
    def apply_move(self, move): 
        next_board = copy.deepcopy(self.board) 
        next_board.place_stone(self.next_player, move.point) 
        return GameState(next_board, self.next_player.other, self, move) 

    # 새로운 게임을 만드는 메소드 
    @classmethod 
    def new_game(cls, board_size): 
        if isinstance(board_size, int): 
            board_size = (board_size, board_size) 
        board = Board(*board_size) 
        return GameState(board, Player.black, None, None) 

    # 유효한 행동인지 확인하는 메소드 
    def is_valid_move(self, move): 
        return self.board.get(move.point) == 0 

    # 샅은 색깔인 돌의 개수가 5개를 초과하는지 확인하는 메소드 
    def is_middle(self, r, c, stone_color, direction): 
        if direction is Direction.right and self.board.is_on_grid(Point(row=r, col=c-1)): 
            if self.board._grid[r, c - 1] == stone_color: 
                return False 
        if direction is Direction.down and self.board.is_on_grid(Point(row=r-1, col=c)): 
            if self.board._grid[r - 1, c] == stone_color: 
                return False 
        if direction is Direction.right_down and self.board.is_on_grid(Point(row=r-1, col=c-1)): 
            if self.board._grid[r - 1, c - 1] == stone_color: 
                return False 
        if direction is Direction.left_down and self.board.is_on_grid(Point(row=r-1, col=c+1)): 
            if self.board._grid[r - 1, c + 1] == stone_color: 
                return False 
        return True 

    # 오목인지를 확인하는 메소드 
    def is_connect5(self, r, c, stone_color, direction): 
        if not self.is_middle(r, c, stone_color, direction): 
            return False 
        stones = [] 
        stones.append(Point(r, c)) 
        d_row = r 
        d_col = c 
        if direction is Direction.right: 
            d_col += 1 
            while self.board.is_on_grid(Point(row=d_row, col=d_col)) and \ 
                self.board._grid[d_row, d_col] == stone_color: 
                stones.append(Point(row=d_row, col=d_col)) 
                d_col += 1 
        elif direction is Direction.down: 
            d_row += 1 
            while self.board.is_on_grid(Point(row=d_row, col=d_col)) and \ 
                self.board._grid[d_row, d_col] == stone_color: 
                stones.append(Point(row=d_row, col=d_col)) 
                d_row += 1 
        elif direction is Direction.right_down: 
            d_row += 1 
            d_col += 1 
            while self.board.is_on_grid(Point(row=d_row, col=d_col)) and \ 
                self.board._grid[d_row, d_col] == stone_color: 
                stones.append(Point(row=d_row, col=d_col)) 
                d_row += 1 
                d_col += 1               
        elif direction is Direction.left_down: 
            d_row += 1 
            d_col -= 1 
            while self.board.is_on_grid(Point(row=d_row, col=d_col)) and \ 
                self.board._grid[d_row, d_col] == stone_color: 
                stones.append(Point(row=d_row, col=d_col)) 
                d_row += 1 
                d_col -= 1 
        if len(stones) is 4: 
            return True 
        return False       

    # 게임이 끝났는지 확인하는 메소드 
    def is_over(self): 
        is_full = True 
        for r in range(1, self.board.num_rows + 1): 
            for c in range(1, self.board.num_cols + 1): 
                stone_color = self.board._grid[r, c] 
                if stone_color != 0: 
                    if self.board.is_on_grid(Point(row=r, col=c+1)) and \ 
                        stone_color == self.board._grid[r, c + 1]: 
                        if self.is_connect5(r, c, stone_color, Direction.right): 
                            self.winner = "Black" if stone_color == Player.black else "White" 
                            return True 
                    if self.board.is_on_grid(Point(row=r+1, col=c)) and \ 
                        stone_color == self.board._grid[r + 1, c]: 
                        if self.is_connect5(r, c, stone_color, Direction.down): 
                            self.winner = "Black" if stone_color == Player.black else "White" 
                            return True 
                    if self.board.is_on_grid(Point(row=r+1, col=c+1)) and \ 
                        stone_color == self.board._grid[r + 1, c + 1]: 
                        if self.is_connect5(r, c, stone_color, Direction.right_down): 
                            self.winner = "Black" if stone_color == Player.black else "White" 
                            return True 
                    if self.board.is_on_grid(Point(row=r+1, col=c-1)) and \ 
                        stone_color == self.board._grid[r + 1, c - 1]: 
                        if self.is_connect5(r, c, stone_color, Direction.left_down): 
                            self.winner = "Black" if stone_color == Player.black else "White" 
                            return True 
                else: 
                    is_full = False             
        if is_full: 
            self.winner = "Draw" 
            return True 
        else: 
            return False 
     
    # 유효한 행동 목록을 반환하는 메소드 
    def legal_moves(self): 
        moves = [] 
        for row in range(1, self.board.num_rows + 1): 
            for col in range(1, self.board.num_cols + 1): 
                move = Move.play(Point(row, col)) 
                if self.is_valid_move(move): 
                    moves.append(move) 
        return moves 

 

이런 코드를 작성하고 난 뒤 여러 가지 코드들을 덧붙이고 agent 학습을 바로 시작했다.
agent 학습은 Google cloud platform에서 무료 크레딧를 이용해 슈퍼컴퓨터로 진행했다.
우리가 수정해야 할 값은 이 정도 있었다.

LEARNING_RATE는 agent의 학습률로, 0과 1 사이의 값을 사용하며. 적절한 값을 찾아야 한다.
ROUNDS_PER_MOVE는 학습 데이터를 만들 때 한 수에 수행할 MCTS Simulation 수를 정한다. 이 값이 높을수록 좋은 데이터가 만들어지겠지만 agent의 학습 속도는 더 느려지게 된다.
PUCT, PUCT_INIT, PUCT_BASE 역시 적절한 값을 찾아야 하고, C(St)에 쓰이는 상수다. (알파고는 값이 5라고 한다)
SELFPLAY_WORKERS는 데이터를 만드는 작업자의 수를 결정한다. 코어의 수만큼 하는 게 좋지만 그러다가 터져버릴 수 있으니 나는 코어 수 -1로 설정했다.
START_TRAINING은 학습을 시작할 버퍼의 크기를 결정한다. 이 역시 크기가 클수록 많은 데이터를 가지고 학습할 수 있지만 속도가 느려진다.
EPOCH는 한번 agent가 학습할 때 몇 번 학습할지 결정하는 수다.
BATCH_SIZE는 한 번에 학습할 데이터의 수를 결정한다. 클수록 학습 속도가 느려지지만 정확도는 높아지게 된다.
LOAD_CHECKPOINT는 agent 학습을 중지하고 다시 시작할 때 불러올 모델의 숫자를 입력해서 불러올 수 있다.

위의 수들의 공통점을 살펴보면... 일단 모두 '적절한' 값을 찾는 게 중요하다는 거다. 만약 적절하지 않은 값을 넣었을 때는 모두 단점이 생긴다. 학습 속도가 느려진다거나.. 좋은 데이터가 만들어지지 않는다거나. 그렇지만 이렇게 안 좋은 값을 넣음에도 불구하고 만약 우리에게 무한한 시간이 있다고 가정하면 결국에 언젠가는 오목을 완벽하게 플레이하는 AI가 만들어질 수 있게 된다. 

그렇게 팀원들과 진지한(?) 회의를 하며 값 몇 개를 논리를 펼치며 설정했다. AI를 돌리기 위해서는 최소한 6시간은 학습을 돌려야 된다고 해서 값을 넣고 Google cloud platform에서 돌린 뒤 잠을 잤다.

우리가 자는 동안 AI는 학습 데이터를 1000개 넘게 생성하며 학습을 하고 있었다.

 

일어나서 봇의 학습 데이터를 저장하고 다른 팀들과 오목 토너먼트를 했는데. 결승을 무려 2번이나 진출했다!!

역시 저번 여름캠프 때나 지금이나 내가 학습시킨 agent가 이런 쾌거를 이룰 때 정말 알 수 없는 희열을 느끼는 것 같다.

OSS캠프에서 여름, 겨울 캠프때 AI를 배우며 AI에 대한 흥미가 치솟게 되었는데, 아직 집에서 할 엄두는 나지 않지만... 그래도 언젠가는 한번 도전해봐야 할 것 같다!