틱택토 강화학습 (Tik-Tak-Toe RL) - [정보과학융합탐구 - 3월 과제]

저번 백준 풀이 과제에 이어 이번에는 정보과학융합탐구 과제로 어떠한 프로젝트 하나를 정하고, 그 프로젝트를 수행해보는 과제가 나왔습니다. 따라서 오늘부터 정융탐 과제도 시작해보도록 하겠습니다. 정보와 관련된 주제이면 뭐든 상관없지만, 이왕이면 제가 흥미있어 하는 걸 하는 게 좋을 것 같다는 생각이 들었고, 여러 후보들 중 강화학습을 시도해보기로 하였습니다.

---

문제 인식

저는 어렸을 때부터 게임을 만드는 활동에 흥미가 있었고, 관심을 가지고 있었습니다. 그래서 실제로 엔트리나 스크래치 등의 프로그래밍 언어를 이용해 게임을 만들어보기도 했는데, 고등학교에 들어와서 AI 학습 방법 중 하나인 강화학습이란 것을 알게 되었고, 게임 AI를 만드는 활동에 큰 흥미를 느끼게 되어 이번 정융탐의 주제로 고르게 되었습니다. 강화학습을 이용해 만들 수 있는 게임 AI의 종류는 무궁무진한데, 저는 이 중 세계적으로 유명하기도 하고 여러 게임들 중 상대적으로 게임의 룰이나 강화학습의 난이도가 낮은 틱택토를 선정하였습니다.

실제 필자가 엔트리에서 만든 게임

 

일반적으로 강화학습을 할 때는 에이전트, 즉 AI 하나를 대상으로 강화학습을 진행하지만 저는 즉 2개의 에이전트를 강화학습하여 AI를 만들 것입니다. 따라서 결론적으로 제가 진행할 프로젝트의 주제는 "Multi Agent를 이용한 Tic-Tac-Toe 강화학습"입니다.

---

관련 조사 시행

강화학습에 대한 여러 자세한 이론들은 다음 글에서 다룰 예정이기에 이번에는 정말 간단한 요소들과 틱택토를 강화학습하는데에 필요한 여러 지식들에 대해서만 다뤄보겠습니다.

 

1. 용어 설명

(1) 강화학습 (Reinforcement Learning)

강화학습은 기계 학습의 한 영역으로, 어떤 환경 안에서 정의되어있는 에이전트(AI 등)가 현재의 상태를 인식해, 선택 가능한 행동들 중 보상을 최대화하는 행동을 선택하는 방법을 의미합니다. 강화학습은 복잡한 환경에서 최적의 해결책을 찾는 상황에 많이 이용되는데, 로봇, 자율주행 등에서 사용되며 특정 상황에서 최대 보상을 찾는 것이기 때문에 많은 게임들이 강화학습에 적합합니다. 바둑 AI 알파고 등이 강화학습을 이용한 가장 유명한 예입니다.

 

- 강화학습의 구성 요소

강화학습은 에이전트, 환경, 상태, 보상, 에피소드, 정책, 가치 함수 등의 요소로 구성됩니다. 

에이전트(Agent)	학습을 수행하는 대상
환경(Environment)	에이전트가 상호작용하는 대상
상태(State)	에이전트가 환경에 대해 파악할 수 있는 정보
보상(Reward)	에이전트가 취한 액션에 대한 결과 (양수, 음수 다 가능)
에피소드(Episode)	에이전트가 최종 상태에 도달하며 보상을 얻는 과정
정책(Policy)	에이전트가 상태를 입력받아 취해야 할 액션을 출력하는 함수
가치 함수(Value Fuction)	특정 상태에서 받을 수 있는 보상을 예측하는 함수

 

예를 들어 바둑에 강화학습을 한다고 하면, 바둑을 두는 AI는 Agent, 바둑판과 상대방과 뭐 기타 등등은 Environment, 바둑돌들의 위치는 State, AI가 어딘가에 바둑돌을 놨을 때 그게 미치는 영향은 Reward, 바둑을 두는 과정이 Episode, 어디에 바둑돌을 놓을지 결정하는 함수가 Policy, 어디에 바둑돌을 놨을 때 가장 이득이 될지를 알아내는 함수가 Value Function입니다.

 

- 강화학습 알고리즘의 종류

AI를 강화학습 시킬 때에는 알고리즘이 필요합니다. 이때 알고리즘은 Policy와 Value Function의 사용 여부로 크게 Value-Based과 Policy-Based로 나눌 수 있습니다.

 

만약 Value-Function이 완벽하다면 agent는 각 상황에서 가장 높은 value를 주는 행동을 택하기만 하면 되므로 policy가 자동으로 따라온다고 볼 수 있습니다. 따라서 이렇게 Value-Function만을 학습하고 policy는 암묵적으로만 갖게 강화학습하는 방식을 Value-Based 강화학습이라고 하고, 대표적으로 Q-Learning, SARSA, DQN 등이 있습니다.

 

반대로 Policy가 완벽하다면 value function은 policy를 만들기 위한 중간 과정일 뿐이므로 value function이 필요하지 않습니다. 따라서 이렇게 value-function 없이 policy만을 갖게 강화학습하는 방식을 Policy-Based 강화학습이라고 하고, 대표적으로 DDPG, A2C, A3C 등이 있습니다. 

 

Value-Based와 Policy-Based가 혼합되어있는 Actor-Critic 방식도 존재합니다. Actor-Critic에서 Actor는 policy을 학습하고, Critic은 value function을 학습합니다.

알고리즘들에 관한 자세한 내용은 다음 글에서 다룰 것입니다.

 

(2) 틱택토 (Tic-Tac-Toe)

틱택토는 두 명이 번갈아가며 O와 X를 3x3 판에 써서 같은 글자를 가로, 세로 혹은 대각선상에 놓이게 하는 놀이입니다. 이 글을 읽을 모두가 알 정도로 정말 유명한 게임이며, 선 4개와 O, X만 있으면 되기에 아주 간단하게 즐길 수 있는 놀이입니다. 이런 유명성과 간단함 때문에 강화학습을 비롯한 여러 게임 관련 프로젝트 등에 자주 쓰이고 있고, 저도 이런 이유들로 인해 틱택토를 강화학습의 대상으로 선정하였습니다.

---

문제 해결 방안 설계

이 프로젝트는 보통 일반적으로 강화학습 프로젝트를 진행되듯이 진행할 것입니다. 강화학습은 보통 '환경 설정 - 문제 정의 - 에이전트 생성 - 학습 진행 - 훈련 및 검증'의 단계로 진행되기에, 이 단계에 맞춰 진행해보겠습니다.

 

1. 환경 설정

먼저, 에이전트와 환경 간 인터페이스 등 에이전트가 운영될 환경을 설정해야 합니다. 제 경우에는 틱택토 게임판, 틱택토의 기본적인 룰 등이 환경에 들어가고, 이를 먼저 구현하는 것이 중요합니다. 파이썬을 이용하여 환경을 설정하는 것이 가능하기 때문에 저는 파이썬으로 환경 설정을 할 것입니다.

 

2. 문제 정의

다음으로, 문제를 정의해야 합니다. 에이전트, 상태, 행동 등을 정의하고 특히 보상을 어떻게 줄지를 정해야 합니다. 문제를 어떻게 정의하는지에 따라 모델의 성능이 달라지기 때문에 이런 점은 신중히 고민하고 생각해보아야 합니다. 다음 글에서 차차 정해보도록 하겠습니다.

 

3. 에이전트 생성

이후 에이전트를 생성해야 합니다. 에이전트를 생성할 때는 두 가지를 같이 해야하는데, 먼저 정책을 나타낼 방법을 선택해야 하고, 적절한 훈련 알고리즘을 선택해야 합니다. 알고리즘은 일반적으로 Single agent의 경우에는 Q-Learning을 주로 사용하지만 제 경우에는 Multi agent를 이용하기 때문에 Q-Learning이 효율적이라고 단정지을 수 없어 Actor-Critic 등 여러 다른 알고리즘에 대해서도 탐구해볼 생각입니다.

 

4. 훈련 및 검증

마지막으로 AI를 훈련시키고, 검증하여 성능을 향상시켜야 합니다. 훈련을 진행하면 에이전트가 환경과 상호작용하며 정택에 따라 행동을 선택하고, 선택에 따른 보상을 받으며 이 보상을 최대화 할 수 있는 방안으로 정책이 개선되어 갑니다. 또 훈련 옵션(중지 기준 등)을 설정하고 정책을 조정하며 훈련을 진행해야 합니다. 이후, 알고리즘의 수정, 하이퍼파라미터의 조정, 보상 구조의 개선 등을 통해서 성능을 향상시킬 수 있습니다.

제 경우에는 Multi agent를 이용할 것이기 때문에 agent 둘이 서로 아무 곳에나 틱택토를 두는 것을 계속해서 반복시키다가 AI의 성능이 자동으로 늘어날 것으로 생각하고 있습니다.

 

+ 추가 연구

원래는 틱택토보다 복잡한 오목 강화학습을 시켜볼 생각이었습니다. 오목은 틱택토보다 게임판도 넓고, 경우의 수도 훨씬 많기 때문에 강화학습의 진가가 훨씬 잘 드러날 것으로 예상되며, 단순한 알고리즘으로 구현 가능한 틱택토 강화학습보다 재밌을 것 같았기 때문입니다. 그러나, 경우의 수가 너무 많아 학습이 오래 걸리고, 이제 강화학습을 시작한 제 실력으로 할 수 있을지에 대한 걱정이 있어 우선은 추가 연구로 남겨두기로 하였습니다.

---

기대효과

먼저, 이번 연구를 통해 강화학습의 기본 원리와 주요 알고리즘들에 대해 깊이 탐구해보며 다양한 지식을 얻을 수 있을 것입니다. 또 Single agent로 강화학습을 진행하는 것과 Multi agent 시스템에서 강화학습을 적용하는 방식의 차이점에 대해 탐구하고, 어느 방식이 더 성능이 좋은지에 대해서도 탐구해볼 수 있을 것으로 기대됩니다. 이러한 Multi agen 시스템에서의 학습 과정을 통해, Agent 간의 협력과 경쟁이 어떻게 학습 과정에 영향을 미치는지에 대해서도 이해할 수 있을 것입니다.