이번 겨울 Winter Extreme 이벤트에서는 1만 실버에 눈사람(상자)을, 5만 실버에 당근(열쇠)을 각각 사거나 999 골드로 상자를 사서 하나 까면 랜덤한 보상이 나오는 행사가 진행되었다.
여기, 어떤 가붕이가 6천만 은사자를 벌어서 상자깡에 꼴아박기로 했고, 상자에서 나올 수 있는 가장 가치 있는 보상을 하나 얻으면 그만두기로 했다. 물론 가장 가치 있는 보상이라는 기준은 사람에 따라 주관적인 기준이 적용되지만, 이 가붕이는 상자깡을 통해 얻은 장비나 장식물을 가이진 마켓에 내다팔아 가이진 코인을 한번에 최대한 많이 벌어들이고자 한다. 기준에 따라 최고가가 아닌 보상은 전부 까서 자신이 써버릴 것이므로 가이진 코인을 벌어들이지 못한다. 여기에 더해 한 번 가이진 마켓에 매물로 내놓은 장비는 다시 회수할 수 없으며, 상자에서 나오는 보상은 전부 랜덤이고 완전히 똑같은 보상은 두 번 다시 나오지 않는다고 가정해보자.
그렇다면 이 가붕이는 자신이 얻을 수 있는 것 중 가장 가치 있는 보상을 내다팔기 위해 1000번의 상자깡 기회 중 얼마를 날려버린 후에 최고가의 기준을 결정해야 실버 라이온을 절약하면서도 가이진 코인을 많이 얻을 수 있을까?
예를 들어, 운 좋게 10번째에 90코인짜리 A 전차를 얻었다면 실라를 좀 더 꼴아박아서 그보다 높은 가격의 장비에 도전하는 것이 유리하겠지만, 만약 운이 더럽게 안 좋아서 가이진 마켓에서 팔 수 없는 부스터 따위만 주구장창 나오다가 990번째가 돼서야 A 장비가 떴다면 그냥 그걸 팔아버리고 상자깡을 때려치는 게 인게임 지갑 사정에 좋을 테니까 말이다.
고등학교 수준의 미적분과 확률과 통계를 이용해 이 문제를 해결해 보자.
여기 n번의 기회가 있다. 이 글에 나온 가붕이의 경우 n = 1000으로 알려진 값이다. 각 보상에 걸린 조건은 앞서 전부 설명했으므로 생략하고, 여기서 중요한 가이진 코인 가치는 순서를 매길 수 있다는 점에 주목하자. 여기서 r-1번째까지는 아무리 가치 있는 보상이 나와도 바로 까서 써버리고, r번째 이후에 나오는 보상 중 r-1번째까지 나온 최고가 보상 이상의 가격를 가진 물건을 팔아야 한다. 즉, 여기서 기준이 되는 상자깡 횟수는 임의의 수 r이다.
이제 기준점 r이 정해졌을 때, 상자깡에서 최고가의 보상이 나왔고 이걸 가이진 마켓에 팔기로 결정할 확률 Pr(r)이라고 하자. Pr(r)은 1번째부터 n번째 상자깡까지 각각의 실행에서 상자깡 보상이 최고가라서 가이진 마켓에 판매할 수 있을 확률을 모두 더한 값이다. 따라서 조건부 확률의 정의에 의해 다음과 같은 식으로 표현할 수 있다.
하지만 우리는 1번째부터 r-1번째 상자깡까지 나온 보상은 의도적으로 판매하지 않고 까버리기로 했으므로, i = 1부터 i = r-1까지 i번째 상자깡 보상을 판매할 확률은 보상의 가격이 어떻든 무조건 0이다. 또한, n번의 상자깡에서 같은 장비는 절대로 나오지 않는다고 했으므로, 최고가는 무조건 1번만 나올 수 있다. 따라서 i번째 상자깡 보상이 최고가일 확률은 항상 1/n이다. 이를 고려하여 Pr(r)을 다시 나타내면 다음과 같다.
그런데 우리는 r번째 이후로 팔 수 있는 보상은 r-1번째 상자깡 이전에 나온 보상보다 높은 가격이어야 한다고 정했다. 이 말은 i-1번째 상자깡까지 가장 높은 가격을 가진 보상은 일부러 까버렸던 r-1번의 상자깡 보상 중에 있었어야 한다는 뜻이다.
당연하지만, i번째 상자깡에서 최고가가 뜨는 것이 확정되면 i-1번째까지의 상자깡 보상에서 2번째로 비싼 물건이 언제 뜰지에는 아무런 영향을 미치지 않는다. 다시 말해 'i-1번째 상자깡 보상 중 최고가는 r-1번째까지의 상자깡 보상 중에 있는 사건'과 'i번째 상자깡 보상이 최고가인 사건'은 서로 독립이므로 조건부 확률 기호 | 오른쪽에 있는 내용을 무시할 수 있게 된다. 그리고 i-1번의 상자깡 보상 중 최고가는 오직 1번 뿐인데, 이것이 i-1번 중 r-1번째까지에 속할 확률은 단순히 (r-1)/(i-1)이다. 따라서 여태 길게 설명한 Pr(r)은 다음과 같이 간단히 정리된다.
이걸 계산하면 되긴 하는데, 문제가 있다. n = 1000으로 정말 큰 값이라서 최적의 r을 찾으려면 1000번의 노가다를 통해 Pr(r)이 최대가 되는 r을 일일이 찾아야 한다. 이건 매우 골치아프고 좆같은 노가다이므로 가붕이들이 모두 학을 뗄 것이다.
이런 노가다를 줄여주는 것이 바로 미적분이다. 물론 약간의 근사 과정을 거치긴 해야 하지만 1000번 노가다 뛰는 것보단 나으니까 한번 살펴보자.
n의 값이 충분히, 아니 존나게 크다고 하면 전체 기회 n번 대비 버리는 기회 r-1번의 비율, 즉 (r-1)/n의 값이 연속적인 값을 가진다고 근사할 수 있다. 이 비율 (r-1)/n = x라고 해보자. 간단한 곱셈과 나눗셈과 극한을 통해 다음과 같이 이산확률분포인 Pr(r)을 연속확률분포 Pr(x)로 근사할 수 있다.
고등학교 미적분을 성실히 들은 사람은 lim과 Σ가 같이 나오는 것에서 왠지 모르게 ∫로 바꾸고 싶은 충동이 든다.
따라서
이게 노가다 줄이는 거랑 뭔 상관이냐 싶겠지만 우리는 어차피 Pr(x)가 최대가 되는 x를 찾는 것이 목표가 아닌가? 마침 x ln x는 0<x<1 구간에서 미분 가능한 함수이므로 여기서 미분 한 번만 하면 극댓값이자 최댓값이 나오는 x를 구할 수 있다.
그런 x = 1/e = 0.367879...가 나온다.
따라서 이 가붕이는 1000번의 상자깡을 한다면 367번째까지는 뭐가 나오든 일단 다 까버리고 이후에 나오는 보상 중 여태까지 가장 비싼 물건이 뜨면 곧바로 가이진 마켓에 팔아버린 후 상자깡을 때려치는 것이 가장 효율적이라는 계산이 나온다.
이 문제는 사실 '비서 문제(Secretary Problem)'라고 불리는 문제로, 가장 좋은 비서를 얻기 위해 사장님들이 처음 몇 명은 일부러 탈락시키되 초반 탈락자 중 최고점을 기억해뒀다가 이후에 그 기준을 넘어가는 후보가 나오면 곧바로 채용하여 실패 확률을 줄인다는 가상의 에피소드에서 탄생한 문제다.
n이 어떤 값이든 대략 36.8%까지는 존버타다 그 이후 여태까지 가장 좋은 물건이 나타나면 붙잡는다는 전략은 결혼 시장이나 부동산 거래 같은 문제에 적용할 수도 있다고 하는데 둘 다 모쏠아다 월급쟁이 가붕이들에게는 별 쓸모 없는 이야기이므로 게임 이야기도 할 겸 워 썬더에 적용해 보았다.
참고로 필자는 이 최적 정지 이론을 이용해 실라깡을 굴렸는데 처음 10번 연속 부스터만 나와서 곧바로 때려쳤다.
참고 자료
채널운영