딥러닝 파이토치 강좌, 몬테카를로 트리 검색을 적용한 틱택토 게임 구현

본 글에서는 딥러닝과 파이토치를 활용하여 몬테카를로 트리 검색(MCTS) 알고리즘을 적용한 틱택토 게임을 구현하는 과정을 설명합니다. 우리는 기본적으로 MCTS가 어떻게 작동하는지, 그리고 이를 통해 어떻게 AI가 틱택토 게임을 플레이할 수 있는지를 이해할 것입니다.

틱택토 게임 개요

틱택토(Tic-Tac-Toe)는 3×3 정사각형 격자에서 두 플레이어가 번갈아 가며 X 또는 O를 놓고, 가로, 세로 또는 대각선으로 3개의 연속된 말을 놓으면 승리하는 게임입니다.

1단계: 환경 설정

이 튜토리얼을 진행하기 위해서는 필요한 패키지를 설치해야 합니다. 다음은 필요한 주요 라이브러리입니다.

pip install torch numpy matplotlib

2단계: 게임 환경 구현

먼저 틱택토 게임 환경을 구현합니다. 게임의 규칙을 정의하고, 상태를 나타내는 클래스를 만들어야 합니다.

import numpy as np

class TicTacToe:
    def __init__(self):
        self.board = np.zeros((3, 3), dtype=int)  # 0: 빈칸, 1: X, -1: O
        self.current_player = 1  # 1: X의 차례, -1: O의 차례

    def reset(self):
        self.board = np.zeros((3, 3), dtype=int)
        self.current_player = 1

    def make_move(self, row, col):
        if self.board[row, col] == 0:
            self.board[row, col] = self.current_player
            self.current_player *= -1

    def check_winner(self):
        for player in [1, -1]:
            for row in range(3):
                if np.all(self.board[row, :] == player):  # 행 체크
                    return player
            for col in range(3):
                if np.all(self.board[:, col] == player):  # 열 체크
                    return player
            if np.all(np.diag(self.board) == player) or np.all(np.diag(np.fliplr(self.board)) == player):
                return player
        return None if np.any(self.board == 0) else 0  # 게임이 진행 중인 경우
        
    def display(self):
        symbols = {1: 'X', -1: 'O', 0: ' '}
        for row in self.board:
            print("|".join(symbols[x] for x in row))
            print("-" * 5)
        print("\n")

# 게임 테스트
game = TicTacToe()
game.make_move(0, 0)
game.display()
game.make_move(1, 1)
game.display()
        

3단계: 몬테카를로 트리 검색(MCTS) 알고리즘

MCTS는 불확실한 상황에서 의사결정 문제를 해결하기 위한 방법입니다. 기본적으로 이 알고리즘은 다음 네 가지 단계로 구성됩니다:

1. 선택(Selection): 현재 트리에서 노드를 선택합니다.
2. 확장(Expansion): 선택된 노드에서 가능한 행동을 확장합니다.
3. 시뮬레이션(Simulation): 확장된 노드에서 게임을 플레이하여 결과를 얻습니다.
4. 백업(Backpropagation): 결과를 통해 부모 노드에 정보를 업데이트합니다.

MCTS 클래스 구현

import random
from collections import defaultdict

class MCTSNode:
    def __init__(self, state, parent=None):
        self.state = state  # 현재 게임 상태
        self.parent = parent
        self.children = []  # 자식 노드
        self.wins = 0  # 승리 횟수
        self.visits = 0  # 방문 횟수

    def ucb1(self):
        if self.visits == 0:
            return float('inf')  # 방문한 적 없는 노드는 우선 선택하도록 함
        return self.wins / self.visits + np.sqrt(2 * np.log(self.parent.visits) / self.visits)

class MCTS:
    def __init__(self, iterations):
        self.iterations = iterations

    def search(self, game):
        root = MCTSNode(state=game)

        for _ in range(self.iterations):
            node = self.select(root)
            winner = self.simulate(node.state)
            self.backpropagate(node, winner)

        return max(root.children, key=lambda child: child.visits).state

    def select(self, node):
        while node.children:
            node = max(node.children, key=lambda child: child.ucb1())
        if node.visits > 0:
            for action in self.get_valid_moves(node.state):
                child_state = node.state.copy()
                child_state.make_move(action[0], action[1])
                child_node = MCTSNode(state=child_state, parent=node)
                node.children.append(child_node)
        return random.choice(node.children) if node.children else node

    def simulate(self, state):
        current_player = state.current_player
        while True:
            winner = state.check_winner()
            if winner is not None:
                return winner
            valid_moves = self.get_valid_moves(state)
            move = random.choice(valid_moves)
            state.make_move(move[0], move[1])

    def backpropagate(self, node, winner):
        while node is not None:
            node.visits += 1
            if winner == 1:  # X의 승리
                node.wins += 1
            node = node.parent

    def get_valid_moves(self, state):
        return [(row, col) for row in range(3) for col in range(3) if state.board[row, col] == 0]

# MCTS 사용 사례
mcts = MCTS(iterations=1000)
move = mcts.search(game)
print("AI의 선택:", move)
        

4단계: AI와 사용자 간의 게임 구현

이제 완성된 MCTS를 사용하여 사용자와 AI 간의 게임을 구현해 보겠습니다.

def play_game():
    game = TicTacToe()
    while True:
        game.display()
        if game.current_player == 1:  # 사용자 차례
            row, col = map(int, input("행과 열 번호를 입력하세요 (0, 1 또는 2): ").split())
            game.make_move(row, col)
        else:  # AI 차례
            print("AI가 선택하는 중...")
            move = mcts.search(game)
            game.make_move(move[0], move[1])
            print(f"AI가 선택한 위치: {move}")

        winner = game.check_winner()
        if winner is not None:
            game.display()
            if winner == 1:
                print("축하합니다! 당신이 이겼습니다!")
            elif winner == -1:
                print("AI가 이겼습니다!")
            else:
                print("무승부입니다!")
            break

play_game()
        

결론

이번 강좌에서는 딥러닝과 파이토치의 기본 가이드라인을 살펴보았습니다. 몬테카를로 트리 검색을 활용하여 간단한 틱택토 AI를 구현하는 과정은 기술적으로 도전이 될 수 있지만, 결과적으로는 매우 흥미로운 경험이었습니다. 앞으로 더 나아가 다양한 알고리즘과 기술을 활용하여 보다 완벽한 AI를 개발할 수 있기를 기대합니다.