표준 rand()함수보다 유용한 랜덤 생성 알고리즘 – MT, WELL

안녕하세요. 알콜코더 민군입니다.

 

현재 제작 중인 게임에서, 랜덤 시드 값을 일치 시켜서, 랜덤 결과를 서로 다른 클라이언트끼리 동기화 시키는 작업을 진행 하였습니다. 랜덤 시드값만 서로 일치시키면, 이후에 생성되는 랜덤 함수의 결과값들은 모두 일치가 되기 때문에, 예전에 스타크래프트와 같은 패키지 게임에서 자주 사용했던 테크닉입니다. ^^; 서로 다른 클라이언트끼리 처음 시드값만 일치 시키면, 이후의 랜덤값은 정해져 있기 때문에, 그 랜덤값을 사용한 이벤트등의 동기화에 사용하는 것이죠.

 

이런 테크닉은 패키지 게임 시절에는 리플레이 저장이나 네트워크 동기화등에서 상당히 많이 사용하였습니다. 하지만 온라인 게임으로 넘어오면서, 대부분 서버에서 랜덤값을 직접 생성하여 넘겨주기 때문에, 이 테크닉 쓸일이 거의 없었는데… 이번 상황은 랜덤값이 게임의 결과에 전혀 영향을 끼치 않고, 단지 연출에만 영향을 끼치기 때문에 이 테크닉을 사용하기로 하였습니다. (서버 부담을 줄여달라는 서버쪽의 간절한 요청 때문에.. 아흑..OTL)

 

일반적으로 랜덤 함수라면 C++ 표준 rand() 함수를 사용하게 됩니다. 뭐.. 일반적인 랜덤값을 사용하는 경우에는 사실 이 표준 함수를 사용해도, 별 문제는 없습니다. ^^; 하지만 위와 같은 테크닉을 사용할 때는 rand() 함수를 사용하면 안됩니다!

왜냐하면, C++의 표준 rand() 함수는 아래와 같은 약간의 문제점을 가지고 있습니다.

rand() 함수의 분포는 그리 고르지 않다. 특히 작은 표본을 사용할때는 더욱 그렇다.  즉, 이말은 1~10까지 랜덤을 1억번쯤 돌리면, 확률이 다들 비슷하게 나오긴 하지만, 10번 정도만 돌릴때에는 1 하나만 10번이 나온다거나 하는 가능성이 있다는 것입니다.   rand() 함수는 전역 함수이다. 어디서든 사용이 가능하다 이 함수는 표준 함수이기 때문에, 코드의 어디에서도 호출이 가능합니다. 그래서 호출 되는 경우를 제어할 수 가 없습니다.

 

< 즉 이런 기적의 확률이 나올수도 있는거임.. ㅠ.ㅠ >

 

저의 경우에 문제가 되는 것은 1번이 아니라, 2번입니다. 같은 랜덤 시드값으로 서로 다른 클라이언트에서, 싱크를 맞추기 위해서는 랜덤 호출 횟수가 정확히(!) 일치하여야 합니다! 내가 랜덤함수를 5번 호출했으면, 상대방도 5번 호출해야 같은 결과 값이 나와서 싱크가 일치하게 됩니다.

그런데 만약? 내가 작성한 코드가 아니라 어딘가 다른 코드에서 그것도 한쪽 클라이언트에서만 그 사이에 rand()를 호출하게 되면 어떻게 될까요? 넵. 당연히 그 다음부터는 모든 싱크가 아작이 나게됩니다…(그리고 이 경우에는 어디서부터 문제가 발생 했는지 찾는 것도 거의 불가능)

전역 함수라는 특징 때문에, 어디서 어떻게 불리울지 모르기 때문에, 언제 호출 횟수가 어긋날지 모른다는 문제가 발생하기 때문에, 랜덤 시드로 씽크를 맞추는 이 테크닉에서는 rand() 함수를 사용하는 것은 불가능 합니다. (내 코드에서는 절대 그럴리가 없어! 라고 해도… 다른 사람이 작성한 코드에서 과연 부르지 않는다는 보장이 있을까요…)

 

그래서 따로 랜덤 생성 클래스를 만들어 사용하게 됩니다. 랜덤 클래스를 만들고 그 인스턴스만을 사용하게 되면, 호출 횟수가 어긋나는 문제를 해결할 수 있으니까요. ^^

저의 경우가 바로 이런 경우라서, 랜덤 생성 알고리즘을 한번 찾아 봤습니다. 랜덤 생성 알고리즘은 "난수 생성기(Random Number Generator)", 혹은 "의사 난수 생성기" 등으로 불리웁니다. (그냥 저는 편의를 위해.. 이후 '랜덤 생성기'라고 칭하겠습니다. 이게 걍 편해요…)

 

이렇게 따로 랜덤 생성기를 이용해서, 랜덤 생성 클래스를 만들어 사용하면, 위와 같이 코드의 다른곳에서 랜덤값이 불리우는 경우를 제어할 수 있습니다. 물론 그렇다고 랜덤 생성 알고리즘을 혼자 고급 수학책이나 물리책 펴놓고 만들어서 쓰라는 이야기는 아닙니다. 친절하게도 이런 알고리즘은 전문 수학자 분들이 편하게 갖다 쓸수 있도록 편하고도 멋지게 만들어 두었습니다. (아이구~ 이런 감사할때가….)

 

이런 랜덤 생성기중에서 가장 유명하고 널리 쓰이는 알고리즘이 바로 [메르센 트위스터(MT.Mersenne Twister)]와 [WELL]이라는 랜덤 생성기입니다.

그리고 이 랜덤 생성기들은 위와 같은 테크닉에 사용할 수 있는 용도 외에도 다음과 같은 뛰어난 장점들을 가지고 있습니다

표준 함수보다 랜덤 분포가 훨씬 고르다 표준 함수의 경우 2^32승의 period를 가지는데 반해, MT의 경우는 2^19937-1를 가집니다. 그리고 623차원까지 동일분포 되어 있습니다. (자세한건 아래 링크 참조)   표준 함수보다 훨씬 속도가 빠르다. MT의 경우에 비트 연산만으로 구현되어 있어서, 표준 rand()보다 약 4배가 빠르다고 합니다. 그리고 WELL 같은 경우에는 MT보다 40%가 더 빠르다고 합니다.

 

 

메르센 트위스터 위키백과, 우리 모두의 백과사전. 메르센 트위스터(Mersenne Twister)는 1997년에 마츠모토 마코토(松本 眞)와 니시무라 다쿠지(西村拓士)가 개발한 유사난수 생성기이다.[1] 메르센 트위스터는 동일한 저자들이 개발한 TT800 생성기의 개선판으로, 기존 생성기들의 문제점들을 피하면서 매우 질이 좋은 난수를 빠르게 생성할 수 있도록 설계되었다. 메르센 트위스터의 이름은 난수의 반복 주기가 메르센 소수인 데에서 유래했다. 메르센 트위스터는 그 속도와 난수의 품질 때문에 점점 많은 곳에서 채택되고 있으며, 흔히 주기가 219937 − 1인 MT19937을 사용한다. MT19937과 같으나 생성해 내는 난수가 32비트가 아닌 64비트인MT19937-64도 쓰이며, 2006년에 동일한 저자들이 발표한 SIMD 기반 메르센 트위스터는 MT19937에 비해 대략두 배 정도 빠른 것으로 알려져 있다. 난수의 품질에도 불구하고, 메르센 트위스터는 암호학적으로 안전한 유사난수 생성기가 아니다. 즉 난수의 특성(주기, 난수 범위)을 알고 있을 때 유한한 수의 난수(이 경우 624개)만으로 현재 생성기의 상태를 알아 낼 수 있으며, 그 뒤에 나올 난수를 예측해 낼 수 있다. 암호학적으로안전한 유사난수 생성기를 얻기 위해서는 해시 함수를 사용해야 하지만 난수의 생성 속도가 낮아진다. 또는 블룸 블룸 슙(BBS)과 같이 암호학적으로 안전하게 설계된 생성기를 쓸 수도 있다.   < 출처 : 위키피디아 >

 

메르센 트위스터는 현재도 가장 널리 사용되고 있는 랜덤 생성기입니다. C++에서는 Boost에도 이 MT 랜덤 생성기가 구현 되어 있습니다. 또한 MATLAB, Ruby, Python등의 언어에서도 기본 난수 알고리즘으로 채택되어서 사용 되고 있습니다. 뭐 물론 단점이 없는 건 아니지만, 장점이 훨씬 더 크기 때문에 표준으로 채택이 되었겠죠. ^^

그리고 가장 큰 장점은 특별히 따로 구현하지 않아도, Boost에 포함되어 있기 때문에, Boost만 있다면 바로 사용이 가능하다는 장점이 있습니다. 사용 방법에 관해서는 하단의 참조 링크에서 확인하실 수 있습니다.

 

WELL

WELL은 위 MT의 디자이너가 10년후에 고안한 난수 발생 알고리즘 입니다. 그의 주장에 따르면 MT보다 40% 빠르고 코드도 더 간단합니다. WELL은 분포도에 따라서 WELL512, WELL1024, WELL19947, WELL44497의 종류가 있습니다. 숫자가 클수록 분포도가 높긴 하지만, 게임에서 사용하기엔 512나 1024만으로도 충분할 것 같습니다.

WELL의 구현 코드는 이곳에서 받을 수 있습니다. 실제로 보면 정말 구현은 간단합니다.

아래가 WELL512의 구현 코드입니다.

이게 다입니다. Period는 이름 그대로 2^512입니다. 그렇다 해도 일반 PC로 저걸 세는데 10^100년이 걸린다고 하는군요. 초나 분이 아니라 년 말입니다. (googol years라고 부른다고 하는군요)

사용법은 위의 state만 적절히 초기화 해주고, 함수를 호출하면 32비트 정수(난수)가 리턴됩니다.

 

간단한 시물레이터로 두 난수 발생기를 시뮬레이팅 해 보았을 때의 차이를 보여드리겠습니다.

C/C++의 rand함수

WELL512 알고리즘

 

<이미지 출처 : binsoo Blog >

 

일반적으로 게임 개발할때는 이런 랜덤 생성기까지 필요 하지 않을지도 모릅니다. 그러나 MMORPG와 같이 랜덤이 게임의 밸런스에 큰 영향을 끼치는 경우에는, 서버 측에서 이런 고성능의 랜덤 생성기가 필요한 경우가 많습니다. 유저나 해커가 랜덤값을 함부로 예측해서는 안되니까요. ^^; 그리고 저의 경우 처럼 랜덤 시드를 이용해서 이벤트 동기화를 맞추는 경우에는 전역 함수인 rand()를 사용할 수 없기 때문에 꼭 이런 랜덤 함수가 별도로 필요합니다. 그런 경우에 굳이 이런 좋은 난수 알고리즘들을 놔두고 새로 짜는 고생은 안하는게 낫겠죠.(그렇다고 내가 만든 알고리즘이 저것보다 좋을리는 택도 없을 테니…=ㅅ=;)

 

< 참고 자료 > 위키피디아 : 메르센 트위스터 [한글] Generating random numbers in game.[한글] Boost 라이브러리의 랜덤 함수 이용 [한글] WELL Random number generator [영문] Random Number Generation [영문]