LACI-QD 구현기

이 글은 Lockcept AI의 첫 작품인 쿼리도 AI Agent (LACI-QD)를 구현한 과정을 담은 글이다. 아직 성능이 뛰어나지는 않지만, 지금까지 어떻게 접근했는지 방법을 정리해보려고 한다.

 

https://github.com/lockcept/LACI-QD

GitHub - lockcept/LACI-QD: Lockcept AI of Quoridor

 

알파제로

크게는 알파제로의 틀을 따왔다(https://github.com/suragnair/alpha-zero-general). 핵심 아이디어는 Policy, Value Network의 단일화 및 MCTS를 활용한 Policy Evaluation이다. 이 프로젝트에서는 오델로를 예시로 들어 여러 가지 게임에 적용할 수 있는 AlphaZero General Framework를 제공해주었다. 알파 제로 논문은 https://blog.lockcept.kr/138 에서 간단하게 리뷰한 적이 있으니 궁금하면 참고해보기를 바란다.

 

모델링

네트워크의 input으로는 보드게임의 state를 받는다. 보드게임의 현재 상태를 최대한 간결하게 표현하고자 다음과 같이 설계하였다.

1. 9x9 보드게임 판에서 나의 위치 (one-hot)
2. 9x9 보드게임 판에서 적의 위치 (one-hot)
3. 8x8 세로벽의 존재 유무 (one-hot)
4. 8x8 가로벽의 존재 유무 (one-hot)
5. 나의 남은 벽의 개수
6. 적의 남은 벽의 개수

하나의 다차원 배열에 담기 위해 9x9x6의 배열을 선언하여 데이터 저장시에나 네트워크 추론 시 사용하였다.

 

게임 룰

게임 룰을 작성하는 데에는 큰 무리는 없었다. 특정 state에서 특정 action을 취할 때에 state가 어떻게 변하는가, 이 때에 valid action으로는 어떤 것들이 가능한가 를 구현하면 되었다.

action의 종류는 움직임 9x9, 세로벽 8x8, 가로벽 8x8으로 총 209 종류로 정의하였다.

조금 까다로운 부분이 있었다면 움직임을 취할 때 근접한 칸에 적 유닛이 있다면 점프하여 넘어갈 수 있다는 것, 이 때에 점프 할 위치에 벽이 있다면 90도 방향으로 꺾어 움직일 수 있다는 특수 규칙이었다. 그러나 코드가 조금 복잡해질 뿐 논리적으로 큰 어려움은 없었다.

 

무한 루프

그렇게 기존 프레임워크에 맞추어 학습하였으나, 큰 문제가 발생했다. 게임을 마치는 방법을 학습하지 못한다는 점이었다. 우연히 한 번이라도 목표 지점에 도달하게 된다면 우월한 전략으로 취급되어 학습이 진행 되겠지만, 벽을 설치해대면서 랜덤한 무빙을 취했을 때 그럴 확률이 너무 낮았다. 그래서 거의 무한루프에 가까운 학습 진행을 보여주었다.

 

해결해보고자, 현재 진행 중인 턴을 board의 state에 추가하였다. 그리고 이 값이 max_turn 보다 커질 경우 목표 지점까지의 거리를 계산하여 부분적 승리로 인정하였다. 그러나 인위적인 점수의 개입을 했음에도 불구하고 아직은 성과가 없어서 반려하였다.

 

구조 변경

말이 올바른 방향으로 가고 있는지, 어떤 칸이 목표 지점과 가까운지 알려주기 위하여 보드판의 구조를 조금 변경하였다. 목표 지점까지의 최단 거리가 얼마인지 계산하여 모든 칸에 기입하였다. 이 데이터를 토대로 network는 나의 방향성 및 적을 방해하는 액션의 학습을 기대했다.

추가로 벽의 위치가 말의 위치와 잘 어울릴 수 있도록, 총 판의 크기를 17x17로 정의하였다. 그렇다면 홀수 번째 칸은 말이 위치 가능한 곳, 짝수 번째 칸은 벽이 위치 가능한 곳이 된다.

남은 벽의 수, 남은 거리 등 스칼라로 표현 가능한 값은 굳이 다차원 배열에 포함하지 않았다.

 

네트워크는 CNN Layer와 Fully Linear Layer를 결합하여 설계하였다.

CNN Layer는 (5, 17, 17) → (64, 17, 17) → (128, 9, 9) → (256, 9, 9) → (512, 9, 9) → 512 → 256

Fully Linear Layer는 4 → 32 → 32

두 값을 합쳐서, 256 + 32 → 256 → 1 (tanh) + 209 (softmax) 로 분해하여 사용하였다.

 

초기 데이터

백지부터 시작하는 학습을 꿈꾸긴 하였으나 시간과 자원의 한계로 인해 학습 초기 데이터를 임의로 생산해주었다. 그리디 Agent를 서로 맞붙여서 각각의 board state와 policy를 저장하여 네트워크 학습에 사용했다. 결과적으로는 매우 빠른 수렴 속도를 보여주었다. 그러나 백지부터 시작하지 못했다는 한계로 인해 창의적인 플레이를 기대하기 힘들 수 있으므로, 엄청난 성능 향상이 아닌 경우 최대한 지양하고자 한다.

 

시각화

게임을 시각화 할 필요성을 두 가지 느꼈다. 하나는 알고리즘의 직관성을 높이기 위해서, 그리고 하나는 직접 알고리즘과 싸워보기 위해서이다.

간단한 명령어를 통해 게임을 관찰하거나 플레이 해볼 수 있도록 만들었다.

 

python src/play_game.py --p1 [player_type] --p2 [player_type]

 

이 때, player_type에는 human, random, mcts, greedy 등 다양한 알고리즘이 들어갈 수 있다.

 

만약 human이 아닌 AI algorithm을 선택한 경우 행동 전 이렇게 확률 분포를 보여준다.

 

결과

썩 좋지는 못했다.

 

Loss Graph는 이렇게 생겼는데 200 timesteps 근처에서 Greedy 초기 데이터가 점점 희석되어 그래프의 양상이 조금 달라졌다.

 

 

NNet, MCTS를 greedy와 대결 시켰을 때에 좋은 승률을 보이지 못하였다. 특히 Policy Loss가 급격히 증가하는 지점에서 승률이 망가지기 시작했다.

 

MCTS의 사용 이유는 NNet의 발전을 위해서지만, MCTS가 NNet보다 크게 똑똑하지는 않음을 보였다.

 

Greedy Policy와 Network Policy는 점점 달라짐을 알 수 있었다.

한 편, 백지부터 학습을 시작할 경우 Cross Entropy가 7.8부터 시작하여 3.8로 수렴하였다.

 

초기 데이터를 활용하지 않은 경우 Loss는 위와같이 변화했다.

 

앞으로

현재 문제점은 MCTS가 network를 발전시키지 못하는 점이라고 생각한다. 이 부분을 해결하여, 학습 사이클을 개선하여 최종적으로는 웹서비스로 AI와 대결할 수 있게끔 만들고 싶다. 적어도 Greedy 상대로 95% 이상의 승률은 보여야 하지 않나 싶다.