[기술컬럼] 여러 숫자들 중에서 확률적으로 선택하기

게임 서비스를 만들다 보면 몇 가지 선택지 중에서 하나 혹은 여러 개를 일정 조건에 따라서 골라야하는 작업이 많습니 다. 예를 들어서 다음과 같은 것들이 있습니다.

  • 게임의 한 단계를 완료한 후 몇 가지 보상 중에 하나를 제공
  • 일별 퀘스트 목록 중에 일부를 임의로 골라서 주기

실제로는 이런 기능을 구현할 때 단순히 여러 개 중에 균일한 확률로 고르는 경우는 많지 않습니다.

  • 여러 개의 선택지가 서로 다른 확률로 고릅니다.
  • 하나의 선택지가 중복해서 나올 수도 있고, 중복을 허용하지 않을 수도 있습니다.

이런 기능을 게임 서버에서는 어떻게 구현하면 좋을까요? 우선 게임 서버가 일반적인 클라이언트 앱이나 프로그램과 다른 부분을 생각해봅시다. 게임 서버는 여러 유저에 대한 처리가 동시에 이뤄집니다. 이로 인해 자원에 제약이 있습니다. 이 상황에서,

  • 가능한한 빠른 시간 안에 응답해야 합니다.
  • 최대한 많은 수의 유저 요청을 처리해야 합니다.

그래서 다음과 같은 부분이 서버 구현에선 권장됩니다.

  • 선택하는 일이 일정 시간 안에 결정론적으로 끝날 것. 여러 유저의 요청을 동시에 처리하기 때문에 시간을 예측 할 수 없다면 응답 시간을 보장하기 힘듭니다.
  • 선택 과정이나 선택을 위한 자료 구조의 메모리 사용량을 최소화 할 것. 그래야 여러 명의 유저를 처리할 수 있 습니다.

이 부분을 염두에 두고 확률적으로 선택하는 구현을 어떻게 할지 설명합니다.

 

문제 정의

선택지가 n개 있고, 각각 특정 가중치로 선택하는 문제를 생각해보겠습니다. C++ 코드로 표현한다면 아래와 같은 클 래스로 나타낼 수 있습니다.

1

예를 들어, 네 개의 아이템 0, 1, 2, 3을 각각 15, 25, 59, 1 의 비율로 선택하는 것을 생각해보겠습니다. (편의상 백분 위 확률이 되게 숫자를 선택했습니다)

2

위와 같은 빈도수 테이블로 이런 내용을 표현할 수 있습니다.

 

중복을 허용하는 선택하기

MMORPG 에서 필드의 특정 몬스터를 처치할 때마다 아이템을 준다고 해봅시다. 아주 간단하게, 하나의 아이템만 준 다고할 때, 몬스터 종류 별로 위와 같은 테이블을 하나씩 지정해둘 수 있습니다. 여기서 실제로 아이템을 선택하는 코 드를 만들어봅시다.

쉽게 생각하면 아래처럼 구현해볼 수 있습니다.

  • 가중치의 총합을 구합니다. 이 값을 W라고 하겠습니다.
  • 균일한 분포의 random 함수로 [1 .. W] 사이의 정수 k 를 하나 구합니다.
  • 테이블을 처음부터 하나씩 검사해서 가중치를 합산합니다. 이 때 합산 결과가 k 보다 같거나 커지는 순간의 id 를 반환합니다.

코드로 표현하면 아래와 같습니다.

3

혹은, 아래와 같이 전처리를 한 후에 이진 검색합니다.

4

대부분의 경우 아이템 확률 테이블은 충분히 크지 않기 때문에 전자와 후자는 속도차이가 거의/전혀 없습니다. (상황에 따라선 순차실행인 전자가 더 빠르기도 합니다)

 

중복을 허용하지 않는 경우

일일 퀘스트를 n개 중에 k개를 고르거나 할 때는 중복을 허용하지 않습니다. 이런 경우에는 어떻게 할까요?

쉬운 구현

쉽게 생각해서 구현하면, 다음과 같이 해볼 수 있습니다.

  • (위에서 언급한) 중복을 허용하는 선택 알고리즘을 써서 하나를 고릅니다.
  • 선택한 알고리즘을 테이블에서 제거합니다.

이 과정을 반복해서 k개를 고르는 방식을 쓸 수 있습니다. 다만 이 경우 확률 테이블을 항상 새로 만들어야 합니다. (전 체 원소를 한 번씩 확인해야합니다)

혹은, 중복 검사를 위한 std::set 혹은 std::unordered_set 을 두고 아래와 같이 처리할 수 있습니다.

  • 중복을 허용하는 선택 알고리즘을 써서 하나를 고릅니다.
  • 해당 원소가 이미 나왔다면 재시도하고, 아니라면 중복 검사 집합에 넣습니다.
  • k개를 모두 선택했다면 종료합니다.

다만, 랜덤 알고리즘이 충분히 좋지 못하다면 해당 알고리즘의 종료 시간을 예측할 수 없는 문제가 있습니다. (대부분의 문제가 그렇듯, 현실에서 이 문제는 거의 나타나긴 어렵습니다.) 그리고 정렬이나 정규 표현식 처럼 유저가 악의적 으로 이용하기 쉽지도 않아서 큰 문제는 아닙니다.

실제 구현 예를 들자면 아래와 같습니다.

5.PNG

코드를 보면 실제 시행 시간이 하나 선택하는 것을 k번 하는 정도일 것이라 추측할 수 있습니다.

 

조금 복잡한 구현

실행 시간을 항상 예측할 수 있고 / 테이블을 새로 만들지 않는 방법이 가능할까요?

Efraimidis와 Spirakis가 2005년에 내놓은 Weighted Random Samping 알고리즘을 사용하면 가능합니다. 알고리즘 은 아래와 같이 동작합니다.

  • 각 선택지, 가중치에 대해서,
    • [0,  1] 사이에서 균일한 확률로 랜덤한 값 하나 획득
    • 해당 값을 1/가중치 만큼 제곱
  • 나온 값들을 내림차순으로 정렬
  • 앞의 k개를 선택

실제로 만들어보면 아래와 같습니다.6

이렇게 하면 k가 커져도 실행 시간이 늘어나지 않습니다. (그래서 k가 크다면 이쪽 알고리즘이 유리합니다) 그리고 이전 구현과 달리 테이블을 전처리하지 않아도 됩니다.

다만 이 구현은 부동 소숫점 연산 (나눗셈과 제곱, 제곱은 미리 할 수도 없습니다) 을 사용하고, 정렬도 해야해서 k가 작 다면 효율적이지 않습니다.

맺음말

게임 내에서 흔히 접할 수 있는 가중치에 따른 선택 알고리즘을 살펴봤습니다. 쉽게 생각할 수 있는 간단한 구현과, 조금 더 복잡한 구현에 대해서 살펴봤습니다.

게임 컨텐츠를 만들 때,

  • 사용하려는 테이블 크기
  • 중복 허용 여부
  • 선택할 아이템 수

같은 내용에 따라서 적당한 방식을 선택하고 성능을 확인하고 사용하시면 됩니다.

 

아이펀팩토리 김진욱 CTO 

답글 남기기

댓글을 게시하려면 다음의 방법 중 하나를 사용하여 로그인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중