📌 모듈러 편향 (Modulo Bias)
올해 4월 9일, 메이플스토리에서 진행한 Maple Now 생방송에서 아이템 드롭률과 관련하여 확률 오류 문제가 발생했다는 것을 공개했다. 해당 확률 오류는 모듈러 편향이 원인으로 지목되었고, 이를 유저들에게 설명하기 위해 라이브 방송에서 모듈러 편향에 대해 설명을 하는 일이 발생했었다.
취업 준비를 진행하면서 메이플스토리도 조금씩 플레이하던 사람으로서 해당 라이브 방송을 시청했었고, 나머지 연산을 통해 확률을 구현하는 경우 모든 구간의 확률이 동일하지 않다는 것을 알고 있었지만 지식이 파편화되어있는 느낌을 받았기 때문에 메이플스토리 라이브를 활용하여 이번 포스트에서 파편화된 지식을 한군데에 모아보려고 한다.
💡 모듈러 편향이 발생하는 원인?
32비트 환경에서 난수 생성기가 생성할 수 있는 난수는 총 232 = 4,294,967,296개이다.
메이플스토리는 해당 난수를 10진법을 활용하여 직관적으로 표현하기 위해 10억으로 나눈 나머지 값을 활용하는 방식을 사용하였다.
즉, 아이템 드롭률이 1%인 아이템은 0부터 9,999,999 사이의 숫자가 나오는 경우 드롭되는 것이다.
하지만 약 42억개의 모든 수를 10억으로 나머지 연산을 하였을 때 모든 수가 동일하게 나오지 않는다.
| 나머지 값 | 난수 값 | 난수 갯수 |
|---|---|---|
| 0 | 0, 1,000,000,000, 2,000,000,000, 3,000,000,000, 4,000,000,000 | 5개 |
| 1 | 1, 1,000,000,001, 2,000,000,001, 3,000,000,001, 4,000,000,001 | 5개 |
| ... | ... | ... |
| 294,967,296 | 294,967,296, 1,294,967,296, 2,294,967,296, 3,294,967,296, 4,294,967,296 | 5개 |
| 294,967,297 | 294,967,297, 1,294,967,297, 2,294,967,297, 3,294,967,297 | 4개 |
294,967,296 까지는 5개의 수의 나머지 연산을 통해 나올 수 있지만, 294,967,297 부터는 4,294,967,297이 32비트 정수 범위를 넘어가서 나오지 않기 때문에 총 4개의 수의 나머지 연산을 통해 나올 수 있다.
즉, 의도한 확률은 1천만 / 10억으로 1% 이지만, 5천만 / 42억 9천만으로 1.164% 로 아이템이 드롭되게 되고 있었던 것이다.
💡 모듈러 연산 활용 시 확률을 높이는 법
모듈러 연산을 활용하여 확률을 증가시키는 방법은 두가지가 있다.
- 난수 범위를 늘리는 방법
- 나머지에 사용되는 수를 줄이는 방법
메이플스토리는 2번의 방법을 써서 확률을 증가시켰다. 하지만 수를 줄이기 전 후 모두 1천만 이하의 수가 나오는 확률은 동일하고, 확률 증가폭이 더 늘어 나머지 연산을 했을 때 1천만 이하의 수가 나오는 횟수가 늘어야 확률이 늘어나는 오류가 발생하게 된 것이다.
예시에 활용된 숫자가 너무 커서 헷갈린다면 숫자를 줄인 예시도 라이브에서 친절하게 설명해줬으니 이것으로 이해해보도록 하자.
💡 모듈러 편향을 방지하는 방법?
모듈러 편향을 방지하는 법은 생각보다 간단하다. 42억 개의 난수 중 40억을 초과하는 수는 확률 계산에 사용하지 않고 버리면 된다. 42억 개의 난수 중 40억 개만을 사용하여 나머지 연산을 진행한다면 나머지 연산을 했을 때 나오는 모든 수가 동일하게 4번씩 나오게 되므로 특정 수가 더 많이 나오거나 적게 나오지 않고 균일한 확률을 보장받을 수 있게 된다. 이러한 방식을 거부 샘플링 (Rejection Sampling) 이라고 명칭한다고 한다.
Reference
2026년 4월 9일 Maple Now 라이브 스트리밍
모두가 이해하는 모듈러 편향: 메이플스토리를 중심으로
4월 9일 MAPLE NOW에서 공개된 메이플스토리 확률 로직 내 모듈러 편향 이슈
