게임 서버 프로그래밍 입문 (5) - 라이브러리 (Random MT 함수)

게임은 일종의 랜덤의 연속적인 놀이입니다. 디아블로3 같은 게임을 생각해 봅시다. 이 게임의 줄거리는 악마를 잡는 게임입니다. 게임 진행도 악마를 죽이고, 그 악마가 괜찮은 장비를 들고 있다면, 그걸 주워다가 착용해서 좀 더 강해지고, 강해지면 더 강한 악마를 처치하는 드래곤볼 시스템을 탑재 하고 있습니다.   오른쪽 스샷은 2014년 9월 1일 기준으로 필자가 정복자 레벨 (최고 레벨 = 70 이후로 다시 1부터 시작하는 레벨) 277이 되도록 하나밖에 못 먹은 아이템입니다. 자랑은 아니고, 제가 죽인 몬스터들의 숫자를 보도록 하겠습니다.   친절하게 디아블로3은 이런 것도 카운팅이 되고 있어요. 디아블로3은 몬스터 죽일 때마다 캐릭터 객체 어딘가에서 카운팅이 된다는 거겠죠. 위의 창에 나타난 정보로는 제가 정예 24665마리를 처치했고 일반 몬스터는 642560마리를 잡았다고 기록되어 있습니다.

 

앞서 말씀드렸듯이 디아블로3은 무수히 많은 아이템이 있고, 몬스터를 죽일 때마다 굉장히 낮은 확률로 높은 아이템을 떨어뜨립니다. 그럼 이 전설 아이템이 드랍되는 프로그램을 어떻게 작성하면 좋을까요? 간단히 생각한다면 아래와 같이 작성할 수 있지 않을까요?

 

이렇게?

#include <cstdlib> #include <ctime> #define ITEM_ID_MAX     (1000000)   //아이템 최대 ID 번호    ... //랜덤 아이템 ID를 생성 int randomDropItem() {      return (rand() % ITEM_ID_MAX) + ITEM_ID_START; }   //랜덤 시드 생성 srand((unsigned int)time(NULL));   //드랍 아이템 생성 Item *item = new Item(randomDropItem());

 

랜덤 함수를 써서 적절히 처리했습니다만, 이러면 정말 될까요?
혹시 rand 함수가 어느 숫자까지 랜덤으로 뽑을 수 있는지 알고 계시나요?

 

레퍼런스 사이트인 cplusplus.com나 MSDN에서 함수 정의를 보도록 하죠 . 음... 리턴 값으로 0 ~ RAND_MAX까지 의사 난수를 준다고 하네요. RAND_MAX…… 0x7FFF 로 정의되었다고 합니다. 계산기로 보니 0x7FFF, 2byte short의 최댓값이네요.

 

16bit 컴퓨터 당시의 잔재로 생각됩니다만, 왜 하필이면 0~0x7FF로 제한을 두었을까요?
C++의 rand 함수는 아래의 레머(Lehmer)가 고안한 알고리즘을 활용합니다.

 

f(x) = (A * f(x-1) + C ) mod M

즉, 계산을 통한 난수를 만듭니다. 이를 pseudo-random number, 의사 난수라 합니다.
의사 난수 공식에 사용되는 A, C, M은 정수이며, A가 8로 나눌 때 나머지가 5인 수, C 가 홀수 이면, 0 ~ (M-1)까지의 정수가 M 주기로 한 번씩 나타나는 성질을 이용하죠.

 
이제 무엇이 문제인지 눈치를 채셨나요?

 

아까 디아블로3의 마법사의 로망 “워의 마법봉” 드랍 확률을 1/1000이라고 합시다. 
그리고 위의 함수 처리로 아이템을 드랍시킨다면,
int itemRatio = rand() % 1000; if (itemRatio == 987) return “워의 마법봉”; 으로 작성되겠죠.

여기서 레퍼런스 랜덤 함수 처리, 0~32767 에서 나오는 숫자 중 %1000을 하게 되면 확률적으로 0~767 id가 33번 나올 때, 768~999까지 32번 나오겠네요.

 

이거 게임 밸런스가 미묘하게 틀어지기 시작하는군요.
현실적으로 기획자가 이 아이템은 십만 분의 1 확률로 나오도록 처리하도록 해봅시다.
코드 상으로는 아마 int itemRatio = rand() % 100000; 이 되겠군요.
그럼, 과연 32768 ~ 99999의 숫자가 나올까요? 위 id의 게임 아이템은 절대 얻을 수 없겠죠.
또, rand는 시드 값 위 식에서 f(0) 값으로 srand 함수를 사용하여 지금 시각을 주도록 코딩하는데, 이 srand 시드 값은 프로그램 전체에 영향을 미칩니다.

 

그런데 rand의 난수 범위가 short 최대치 인지라, 이 랜덤 순열은 1주 ~ 2, 3주 러닝 타임을 가진 게임 서버 프로그램에서 난수 순환이 빨리 오겠죠.
결국, 이런 여러 문제로 기본 C언어 (POSIX C이라고 합니다)의 rand 함수는 게임 프로그램에 사용하는 것은 위험한 요소가 많습니다.

 

그럼 어떻게 하면 좋을까요?

수학자들은 이미 해결을 했습니다.
보통 메르센 트위스터 랜덤(Mersenne Twister random)이라고 해서 RandomMT라고 표현하기도 합니다.

(MT는 Multi Thread 약자가 아닙니다) 난수의 반복주기가 메르센 소수(Mp = 2p - 1 )라 그 품질이 좋고,

이 주기가 2의 19937 제곱 -1이므로 위의 예와 같은 rand() % 1000으로 몇몇 숫자 범위 대에 확률이 낮아지지 않습니다. (오차 범위에 수렴하죠).

게다가 rand 함수보다 빠르기도 합니다. (비트연산 코드입니다) 실제 구현 소스는 아래 사이트에서 열람할 수 있습니다.

 

 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

C++0x11 이후 버전에서는 이 함수를 아예 표준 라이브러리에 포함 시켰습니다.
이를 활용한 클래스는 아래와 같습니다.

 

RandomMt.h

#pragma once #include "stdafx.h"   #define RAND(type, maxVal)       (type) RandomMT::getInstance().rand(maxVal)   class RandomMT : public Singleton<RandomMT> { public:     uint64_t rand(int maxVal)     {         //MT19937 난수 엔진         std::mt19937 engine((uint32_t)time(nullptr)  + (uint32_t)std::this_thread::get_id().hash());                 std::uniform_int_distribution<uint64_t> distribution(0, UINT64_MAX);         //rand 생성 함수포인터 bind         auto generator = bind(distribution, engine);           return (uint64_t)(generator() % maxVal);     } };

 

잘 보시면 엔진 초기화 할 때, srand 처럼 현재 시각을 넣는데 거기에 현 쓰레드의 hash 번호를 더해서 넣어 주었습니다. 각각 쓰레드 마다 다른 값을 줘야 하기 때문이죠.
아마 현업에서는 이 코드를 직접 구현한 곳이 많을 겁니다.

 

아니면 이것을 또 개선한 RandomWell을 쓸 겁니다.
여기서는 메르센 트위스터 19937을 사용했지만, 심화로 Random Well 소스를 위의 사이트에서 구해서 작성해 보시는 것도 좋은 경험이라 생각합니다. (생각보다 몇 줄 안 합니다)  

 

위 내용은 제가 집필한 "게임 서버 프로그래밍 입문" 책의 내용중 일부 부분에 대한 내용입니다.

전체 소스 코드와 책 구입에 대해서는 http://rosagigantea.tistory.com/589 에 링크 시켰습니다.