[논문]매치 3 게임 플레이를 위한 PPO 알고리즘을 이용한 강화학습 에이전트의 설계 및 구현

박대근; 이완복

doi:10.22156/cs4smb.2021.11.03.001

매치 3 게임 플레이를 위한 PPO 알고리즘을 이용한 강화학습 에이전트의 설계 및 구현
Design and Implementation of Reinforcement Learning Agent Using PPO Algorithim for Match 3 Gameplay 원문보기

융합정보논문지 = Journal of Convergence for Information Technology, v.11 no.3, 2021년, pp.1 - 6

박대근 (공주대학교 게임디자인학과) , 이완복 (공주대학교 게임디자인학과)

초록
AI-Helper

매치 3 퍼즐 게임들은 주로 MCTS(Monte Carlo Tree Search) 알고리즘을 사용하여 자동 플레이를 구현하였지만 MCTS의 느린 탐색 속도로 인해 MCTS와 DNN(Deep Neural Network)을 함께 적용하거나 강화학습으로 인공지능을 구현하는 것이 일반적인 경향이다. 본 연구에서는 매치 3 게임 개발에 주로 사용되는 유니티3D 엔진과 유니티 개발사에서 제공해주는 머신러닝 SDK를 이용하여 PPO(Proximal Policy Optimization) 알고리즘을 적용한 강화학습 에이전트를 설계 및 구현하여, 그 성능을 확인해본 결과, 44% 정도 성능이 향상되었음을 확인하였다. 실험 결과 에이전트가 게임 규칙을 배우고 실험이 진행됨에 따라 더 나은 전략적 결정을 도출 해 낼 수 있는 것을 확인할 수 있었으며 보통 사람들보다 퍼즐 게임을 더 잘 수행하는 결과를 확인하였다. 본 연구에서 설계 및 구현한 에이전트가 일반 사람들보다 더 잘 플레이하는 만큼, 기계와 인간 플레이 수준 사이의 간극을 조절하여 게임의 레벨 디지인에 적용된다면 향후 빠른 스테이지 개발에 도움이 될 것으로 기대된다.

Abstract ▼ AI-Helper

Most of the match-3 puzzle games supports automatic play using the MCTS algorithm. However, implementing reinforcement learning agents is not an easy job because it requires both the knowledge of machine learning and the way of complex interactions within the development environment. This study proposes a method in which we can easily design reinforcement learning agents and implement game play agents by applying PPO(Proximal Policy Optimization) algorithms. And we could identify the performance was increased about 44% than the conventional method. The tools we used are the Unity 3D game engine and Unity ML SDK. The experimental result shows that agents became to learn game rules and make better strategic decisions as experiments go on. On average, the puzzle gameplay agents implemented in this study played puzzle games better than normal people. It is expected that the designed agent could be used to speed up the game level design process.

주제어

표/그림 (11)

그림 Fig. 1. Four Stages of MCTS
그림 Fig. ２. Structure of Reinforcement Learning
그림 Fig. 3. MatchThreeGame Class
그림 Fig. 4. Agent Structure
그림 Fig. 5. Observation Data
그림 Fig. 6. Candy Crush Saga 99 Stage
표 Table 1. Hyperparameter Setting
그림 Fig. 7. Tensorboard Graph
그림 Fig. 8. Number of Clear Games Per Game
그림 Fig. 9. Number Of Remaining Jelly Per Game
표 Table 2. Required Turn Comparison

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

편이다[4]. 본 연구에서는 게임 분야 개발자들이 보편적으로 많이 사용하는 유니티 Machine Learning(ML) SDK를 이용하여 강화학습 에이전트를 손쉽게 개발할 수 있는 방법을 제안하며 게임 플레이 에이전트를 설계 및 구현하고 그 효용성에 대해 알아보려 한다.

제안 방법

개발한 게임 플레이 AI는 “캔디 크러쉬 사가의 99 스테이지(Candy crush saga 99 stage)” 게임에 적용하여 게임플레이를 학습시키고 에이전트의 플레이 성능을 측정하기 위해 데이터를 수집한 후 결과를 분석하였다. 본 논문의 구성은 다음과 같다.
2와 같이 에이전트와 환경 두 부분으로 구성되며, 에이전트는 환경을 관찰하여 정책에 따라 행동을 선택하여 실행한다. 그 후 환경에서 다음 상태와 보상 결과를 받고 보상을 최대화하는 방향으로 정책을 수정한다[10]. 이 과정을 충분한 횟수만큼 반복하여 최적의 정책을 찾아가게 된다.
구성하였다. 보상이 자주 이루어지고 블록의 랜덤 성이 크기 때문에 빠른 업데이트를 위해 수치들을 낮게 지정하도록 구성하였다.
본 연구에서는 먼저 유니티 엔진을 이용하여 캔디크러시 사가를 모방하여 매치 3 게임을 구현하였으며 구현한 매치 3 게임에 유니티 ML SDK를 적용하여 매치 3 게임 자체를 에이전트로 구성하였다.
실험은 캔디 크러쉬 사가의 99 스테이지를 모방하여 만든 스테이지를 이용하여 에이전트를 학습시키고 그 결과를 분석하였다. 실험은 Window 10 Home 1909 OS에서 Unity 2019.
3에서 보이는 바와 같이 게임 진행을 위한 기본적인 기능인 X*Y Field 생성, Block 선택, Block 연결확인, 연결된 Block 삭제, Field 정렬, Field 채우기, 특수 Block 생성 기능이 구현되어 있다. 정렬과 채우기는 캔디 크러시 사가를 모방하여 위에서 아래로 정렬 및 채우되 빈 곳이 있으면 빈 곳으로 블록이 흐르도록 만들어졌으며 Match 방식과 특수 Block 생성의 조건도 캔디 크러시 사가의 방식과 동일하도록 구현하였다.
학습을 위한 에이전트는 유니티 ML SDK에 있는 Agent Class를 상속받음으로써 구성하였으며 본 논문에서는 Fig. 4에 보이는 바와 같이 게임을 진행하는 MatchThreeGame Class에 상속하여 단일 에이전트로 구성하였으며, 관측 데이터 입력과 행동 정의는 Sami Purmonen이 제안한 방식으로 진행하였다[13].

대상 데이터

학습에 이용되는 스테이지는 [Fig. 6]에서 보이는 캔디 크러시 사가의 99 스테이지를 모방하여 구성하였다.

데이터처리

에이전트의 성능 측정을 위한 비교 데이터는 유튜브를 통해 아이템을 사용하지 않고 캔디 크러시 사가 99 스테이지를 클리어한 영상 49개를 수집하여 클리어를 위해 행동한 턴 수를 분석하였으며 그 결과는 [Table 2]의 Expert Group의 수치와 같다.

이론/모형

선택 단계에서 어떤 자식 노드를 선택해야할지 결정하기 위해 각 노드의 Upper Confidence Bounds Apply To Tree(UCT) 알고리즘으로 점수를 계산하여 자식 노드를 선택한다[7].

성능/효과

게임 횟수별 클리어 횟수 증가와 남은 젤리 수의 감소를 통해 에이전트가 게임의 클리어 방법을 올바르게 학습하고 있다고 판단할 수 있었다.
9]와 같이 나타났다. 스테이지에 존재하는 9개의 젤리를 2번씩 지워야 게임이 종료되기 때문에 스테이지 클리어를 위해서는 18개의 젤리를 지워야하는데, 게임의 학습 횟수가 100단위로 올라갈 때마다 게임당 남은 젤리의 수가 적어지는 것을 확인할 수 있었다.
평균적으로 11턴 이후에 게임을 종료하기 때문에 비교데이터보다 평균 44%적은 턴 수를 필요로 하였다. 실험 데이터들을 통해 에이전트가 게임의 규칙을 학습한 이후, 매우 전략적 판단을 하고 있다는 것을 알 수 있었으며 본 연구에서 구현한 퍼즐 게임 플레이 에이전트가 평균적으로 사람보다 퍼즐 게임을 더 잘 플레이한다는 것을 알 수 있었다.
평균적으로 11턴 이후에 게임을 종료하기 때문에 비교데이터보다 평균 44%적은 턴 수를 필요로 하였다. 실험 데이터들을 통해 에이전트가 게임의 규칙을 학습한 이후, 매우 전략적 판단을 하고 있다는 것을 알 수 있었으며 본 연구에서 구현한 퍼즐 게임 플레이 에이전트가 평균적으로 사람보다 퍼즐 게임을 더 잘 플레이한다는 것을 알 수 있었다.
8]과 같이 나타났다. 학습 과정과 마찬가지로 게임의 학습 횟수가 100단위로 올라갈 때마다 클리어 횟수가 많아지고 있는 것을 확인할 수 있었다.

참고문헌 (13)

E. Poromaa. (2017. Crushing Candy Crush : Predicting Human Success Rate in a Mobile Game using Monte-Carlo Tree Search. Student thesis. KTH.
R. Coulom. (2006). Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. 5th International Conference on Computer and Games. May 29-31.
D. Silver. (2016). Mastering the game of Go with deep neural networks and tree search. Nature. 529(7587). 484-489.

상세보기
A. Andelkovic. (2018). Using Artificial Intelligence to Test the Candy Crush Saga Game. Alexander Andelkovic. comaqa. (Online). https://www.youtube.com/watch?v4xECMpgeOxE/
D. Silver. (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. Science. 362, 1140-1144.

상세보기
L. Kocsis & C. Szepesvari. (2006). Bandit based monte-carlo planning. In European conference on machine learning (pp. 282-293). Springer, Berlin, Heidelberg.
S. Gelly, Y. Wang, R. Munos & O. Teytaud. (2006). Modification of UCT with Patterns in Monte-Carlo Go. Computer Science.
Aiandgames. (2018). Monte-Carlo Tree Search in TOTAL WAR: ROME II's Campaign AI. aiandgames. (Online). https://aiandgames.com/revolutionary-warfare-the-ai-of-total-war-part-3/
M. V. Otterlo & M. A. Wiering. (2012). Reinforcement learning and markov decision processes. In Reinforcement learning (pp. 3-42). Springer, Berlin, Heidelberg. DOI : 10.1007/978-3-642-27645-3_1
F. S. Melo, (2007). Convergence of Q-learning: a simple proof. Proceedings of the European Control Conference 2007. 2-5.
R. Bellman. (1957). A Markovian Decision Process. Journal of Mathematics and Mechanics. 6(5). 679-684.
M. Tokic & G. Palm. (2011). Value-Difference Based Exploration: Adaptive Control Between Epsilon-Greedy and Softmax. Advances in Artificial Intelligence, Lecture Notes in Computer Science. 7006. 335-346 DOI : 10.1007/978-3-642-24455-1_33
S. Purmonen, (2017). Predicting Game Level Difficulty Using Deep Neural Networks. Student thesis of KTH.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증