[저널리뷰] - Anomaly Detection in Player Performaces in Multiplayer Online Battle Arena Games

Journal Reveiw of Game Anomaly Detection

논문제목 : Anomaly Detection in Player Performaces in Multiplayer Online Battle Arena Games

2022년에 나온 논문으로 Cheat Detection의 가장 최근논문이라 생각이 들어 리뷰를 진행했다. 이번 논문은 특히 Background 부분의 Reference Paper들을 하나하나 보면서 과거의 Anomaly Detection이 어떻게 진행되어왔는지 볼 수 있었다.

 

Abstract

E-Sports 시장이 커지면서 Cheating의 문제도 커지고 있기에 이 논문에서는 DOTA2를 case study로 선정하여 새로운 Archetype Analysis를 적용하였고 이 Anomalies들이 Esports Broadcasting과 Cheat Detection에 어떻게 활용되는지를 보여준다.

Keywords

- Datasets

- Neural Networks

- Gaze Detection

- Text Tagging

 

Introduction

논문의 초반에는 과거에 비해 E-sports 시장이 얼마나 큰 규모가 되었는지와 Cheating이 게임 유저가 떠나가는 원인인 이유를 설명한다. 이 논문에서 DOTA2 라는 게임를 연구대상으로 사용하였음을 밝히고 연구의 전반적인 방향을 설명한다. 크게 DOTA2의 매치데이터를 수집,  Archetype Analysis 적용, Hyper-parameter optimisation으로 나뉜다. 그리고 이 결과들이 storytelling과 cheat detection에 사용될 수 있다고 말한다.

Background

1. 게임의 원격적인 데이터 수집 및 분석이 가능해져서 이 연구분야가 커지게 되었다. 대표적인 분야로는 Behavior Profiling, Player Behaviour Visualization, Win Prediction, Micro Prediction, Role Detection 등이 있고 이분야들은 특히 Epsorts 중계에 큰 도움이 된다.

2.  Anomaly Detection 분야로 Player의 게임 속 Cheating을 방지하는 것 이 논문에서 두 논문을 reference로 달았는데 그 논문은 다음과 같다.

- Phai Vu Dinh, Thanh Nguyen Nguyen, and Quang Uy Nguyen. 2016. An empirical study of anomaly detection in online games. In 2016 3rd National Foundation for Science and Technology Development Conference on Information and Computer Science (NICS). IEEE

- Albert B Jeng and Chia Ling Lee. 2013. A study on online game cheating and the effective defense. In International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems. Springer

 

첫번째 논문의 경우, unsupervised learning 을 사용하였고, 두번째 논문의 경우 활동로그를 바탕으로 통계분석을 수행하였다.

 

그리고 앞으로 이 논문에서도 다룰 Archetype Analysis를 팀게임에 적용한 논문은 다음과 같다.

 

- Rafet Sifa, Anders Drachen, Florian Block, Spencer Moon, Anisha Dubhashi, Hao Xiao, Zili Li, Diego Klabjan, and Simon Demediuk. 2021. Archetypal Analysis Based Anomaly Detection for Improved Storytelling in Multiplayer Online Battle Arena Games. In 2021 Australasian Computer Science Week Multiconference.

이 선행연구는 League of Legend 라는 게임을 바탕으로 분석을 진행하였는데 이 논문에서 분석한 DOTA2라는 게임과 가장 유사하며 유명한 게임이다. 이 논문을 리뷰하면서 컨벡스의 개념을 처음 접했는데, 컨벡스의 수학적 의미는 공간 내 임의의 두 점을 선택했을 때 두 점을 이은 선은 반드시 해당 공간에 포함된다는 성질을 의미한다. 추가로 컨벡스개념을 이해하는데 가장 도움이 되었던 블로그 링크를 함께 첨부한다.

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=destiny9720&logNo=221410094589

19. 컨벡스(Convex)와 삼각형(Triangle)

 

Hyper Parameter Tunning 에는 Baysian Hyper Parameter Optimisation 을 사용하였다.

 

3. DOTA2에 대한 설명들이 나오는데, 간단히 설명하면 League of Legend와 비슷하다. 공격로가 세 갈래로 나뉘어져있고 각 진영으로 이어진다. Creep이라고 불리는 npc들이 매 시간마다 공격로에 소환되고, 플레이어가 죽게되면 일정시간 후에 부활하게 된다. 다양한 오브젝트들을 획득하면서 먼저 진영을 파괴하는 팀이 승리하는 방식이다. 

Map of DOTA2

DOTA2에 대한 더 자세한 플레이 방식이나 도메인적인 지식을 원한다면 아래 논문을 참조해도 좋다.

- Simon Demediuk, Peter York, Anders Drachen, James Alfred Walker, and Florian Block. 2019. Role Identification for Accurate Analysis in Dota 2. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, Vol. 15.

 

Algorithms

1. Archetype Analysis & Frank-Wolfe Algorithm

Archetype Analysis은 해석가능한 데이터 묘사방법인데 archetype이라고 불리는 convex와 비슷한 데이터포인트를 바타으로 분석하는 방법이다.

인 데이터가 있다고 가정하자.

 

이 X는 인수분해를 통해 다음과 같이 나타낼 수 있다.

 

 

B 는 column-stochastic하고 archetype을 정의하기 위해 사용된다.

H 는 row-stochastic 하고 각 archetype에 대한 coefficient를 포함한다.

 

이 B와 H는 다음 Loss Function을 최소화하면서 얻을 수 있다.

각 iterative update 마다, Frank-Wolfe (FW) Algorithm을 사용하는데 convex function에서 loss를 최소화 하는 방법이다.

FW 알고리즘은 iterate마다 gradient vector를 평가하여 사전에 정의된 learning rate에 따라 업데이트를 한다. 

Stopping Condition은 iteration의 최대수치를 정해주거나, H-H_update 의 최소변화량을 treshold로 설정해주는 방법이 있다.

 

Baysian Optimization의 경우는 예제코드까지 함께 있는 친절한 링크를 첨부하겠다.

https://wooono.tistory.com/102

[ML] 베이지안 최적화 (Bayesian Optimization)

 

Data And Experiemental Results

4 Step of Archetype Analysis

(i) data collection

(ii) feature engineering and pre-processing

(iii) model training and validation

(iv) online anomaly detection

 

1. Data Collection

OpenDota API를 이용하여 7.26버전의 2,000개의 5vs5 match 데이터를 수집함. 게임데이터는 프로들의 esports 경기와 실력이 좋은 일반인들의 경기가 섞여있음. 이 플레이어들은 META (most effective tactics available)를 따라가며 진지하게 게임에 임한다. 매 초마다 많은 수치데이터가 기록된다.

 

2. Feature Engineering and Pre-processing

Table1 : Feature used for modeling

모델링에 사용된 Feature 는 위와 같다. 총 91개의 feature가 있었지만 의미 있는 8개의 feature를 selecting 하였다.

Table 2: Hyper-parameters of the Frank-Wolfe archetype analysis algorithm

하이퍼 파라미터 튜닝에 사용된 Search Space는 위와같다.

 

3. Model Training and Validation

- Archetype Analysis, Bayesian Hyper-parameter optimization.

Minimal distance d_t

t* = 13일 때 optimal distance d13 = 0.04639.

hyper-parameters k = 31, delta_b = 0.0003, delta_H = 0.009, tmaxB = 2986, tmaxH = 2561.

 

4. Online Anomaly Detection

보통 outlier는 optimal convex hull보다 극심하게 떨어져 있기 때문에 3개의 샘플을 선정하였음.

Raw features of the selected players

Anomaly 1 : Ursa라는 캐릭터를 쓰는 유저, Kill feature에서 이상함을 감지 처음 12분동안 7 kill을 함. 심지어 서포터의 도움없이 발생함.

Anomaly 2: Boush라는 캐릭터를 쓰는 유저, Kills-Hero Damge간의 이상함을 감지. 실제 데이터를 보니 그의 팀의 3명이 접속을 종료하여 2명에서 게임을 진행하였음. 팀원의 부재로 킬을 만들어내지 못한 것을 확인.

Anomaly 3: Sven이라는 캐릭터를 쓰는 유저, XPM이 충분히 높음에도 Death가 0인것을 감지. 상대 Broodmother가 spiderlings를 Sven에게 제공해서 XPM이 더 높음. 그래서 처음 20분간 레벨차이가 4레벨 차이가 발생한 것.

 

위와 같은 Anomaly들을 감지하면 Esports의 중계에 더 효과적으로 사용이 가능하다. 모델을 통해 방송자는 anomalous 한 behaviour들을 강조해서 설명할 수 있다.

 

Cheat Detection으로의 활용은 anomaly가 감지되면 계정을 mark하고 특정 threshold의 mark를 넘게 되면 관리자에게 flag되도록 한다. rank가 있는 게임에서 위와 같은 cheating은 이루어져서는 안되기 때문에 빈번한 제제가 필요하다.

 

이 모델은 매 패치별로 데이터가 변하기 때문에 재구성이 되어야 한다.

CONCLUSION

이 논문은 이상 탐지를 위한 새로운 접근 방식을 제시했다. e스포츠 방송사가 활용할 수 있는 선수의 이상 플레이 감지,
치트 감지를 위한 개선된 DOTA2에서의 베이지안 응용 프로그램을 추가로 소개했다.
효율적으로 검색할 수 있는 하이퍼파라미터 최적화 알고리즘, 보조 도구로 최적의 모델 하이퍼 파라미터 튜닝등 적용.
이 연구는 DOTA 2에 초점을 맞추었지만 특히, 이 연구에서 제시한 접근 방식은 쉽게다른 온라인 e스포츠 및 경쟁 온라인 게임으로 확장이 가능하다.