Loading
2017.07.01 14:38 - 쿠나

게임 채보 난이도 자동추산 알고리즘

- 문제


고전적인 형태의 난이도 추산 알고리즘은 LR2 Stairway 에서 이미 시도된 바가 있고, 이후 walkure에서 MCMC 알고리즘을 이용한 sigmoid model fitting을 수행하여 보다 진보된 난이도 추론을 보여준 바 있다. 그걸 보고 똑같이 15년도 말 즈음에 시도를 해 보았지만! 그닥 마음에 들지 않았다 ...


문제점은 크게 다음과 같았다.


  1. sigmoid fitting이 소모하는 엄청난 연산량
    유저는 1000명, 곡은 5000개, 토탈 500만개의 데이터에 대해 매 iteration마다 fitting하는 건 너무 가혹하지 않나. 당시 계산시키는데 한 일주일 걸린 듯. walkure도 한번 전체갱신 해놓고 다신 안 하는거 보면 ......
  2. 결과물의 질을 저해시키는 data outlier
    데이터 수가 모자란 것도 이러한 outlier에 한 몫 했는데, 이런 경우 흔히 말하는 '표백'을 하지 않는 유저가 존재할 시에는 난이도가 엉망으로 추론되는 문제가 발생한다. 애당초 각 플레이어가 모든 차트에 대해 최선을 다했을 거라는 전제를 가지고 피팅한 거니깐 ...


당시 이 문제를 어떻게 해결할까 고민 조금 했었는데 뭐 한것도 없는거 같이 일에 치여 살다가, 오랜 기간 갱신이 없어 방치된 10/11레벨 차트 서열 문제가 다시 대두되면서 다시 골치가 아파지기 시작했다. 안그래도 할 일이 많은데 자꾸 이녀석이 발목을 잡기에 이번에 확실히 끝내기로 결심하고, 대충 이틀정도 난이도 추론 모델에 대해서 생각했다.





- 알고리즘


우선 내가 가지고 있는 데이터는 walkure에 비해 훨씬 sparse하며, 표백을 하지 않을것/혹은 표백을 할 것 이라는 전제를 가지고 다시 시작해야 했다. 실제로 LR2 인랭의 경우에는 유저풀이 비교적 적은 고렙곡도 플레이 레코드가 500개 이상은 무조건 있는 반면, 선택적으로 갱신을 하는 투덱미의 경우에는 곡당 플레이레코드가 50개도 안 되는 경우가 허다하며, 유저별로 클리어 상태를 plotting 해보면 저렙에 페일 램프가 그대로 있는 상태에서 고렙은 표백한, 정말이지 피팅하기에 매우 부적합한 모델들이 천지이다. 이에 적합한 model이 존재하기는 할까? 생각하던 찰나, 투덱 이번작에서 채택된 닌자랭크가 떠올랐다. 흠... 각 유저별로 최고클딸 30개, 각 차트별 하위 20%정도 유저의 점수 평균을 각 차트의 난이도로 매기면 될 거 같았다. (물론 개수 미달의 데이터는 제외한다)




막상 해보니 그렇게 좋지만은 않았다. 주된 문제는 모든 데이터들이 자꾸 특정 난이도로 수렴해버리거나 곧잘 발산하곤 한다는 것. 아무래도 feedback 함수의 부재인 것으로 보였다.


그래서 2가지 feedback을 보완해 보기로 했다.


  • 추론된 레벨값에 대한 sigmoid 함수 추가 처리
    (알고리즘 특성상 그럴일은 없겠으나) outlier로 인하여 값이 발산해버리는 경우, 그 한도를 설정하여 둔화시키도록 하였다. 원점에서 멀어질수록 기울기를 둔화시키는 함수로서는 sigmoid가 적격인 듯. 아닌가? cot(x)가 더 좋은가? 저것도 괜찮아 보이는데 ...
    (sigmoid(x)-0.5)*4
  • 10 epoch마다 레벨별로 average normalization 수행
    어차피 절대적인 난이도의 측정이 아닌 "상대적인 서열"의 측정이 우리가 원하는 것이므로, 타당한 수준에서의 특정 레벨의 추론값의 평균값을 우리가 임의로 보정해도 이 전제는 틀리지 않는다. 차트 레벨이 11이라면, 이지게이지는 10.7, 하드게이지는 11.3, EXH는 11.8 정도로 보정하도록 하였다.
또한 outlier 방지, 즉 극한의 클딸러(?)를 방지하기 위해, 표본의 하위 10%정도를 버리도록 하였다.[각주:1]




결과는 꽤 만족스러운 듯.



믿음과 신뢰의 12레벨 표본의 경우 인플레가 약간 낀 신곡들을 제외하고 상당히 괜찮게 추산된 듯 하다. 초청소년이나 인보커나 에인션트스케이프이나, 레겐들이 손이 안 가서 그런지 다소 높게 평가되어 있긴 하지만서도. 

노트를 빽빽하게 넣은 다소 느린 곡들이 클리어 난이도가 낮은게 의외였다. 아무래도 노트가 많다 보니 회복 기회가 많아서 그런가? 역시 하드게가 후하긴 후하구나 ...


여기서는 domain knowledge로 EASY/HARD/EXH 레벨 보정을 해 준게 전부지만, 아무래도 채보의 특성이나 bpm이나 순간밀도와 같은 요소들도 같이 혼합해서 난이도 추론 모델링을 할 수 있다면 보다 정확하게 값을 추론해볼 수 있을 것이다. 그건 또 다른 차원의 나! 혹은 또 다른 리듬게임하는 어떤 공돌이에게 지그시 맡기는 걸로...




결과물 : http://iidx.insane.pe.kr


속도도 그럭저럭 빠르다. 100 epoch 기준으로 하루에 스무번정도는 너끈히 돌릴수 있을 듯.

만드는 데까지 꽤나 많은 시간이 걸렸다... 만은, 어떻게든 됐으니 그걸로 만족. 좋은 경험...인가?

  1. 근데 아무리 그래도 quasar 같은 유명한 곡은 난이도 추정값 하락을 피할 수 없더라. 그냥 그게 쉬운건가? [본문으로]
저작자 표시 비영리 동일 조건 변경 허락
신고

댓글을 입력하세요