한국어

EDPS

Random number와 가중치를 고려한 추첨기능 구현하기

이 글이 작성된 해는 2014년도입니다. 
유행하고 있는 추천서비스 등과는 관련이 없는 내용이고 개인적인 필요에 의해서 뭔가 실험하고 작성한 내용이에요. 방문자가 별로 없는 블로그이지만 검색 등을 통한 이 글로의 유입량이 많아서 혹시 오해가 있을까하여 미리 밝혀둡니다.


복수의 아이템이 들어있는 자료구조에서 추첨을 해야하는 경우가 있다. 보통 추첨을 한다하면 무작위로 선택되어야 하는데 때에 따라서는 특정 아이템의 선택 확률을 높여야 할 수도 있다.

 

언어에 따라 조금 차이가 있기는 하지만 보통 random number 생성에 관계된 API들은 수학과 관련된 package로 묶여 있거나 연산에 특화된 기능들끼리 모여있다. 따라서 단순 random number 생성 이외의 기능, 가중치를 고려하는 부분은 직접 구현할 수 밖에 없다. 또는 가중치 고려가 가능하게 만들어진 오픈소스 라이브러리가 있을지도 모르겠는데 그리 복잡하지 않을 것 같아 직접 구현하기로 했다.

 

1. 가중치를 통해 선택확률 높이기

아래의 그림을 보면 윗 부분은 가중치가 1로 동일한 상태이고 아래는 특정 아이템에 가중치를 더 높임으로써 선택될 확률을 높인 상태이다. 칸으로 구별된 bar를 다루게 될 아이템이 담겨있는 자료구조로 보자. 각 칸에는 하나의 아이템이 담겨있고 좌측을 시작으로 우측으로 갈 수록 index가 높다고 하자.
random_weight-900x864.jpg



 

이렇게 하는 것이 어떻게 선택될 확률을 높일 수 있을까?

Java를 기준으로 random number 생성을 살펴보면 단순히 Math.random() 호출시 0과 1사이에 있는 double 값을 생성해서 돌려주게 되어있다. (정확히 0.0 이상 1.0 미만의 값) Random number의 range를 0 ~ total weight로 설정하면 위 그림의 bar 상단에서 좌측에서 우측으로 증가하는 1차원 그래프를 상상해볼 수 있다. 즉 생성된 random number 가 찍히는 점의 아래에 있는 아이템이 선택될 수 있다.

Weight가 동일한 경우는 그래프에서 차지하는 영역이 동일하기 때문에 random number가 동일한 확률로 생성된다면 아이템이 선택될 확률도 동일하다고 볼 수 있다. 반면에 특정 아이템의 weight가 높은 경우 차지하는 영역이 넓어지기 때문에 그만큼 그 영역안에서 random number가 생성될 가능성이 다른 영역에 비하면 높아진다.

 

2. 그렇다면 구현은 어떻게 할까?

위 그림과 그래프를 상상해보면 구현은 간단하다. 각 아이템이 갖는 가중치를 모두 더해서 Math.random() 등으로 random number를 생성할 때 0부터 가중치합 사이의 값이 생성되도록 한다. (역시 언어에 따라 다르지만 random number 생성시 seed 값을 설정할 수 있어야 random number 생성의 중복을 방지할 수 있다. Java의 경우 Math 보다는 Random class를 사용하는게 나을 것으로 판단됨) 그렇게 생성된 random number를 가지고 자료구조에서 index를 증가시키며 각각의 아이템이 가진 가중치를 뺀다. (가중치를 빼지 않고 더해서 하는 방법도 있을텐데 그 경우 random number와의 비교구문이 약간 달라져야 할 것이다) 그렇게 진행하다보면 어느 순간 random number가 0이나 음수가 되는데 그 때의 아이템이 가중치에 따라 선택된 아이템이 된다. Pseudo code로 간단하게 작성하면 아래와 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
List<Item> list = getItemList();
 
double total = getTotalWeight(list);
 
for(int i = 0; i < list.size(); i++) {
 
total -= list.get(i).getWeight();
 
if(total <= 0) {
 
selectedIndex = i;
 
break;
 
}
 
}
 
return list.get(selectedIndex);



펌] https://blurblah.net/1126


WindBoy

2018.06.05 14:15:37
*.131.141.124

당연히 데차 개발은 안하고 다른 게임 개발하는 개발자다. 포지션은 프로그래머.

 

그냥 게임 전체가 뽑기에 의존이는 이런 게임에서 확률은 굉장히 민감한 문제다.

 

근데 개발자나 유저나 다 본질은 전혀 이해하지 못하고 온갖 추측과 잘못된 정보가 난무하더군.

 

아래 수학과가 뭐 확률조작 어쩌구 하는데 읽어보니 개발은 1% 도 못해본 탁상공론에 불과해.

 

 1. 컴퓨터는  랜덤이라는 기능이 물리적으로 불과하다.

  컴퓨터는 결국 단순한 계산기야.  CPU 는 연산을 위한 회로가 집적되어 있고 이걸 케쉬와 커맨드셋등으로

 효율적으로 제어하는 기계에 불과해.  프로그래밍 코드를 밑바닥까지 쪼개고 쪼개면 결국 더하기 빼기의

2진 연산 기계코드로 분해된다. 이런 구조에서 통계학이 말하는 완전한 무작위 값을 뽑아내는건 불가능하다.

통계는 실수고 컴퓨터는 정수만 처리할 수 있기 때문이다. 그럼 소수점 붙어있는 실수는 어떻게 처리하냐고?

부동 소수점 연산기라고 CPU에 붙어 있는녀석이 있는데 이놈이 알아서 연산하는거다. 여기서 실수를 정수(2진 신호)

로 변환해서 처리해준다. 때문에 0.001 을 표현하는 방법은 장치마다 다를 수 있다. 휴대폰은 0.001231라고 인식하는데

똑같은 값을  PC 에서 0.001232라고 인식하는거다. 자세한 데이터는 컴공 교수님에게 가서 물어보시고..

 

그래서 세상에 나와있는 모든 랜덤값들은 그럴싸한 알고리즘에 의해 산출된 가상 값에 불가하다. 1.44% 를 정확하게

뽑을 수 있는 방법은 없다.

 

2. 그럼 랜덤값은 어떻게 산출되나?

 모든 랜덤값은 Seed  값을 바탕으로 수학 알고리즘(당연히 정수계, 실수는 안됨)을 이용하여 난수화 과정을 거친다.

난수화 알고리즘의 성능은 표준분포가 좋은 것들이 몇개 쓰이고 있다. 즉 알고리즘을 사용해서 좌표를 생성했을때

편향되지 않고 고르게 찍히는게 가장 효율이 좋은거다.  고르게 분포할 수록 무작위로 생성되는 것처럼 보이지만

실제로  Seed  에 의해 연산된 예측 가능 숫자다. 즉 랜덤이 아니라는 거지.

 

 그래서 특정 시간대에 뽑기가 잘된다는 도시전설이 존재하는거다. 그냥 풍문이 아니라 사실은 굉장히 그럴싸한

경험적 결과지. 시간에 따라 뽑기에 사용할 난수를 얻기 때문에 알고리즘에 따라, 혹은 서버의 장비의 특성에 따라

특정 시간에 당첨 확률이 높아질 수 있다. 물론 재대로 코딩하면 거의 느끼기 힘들지만.... 프로그래머가 과연 그런 전문

지식이 있을까나?

 

3. 랜덤처럼 보이기 위한 장치

 랜덤은 예측이 불가능해야 의미가 있기 때문에 대부분의 컴퓨터는 CPU의 클럭 카운트(동작 횟수)를  Seed로 사용해서

난수를 추출하고 있다. 당연히 해당 컴퓨터의  CPU 를 물리적으로 확보하고 알고리즘을 분석해보면 1.44%가 맞는지

아닌지 조작이 있는지 없는지, 실제 당신이 언제 뽑기를 하면 당첨될지 다 알수가 있다.

 

 그런데 그건 현실에서 절대 불가능하겠지.  CPU의 동작횟수는 인간이 인지하기도 힘들정도로 빠르고 알고리즘을

분석하고 의미있는 데이터를 추출할려면 꾀나 전문적인 장비가 필요하거든.  그래서 결국 랜덤에 무척 가까운 값을

도출할 수 있다. 그냥 랜덤이라고 믿으면 된다.

 

4. 확률사고에 대한 이야기

 이미 이렇게 답이 있는데 왜 세상에는 끊임없이 확률 사고가 터질까?  그냥 확률스크립트를 조작하는건 그냥 범죄라서

쉽게 수사가 가능하니까 논외로 하자.  실제로 난수로부터 실제 판정에 사용할 값을 추출하는 과정에 대한 프로그래머의

이해가 없어서 이런 사고가 터지는거다. 즉 이론적으로 랜덤값을 추출한다고 해도 이걸 데차 시스템에서 사용하는

값으로 변환 하는 과정에서 표준분포가 소실되는 경우가 굉장히 많다.  대부분 확률은 만분률값은 정수로 변환하게 되는데 1.44%면  난수로 부터 0 ~ 9999까지의 값을 추출한다음 값이 144 미만이면 당첨 이런식으로 코드를 짜게 된다.

즉 프로그래머 개개인의 이해 정도에 따라 실제 적용값은 달라질 수 있다. 위에 예는 만분률을 사용한것으로 1.44% 이하는 버려지기 때문에  0.001%의 오차는 올리거나 내림함으로써 실제 적용 확률에 오차가 발생할 수 있다. 

 

 이 경우 확보한 난수값 자체는 문제가 없기 때문에 프로그래머는 "정상작동 하고 있다" 라고 믿고 우기게 된다. 우기니까

회사도 공지로 문제 없다고 우기는 거다.

 

실제로 시스템에서 뽑기를 100만번 정도 해서 일일이 그래프에 찍어보면 어딘가 뭉치거나 퍼지거나 하는 경우가 많다.

이 경우 변수로는  1.44% 를 줘도 실제 처리 결과는 3%가 넘거나 (자주 뽑힘) 0.1%미만으로(죽어라 뽑아도 안 뽑힘)

나오기 때문에 알아차리기가 매우 어렵다. 대부분의 프로그래머가 확률에 대한 이해가 없고 그냥 대충 어디 구글링한

검증안된 코드를 그냥 넣는 경우가 굉장히 많거든. 알고리즘에 대한 검증이나 시뮬레이션 할만한 고급 프로그래머와

그런데 드는 비용을 과연 데차가 가지고 있을까?

 

만약 문제가 발견된다면? 코드 몇줄 바꿔서 확률을 바꾸고 조용히 넘어가게 된다. 괜히 설레발치면 바로 소송걸리고

난리가 나니까 슬쩍 수정하는거지. 경찰이 압수수색을 해서 코드 업데이트 로그 내용을 확보하지 못하면 절때

문제가 없으니까. 설마 조막만한 게임 회사를 무슨 대기업 압수수색하듯 뒤집을 수 있을 거라고는 생각하지 않겠지?

게다가 그냥 유저들이 게시판에 확률이 이상하다 난리친 것 가지고?

 

 

 

5. 한줄요약

  - 스크립트가 조작되면 그냥 범죄.

  - 프로그래머가 삐리해서 코드를 잘못짜서 적용이 다르게 나오는 현상일 경우 답 없음

  - 확률적용이 문제가 있더라도 개발자가 알아차리기 힘들며 몰래 고치고 우기면 답없음(내부 기밀이라 노출안됨)

  - 걍 묵묵히 돈 바치고 뽑뽑뽑 하는게 답 어짜피 당신만 잘못된 확률을 적용받는게 아니라 공평하게 적용되기

    때문에 가치는 변하지 않음. 오히려 정상으로 만들어서 가치가 내려가거나 올라가는게 더 짜증날것이다.

 

6. 뽑기가 그냥 게임인 몇몇 게임, 프야매 같은거 말야. 확률가지고 장난 많이 친다. 그걸로 매출을 일구는 경우도

  많고. 뽑기 확률이 매출에 매우 민감하기 때문이며 알기가 매우 힘들기 때문에 수시로 일어난다.  0.0001%확률로

 레전드가 나오는데 몇달이 지나도 안나오면 흥미를 잃기 때문에 적당히 한달에 한번은 떠서 난리가 나게 하는 경우도

있음. 이런거 막겠다고 정치권에서 확률공개 하라고 했지만 개발사가 시스템을 소유하는데 그게 재대로 될리가

없겠지? 

 

그런거 알고 나면 뽑기에 월급과 재산을 쏟아붙는 일은 굉장히 꺼려질거다.


펌] http://www.inven.co.kr/board/dchild/4577/13880?category=%EC%A0%95%EB%B3%B4

List of Articles
번호 제목 글쓴이 날짜 조회 수
399 기획자는 결국 사업을 만들어내는 사람이다. 수텐리 2019-09-18 15
398 크롬 OS를 설치하기 수텐리 2019-07-11 31
397 직급별 영어명칭 [1] 수텐리 2019-06-04 325
396 PV, UV란 수텐리 2018-08-28 77
395 HTML Error Code 수텐리 2018-08-28 70
394 QA=테스트라는 잘못된 인식이 불러온 오해 (2) 수텐리 2018-08-14 43
393 QA=테스트라는 잘못된 인식이 불러온 오해 (1) 수텐리 2018-08-14 57
392 버전(Version)을 제대로 이해하기 수텐리 2018-07-30 22
391 MSSQL에서 SELECT 시에 WITH (NOLOCK) 수텐리 2018-07-20 85
390 노트북 배터리 성능 테스트 WindBoy 2018-06-26 234
» Random number와 가중치를 고려한 추첨기능 구현하기 file [1] WindBoy 2018-06-05 430
388 개발 표준 정의서 [1] 수텐리 2018-04-20 1098
387 푸른세상티엔에스 WindBoy 2017-09-27 85
386 Linux 명령어 관리 WindBoy 2017-08-24 185
385 JSON과 JSONP 차이점 [1] WindBoy 2017-03-29 948
384 XP에서 ie8 res://ieframe.dll/acr_error.htm 오류 file WindBoy 2016-08-26 110
383 HP Officejet Pro 8610 한글화 작업 WindBoy 2016-06-01 1676
382 excel TIP WindBoy 2016-05-10 27
381 PC의 공인인증서 위치 admin 2016-03-14 324
380 마케팅 자료 WindBoy 2015-12-05 36