안녕하세요, 파란커피 팀 입니다!
파란커피 팀은 Stanford cs234 강의를 공부하며, ‘수식없는 한글 강화학습 위키’를 제작했습니다.
이번 기수에서는 위키 제작과 동시에, ‘강화학습을 이용한 체스 게임 학습시키기’ 프로젝트를 진행했습니다.
발표가 끝난 후 점심식사&데모&네트워킹 행사 시간에 파란커피 팀이 학습시킨 모델과 체스 게임을 직접 해볼 수 있습니다!
강화학습
강화학습이란?
불확실성 하에서, 최종적으로 최대의 보상을 받을 수 있도록 연속적으로 이어지는 일련의 결정들을 내리도록 학습시키는 것
•
Sequence of Decisions : 하나만 나오고 끝나는 결정이 아닌 계속 이어지는 일련의 결정들
•
Good Decisions : 정확도, 최대한의 보상을 받을 수 있는 최적의 결정
•
the learning : 좋은 결정을 내리기 위해 agent를 학습시킴
강화학습의 핵심
•
최적화
◦
최적화는 모든 모델에서 필수
•
지연된 결과
◦
현재의 결정이 미래에도 영향을 미칠 수 있음 (ex> 게임에서 지금 한 선택이 나중의 승패를 결정함)
◦
challenges : 지금 한 결정에 대해 즉각적인 피드백이 보장되지 않음 → 과거에 내린 결정과 미래에 받을 보상에 대한 관계를 일반화하기 힘들다 ( 특히 머신러닝과 다른 점)
특히 머신러닝과 다른 점)•
탐색
◦
이미 입력-결과가 나온 데이터로 학습하는 것이 아니라, agent가 탐색한 데이터로만 학습
◦
agent가 하는 결정들에 따라 학습하는 내용이 달라짐
•
일반화
◦
이전에 학습하지 않은 상황에 대해서도 지금까지 학습한 것을 바탕으로 문제를 풀어갈 수 있는 능력
◦
모든 action을 프로그래밍 하기엔 양이 너무 방대함 → 일반화하면 처음 보는 상황에서도 agent는 문제를 풀어갈 수 있다
다른 인공지능 학습법과 비교했을 때, 왜 강화학습인가?
•
AI planning : 규칙이 이미 적용된 모델
◦
최적화, 지연된 결과, 일반화는 해당하지만 탐색은 해당하지 않음
◦
일련의 결정들을 결정하는 모델이지만, 규칙이 이미 적용되어 있어 현재의 결정이 미래에 어떤 영향을 미치는지 알고 있다
•
Supervised Machine Learning : 주어진 경험을 통해 학습하는데 result O인 data 이용
◦
최적화, 일반화는 해당하지만 지연된 결과, 탐색은 해당하지 않음
◦
입력-결과가 이미 나온 경험 데이터를 통해 학습
◦
agent가 스스로 경험하며 학습하는 것이 아닌, 이미 경험한 데이터를 통해 학습
•
Unsupervised Machine Learning : 주어진 경험을 통해 학습하는데 result X인 data 이용
◦
최적화, 일반화는 해당하지만 지연된 결과, 탐색은 해당하지 않음
◦
agent가 스스로 경험하며 학습하는 것이 아닌, 이미 경험한 데이터를 통해 학습하나 행동에 대한 결과가 없는 데이터를 사용
•
Imitation Learning
◦
최적화, 지연된 결과, 일반화는 해당하지만 탐색은 해당하지 않음
◦
agent가 스스로 경험하며 학습하는 것이 아닌, 이미 경험한 데이터를 통해 학습
◦
다른 객체에 대한 행동을 따라 학습하기 때문에, 모방해보지 않은 새로운 상황을 마주치면 해결이 불가능하다
강화학습 용어 정리
Model
•
agent가 어떤 action을 취하느냐에 따라 world가 어떻게 바뀔지에 대한 예측 결과를 출력하는 함수
•
Transaction / Dynamics model : agent의 다음 state를 예측
Reward model : 즉각적인 보상을 예측
Policy
•
state를 입력받았을 때 agent가 action을 어떻게 선택할 지 결정하는 함수
•
Deterministic Policy : 입력된 state에 따른 action 출력값이 하나
Stochastic Policy : 입력된 state에 따른 가능한 action 별 확률을 출력
Value Function
•
특정 policy에 따른 미래의 보상의 총합을 예상하는 함수
•
즉각적인 보상과 미래의 보상 각각에 얼마나 비중을 둘 것인지 결정하는 함수
•
value가 높을수록 더 큰 보상을 얻을 수 있으며, 이를 좋은 policy라 한다
Types of RL Agents
•
Model Based Agent
◦
model이 존재
◦
이 model이 policy function이나 value function을 갖고 있을 수도, 아닐 수도 있음
◦
즉 명시된 policy function이나 value function이 없음
•
Model - free Agent
◦
model이 없음
◦
명시된 policy function이나 value function이 존재
이론적 배경
몬테카를로 방법
•
한 에피소드가 끝날 때마다 얻은 reward들로 표본 reward를 만들고, 만들어진 표본 reward의 평균값을 기반으로 강화학습 문제를 푸는 방법
•
어떤 state 이후 관측되는 모든 reward들에 대해 평균을 계산
•
한 에피소드가 완전히 완료된 후에만 그 state에 대한 vlaue의 추정값이나 policy를 update할 수 있음
◦
state를 거친 이후 발생하는 reward를 알 수 있을 떄까지 기다렸다가, 정확한 reward를 알게 되면 그 reward를 이용하여 해당 state의 value 추정값을 갱신
◦
추정값의 증가량은 결정하기 위해 한 에피소드가 완전히 끝날 때까지 기다려야 함
•
학습에 사용할 데이터로 오직 경험(World와 model의 상호작용으로부터 발생한 모든 state, action, reward의 표본을 나열한 것) 만을 필요로 함
•
몬테카를로 갱신의 목표 : 한 state가 끝난 이후의 추정값
동적 프로그래밍 방법
•
World가 완벽하게 주어졌을 때 최적의 정책을 계산하기 위해 사용되는 알고리즘
•
model이 있는 world와 model, policy를 모두 완벽하게 갖춰야 함
•
정책 평가 → 정책 향상 → 정책/가치 반복 의 세 단계를 거쳐 policy를 update 함
•
특정 state에서의 reward 기댓값을 나타내는 가치 함수를 활용
시간차 학습
•
시간차 학습 = 몬테카를로 방법 + 동적 프로그래밍 방법
•
구체적인 환경에 대한 정확한 모델이 없어도 가공하지 않은 state, action, reward들로부터 직접 학습이 가능
•
한 state 내의 시각 t+1에서 즉각적으로 목표를 설정하고, 시각 t까지 관측된 reward와 추정값을 이용해 update 진행
◦
한 에피소드가 끝날 때 까지 기다리지 않고 부분적으로 끝난 학습에서도 value에 대한 추정값을 갱신할 수 있음
◦
추정값의 증가량을 결정하기 위해 다음 시간 단계가 끝날 떄 까지만 기다리면 됨
•
시간차 학습 갱신의 목표 : 시각 t까지 관측된 reward와 추정값
Q-learning
•
주어진 상태(state)에서 agent가 어떠한 행동(action)을 취했을 떄 받을 수 있는 보상(reward)의 기댓값을 예측하는 함수를 이용하여 최선의 정책(policy)를 학습하는 강화학습 기법
•
state를 거치며 state-action쌍 별 value 값을 저장한 Q-table을 update 하며 최선의 정책을 찾음
프로젝트
프로젝트 배경
•
그동안 공부한 강화학습을 적용해보기 위한 프로젝트 진행
•
강화학습 프로젝트 중 가장 접근성이 좋고 대표적인 분야는 게임
⇒ 체스 게임을 강화학습으로 학습시켜보자!
•
모든 말을 사용하는 기본 체스 게임은 이미 다양한 프로젝트들이 진행된 바 있음
•
모든 말과 판을 다 사용하면 state가 너무 많아져 프로젝트 볼륨이 너무 커짐
⇒ 4x4 판에서 각 팀이 폰 4개씩만 사용하는 게임으로 만들어보자!
프로젝트 진행
1. 선행 연구 조사 - AlphaGo Zero
•
AlphaGo Zero 방식이란?
1.
컴퓨터가 스스로 플레이하며 모든 동작들을 기록, 말의 모든 이동들을 기록하여 주어진 체스 페이스가 승리인지, 패배인지 판단하는 방법을 학습
2.
1의 신경망을 복제하고, 이전 state에서 얻었던 데이터 세트로 복제된 신경망을 훈련시킴
3.
1의 신경망과 2에서 복제된 신경망끼리 게임 플레이
4.
둘 중 패배한 신경망은 버리고, 승리한 신경망을 이용하여 2-3단계를 반복
5.
1-4단계 반복
•
Code review
◦
agent
api_chess.py에서 게임 상태를 관찰하기 위해 파이프에서 수신하고 정책 및 값 네트워크에서 예측을 반환하는 프로세스를 정의
model_chess.py에서 주어진 관찰에서 정책 및 값 예측을 수행하기 위한 실제 모델을 정의, 신경망 정의
player_chess.py에서 예측과 판단을 실행하는 것 부터 게임 플레이, 신경망 선택과 과정 반복의 기능을 구현하여 AlphaGo Zero 방식을 구현함
◦
env
chess_env.py 로 체스 환경을 표현하고 작동하기 위한 기능을 캡슐화 함
◦
lib
실행에 필요한 라이브러리 모음, 가장 먼저 설치하고 시작해야 함
◦
play_game
uci.py에서 사람과 Alpha-Zero 방식을 통해 얻은 가장 좋은 모델이 실제로 게임을 해 볼 수 있게 함
◦
worker
evaluate.py 에서 대결한 두 모델 중 가장 좋은 모델이 무엇인지 평가하고 더 나은 모델을 추출해냄
optimize.py에서 이전 state에서 학습하며 얻은 데이터로 새로 학습을 진행함
self_play.py에서 agnet가 스스로 게임을 플레이 하며 데이터를 축적하고, 학습을 진행함
•
시사점
◦
이전 신경망을 복제하여 이전 플레이에서 얻은 데이터로 학습을 시킨 새로운 신경망과 이전 플레이에서 승리한 신경망이 대결하는 방식을 self-play라 하는데, 이 방식을 사용하면 과적합 되는 문제가 있음 → AlphaGo Zero 방식을 사용한다면 이 문제를 해결해야 함. 학습을 멈출 적절한 선이 어디까지인지?
◦
AlphaGo Zero 방식을 사용하지 않더라도 예측과 판단하는 부분은 비슷하기 때문에, 이후 프로젝트에서 예측과 판단 부분의 코드를 참조할 수 있을 듯 하나 모든 종류의 말을 사용하는 원래 체스와 달리 이번 프로젝트에서는 폰만 사용하기 때문에, 예측하고 판단하는 기준을 변경해야 함. 예측하고 판단하는 방식이 아예 다를 수 있음도 염두에 두어야 할 듯.
2. 프로젝트 계획
1.
성능 평가 지표
•
승리 횟수
•
승리할 때 까지 움직인 횟수 → 움직이는 횟수 최대한 적게
◦
판이 클 때 의미가 있을듯
•
폰만 사용하는 것 말고 일반 체스로 돌린 것도 고려해보기
→ 만약에 폰만 사용하는 엔진 구현에 시간 할애가 많이 될 것으로 예상되면, 과감하게 진행방향 수정 (게임 엔진 구현보다는 ‘강화학습’ 자체에 focus)
2.
실험 계획
•
기존에 chess나 pygame library로 chess 게임을 구현할 수 있음. 그런데 우리가 계획했던 프로젝트(pawn chess)를 원래있는 library로는 구현하는 것이 없어보임. 따라서 다른 사람들이 구현해놓은 코드를 수정하거나, 우리가 처음부터 새로운 엔진을 구현해야할 것으로 보임.
•
만약에 파이썬 내장 라이브러리가 아닌 우리가 직접 코드를 구현하게 된다면 다음처럼 구현할 예정이다. 체스 보드를 열과 행으로 표현하고, 1과 -1을 흑 백측 색 폰 기물로 지정, 0을 아무것도 없는 상태로 지정한다. 앙상블 규칙이 없는 상태에서 폰이 선택할 수 있는 action은 3가지가 있다. 전진 (이 부분도 보드가 커지면 1칸전진, 2칸전진으로 추가적으로 나눌 수 있다) ,좌측 공격, 우측 공격이다.
•
추가적으로 논의할만한 사항들
◦
기물 종류가 1개(폰)밖에 없는데 폰들을 위치에 따라서 구분해줘야할까? -ex) bP1, bP2..
3. 데모 구현
•
대강의 게임 과정을 그려보기 위해 게임 엔진의 데모 버전을 제작
•
폰의 넘버는 state를 비교하는 데 영향을 미치지 않음
다음과 같은 상황에서, 가장 왼쪽 아래에 있는 흰색 폰이 1번 폰일 때와 2번 폰일 때의 state가 동일함
⇒ state를 나타낼 때는 폰의 넘버를 구별하지 않기로 함
Q-table의 state는 판의 모양 그대로 저장하는 것이 아닌, ‘B-BB-B—-WW-W—W’와 같이 한 줄로 저장
•
데모 게임 진행 방법
1.
4x4 판에서 (0~3),(0~3) 사이 좌표를 무작위로 선정
2.
1에서 선정한 좌표에서, 다시 무작위로 하나의 action 선택
3.
2에서 선택한 action이 불가능한 움직임이라면 1로 돌아가 다시 좌표 선택부터 반복
ex> 체스 말이 판의 끝까지 도달했을 때 앞으로 전진하는 action이 선택 → 불가능한 움직임
4.
최종적으로 얼마나 더 많은 기물이 남아있는지에 따라 승리, 무승부, 패배 측정
•
데모 진행 결과
선공인 백측의 승률의 33.26%, 후공인 흑측의 승률이 31.28%, 무승부 35.46%로 세 개의 결과값이 각각 33%에 근접함을 볼 수 있음
•
데모 진행 결과 실제 학습 시 고려해야 할 부분
◦
지금은 각 기물의 움직임을 직접 지정해주었지만, 랜덤하게 움직이게 할 예정
: 테두리에 있는 기물이 아니면 할 수 있는 action은 3가지가 있다. 전진, 좌측 공격, 우측 공격이다. 백측부터 하여서 랜덤하게 1개의 기물을 선택하여 움직임 3개 중 또다서 랜덤하게 정해서 첫 번째 수를 두고, 계속하여 진행한다.
: 강화학습이 아닌, 랜덤하게 움직이는 흑과 백의 경기 데이터를 축적시켜서, 학습이 전혀 되지 않은 상태에서의 흑백 승률을 먼저 기록하자. (판의 크기가 작을수록 선공인 백 측의 승률이 높을 것으로 예상)
◦
어떻게 AI의 우수성을 판단하는가?
: 이 프로젝트는 양 측이 대결을 하여서 승패가 갈리는 경우이다. 따라서 우수성을 판단하는 지표로는 다음과 같다.
1.
승률
a.
당연하게 승률이 높은 모델이 좋은 모델이다. 하지만 이 부분에서는 우리가 학습시킨 AI끼리의 승률을 판단하기 때문에 한계가 있을 수 있다. 결국 우리가 만든 여러 모델들중에서 순위를 메기는 것이기 때문이다.
b.
위 문제를 해결하기 위해서 학습시킨 후 사람들과의 대결을 실행하는 방향으로 보여주는 방법이 있다.
c.
위에 언급한 강화학습을 쓰지 않는 랜덤하게 움직이는 경우와 대결을 시켜서 승률을 측정할 수도 있을 것이다. (그런데 아마 의미없을 정도로 높은 승률 기록할 것으로 예상)
2.
승리하기까지의 시간
a.
승리에 도달하기 까지의 시간을 턴으로 환산하여 더 짧은 턴에 승리라는 목표에 도달하는 것이 좋은 모델이다.
b.
시간만을 단축하려다가 안좋은 모델이 나올 문제도 생각하여야 할 것
3.
승리 점수
a.
남은 기물의 개수나, 얼마나 기물이 앞으로 전진하였는지 등 승리 정도를 척도화 시킬 수 있을 것이다. (대승와 겨우 이긴 승리 차별화)
4. Q-table 구현
1.
랜덤하게 움직이는 2개의 agent로 100000번 게임을 진행하고 각 게임의 승패 기록.
2.
승리하였으면 0.9/ 무승부면 0.6/ 패배시 0.3으로 점수부여. (판에 생존한 말의 수에 따라서 추가 점수 부여)
3.
모든 기록(약 중복 포함 60만개 state)을 쌓은 후에 같은 state에 대해서 action들의 평균 산출(1.5만개 state로 축소).
4.
백측 초기 q_table
5.
흑측 초기 q_table
5. 1차 학습
1.
4에서 구현한 q_table 값을 이용해서, 각 state에서 최고 점수를 주는 action을 검색.
ex) 위와 같은 경우에는 3-U라는 action 선택
2.
흑측도 같은 방식으로 action 검색후 선택.
3.
1번의 게임 진행후, 승리하였으면 밟아온 state-action value를 높은 방향으로 업데이트. 반대로 패배하였으면 낮추는 방향으로 업데이트. 무승부를 하였을때는 업데이트 하지않았다.
ex) 위 처럼 한 게임을 했을 때, 백측이 3-U라는 action을 취하고 패배하였다. 그래서 3-U는 더 낮은 값으로 업데이트 되었다.
1차 학습 결과, 특정 state들의 경로만 반복해서 학습을 하는 문제가 발생하였다. 예를 들어서 {4-U, 1-D …. } 에서 모든 action들이 최고값이 되었때, q-table에 따라서 action을 취하므로 계속해서 게임에서 같은 수만 반복하였다. 특히, 무승부를 하였을 때는 업데이트를 해주지 않았기에, 최고 reward를 얻는 경로에서 무승부를 얻는 값만 반복하였다.
6. 2차 학습
•
reward 할당 비율 변경
1.
패배했을 때의 reward* = reward x (10/11+score*0.1), 승리했을 때의 reward = reward x (11/10+score*0.1), 무승부 일 때의 reward = reward x (1+score*0.1)으로 설정함
2.
score는 종료 시 남아있는 기물의 숫자, 전진한 정도에 따른 점수
3.
특정 state들의 경로만 반복해서 학습을 하는 문제를 해결하기 위해서 일정 확률로 Q-table 값을 따르지 않고 다른 action을 취하는 방식으로 업데이트
4-U의 값을 확인해보면 게임을 2번 수행한 이후의 값은 낮지만, 100번의 게임을 수행한 이후의 값이 높아진 것을 볼 수 있음
프로젝트의 발전 방향
•
이후 판의 크기를 8x8, 16x16 등으로 키우거나, 체스 말의 종류를 늘려 적용해볼 수 있다
•
실제 체스 판처럼 시각화하여 나타낼 수 있다
•
Q-Learning 외에 DQN 등의 학습 방법으로 학습시켜 성능을 비교해볼 수 있다
