넥슨이 서비스하는 「크레이지레이싱 카트라이더」는 제가 초등학생일 때부터 있었던 유구한 전통(?)의 온라인 게임입니다. 초등학생 때 부족한 실력이나마 이 게임을 열심히 즐긴 기억이 있습니다. 대학생 때 친구들과 술 한 잔 하고 PC방에서 함께 아이템전을 돌리던 추억도 새록새록 떠오릅니다. 요즘은 직접 플레이하지는 않지만, 유튜브에서 카트라이더 영상이 종종 추천되면 즐겨 시청하는 편입니다. 그 중에서도 형독방송 채널의 영상을 많이 시청하는데요. 저번 주에는 '디비디비딥'이라는 이름의 게임을 빠른 시간에 끝내는 미션을 수행하는 영상이 올라왔습니다.
영상에서 형독이 즐긴 '디비디비딥'은 다음과 같은 규칙을 갖습니다. 한 바퀴 트랙에서 일곱 명의 수비수(시청자)는 미리 자리를 잡습니다. 이후 술래(형독)는 수비수와 순서대로 '디비디비딥'을 진행합니다. 술래와 수비수가 할 수 있는 동작은 좌로 돌리기, 우로 돌리기, 가만히 있기 등 총 세 가지입니다. 만약 술래와 수비수가 다른 선택지를 고르면 술래는 다음 수비수에게 향합니다. 반대로 같은 선택지를 고르면 술래는 직전 수비수에게 향합니다. 이렇게 모든 수비수를 돌파하면 게임이 끝나게 됩니다.
재밌게 영상을 보던 중에 문득 이런 생각이 들었습니다. 수비수들의 목표는 술래가 가능한 늦게 결승선을 통과하도록 하는 것입니다. 시청자들이야 대부분 스트리머가 고통을 받을 때 희열을 느끼는 사람들이니 말이죠. 과연 수비수들이 어떻게 위치해 있어야 이 목표를 이룰 수 있을까요? 간단한 수학 문제라서 컴퓨터 과학과는 크게 연관이 있지는 않지만, 그래도 재미있는 결과라고 생각하여 포스팅해 봅니다.
위 게임을 다음과 같이 모델링하겠습니다. \(n\) 명의 수비수와 한 명의 술래가 게임에 참여합니다. 거리가 1인 트랙 위에 수비수들은 일렬로 자리를 잡습니다. 술래는 출발점부터 시작해 수비수들을 차례로 만나 디비디비딥을 진행합니다. 모든 \(i = 1, \cdots, n\)에 대해 술래가 \(i\) 번째 수비수를 만났을 때 \(p\)의 확률로 디비디비딥에서 진다고 하겠습니다. 이때는 이전 위치로 돌아가 \(i - 1\) 번째 수비수와 다시 디비디비딥을 진행합니다. 만약 \(i = 1\)이라면 출발점을 다시 찍고 오는 것이라고 가정하겠습니다. 반대로 \(1 - p\)의 확률로는 디비디비딥을 이기게 되며 다음 위치로 나아가 \(i + 1\) 번째 수비수와 디비디비딥을 합니다. 만약 \(i = n\)이라면 술래는 도착점까지 향하고 이대로 전체 게임이 끝납니다. 매번 술래와 수비수가 진행하는 디비디비딥은 확률적으로 독립(independent)을 이룬다고 가정하겠습니다. 우리의 목표는 술래가 이동하는 거리의 기댓값이 최대가 되도록 하는 수비수의 배치를 찾는 것입니다.
각 \(i = 1, \cdots, n - 1\)에 대해 \(x_i\)를 \(i\) 번째 수비수와 \(i + 1\) 번째 수비수 사이의 거리라고 정의하겠습니다. 비슷한 이치로 \(x_0\)는 출발점과 첫 번째 수비수 사이의 거리를, \(x_n\)은 마지막 수비수와 도착점까지의 거리를 나타낸다고 하겠습니다. 총 거리는 1이라고 하였으므로, \[x_0 + x_1 + \cdots + x_n = 1 \tag{1} \]을 만족합니다.
이제 \(i = 1, \cdots, n - 1\)에 대해 \(\rho_i\)를 술래가 언젠가 \(i\) 번째 수비수 위치에 있을 때 처음으로 \(i + 1\) 번째 수비수에게로 나아갈 때까지 이동한 거리의 기댓값이라고 하겠습니다. 비슷한 맥락으로 \(\rho_0\)는 출발점에서 처음으로 첫 번째 수비수의 위치까지 갈 때 이동한 거리의 기댓값, \(\rho_n\)은 마지막 수비수에서 처음으로 도착점까지 갈 때 이동한 거리의 기댓값으로 정의하겠습니다. 그러면 우리는 술래가 움직인 거리의 기댓값이 \[ \rho_0 + \rho_1 + \cdots + \rho_n \tag{2} \]으로 표현된다는 것을 알 수 있습니다. 그 이유는 다음과 같습니다. 술래가 게임을 끝내기 위해서는 먼저 출발점에서 첫 번째 수비수가 있는 곳으로 향해야 합니다. 그 거리는 평균적으로 \(\rho_0\)가 될 것입니다. 이후 첫 번째 수비수가 있는 곳에서 두 번째 수비수가 있는 곳까지 도달하기 위해서 가야하는 거리의 기댓값은 \(\rho_1\)이 됩니다. 같은 이치로 \(i\) 번째 수비수에 도착한 후 \(i+1\) 번째 수비수 위치(\(i = n\)이라면 도착점)까지 가는 거리의 기댓값은 \(\rho_i\)가 됩니다. 기댓값의 선형성(linearity of expectation)에 의해 총 거리의 기댓값은 식 2와 같이 이를 모두 더한 것과 같습니다.
이제 \(\rho_i\)를 분석해 보도록 하겠습니다. 먼저 \(\rho_0\)를 고려해 보겠습니다. 출발점에서 처음으로 첫 번째 수비수가 있는 장소까지는 바로 이동하므로 \[ \rho_0 = x_0 \]와 같습니다. 그럼 \(\rho_1\)은 어떻게 될까요? 다음의 경우로 나누어 생각해 보겠습니다.
- \(1-p\)의 확률로 바로 통과합니다. 이때 이동한 거리는 정확히 \(x_1\)입니다.
- \(p(1-p)\)의 확률로 한 번 출발점을 다녀옵니다. 이때 이동한 거리는 정확히 \(2x_0 + x_1\)입니다.
- \(p^2(1-p)\)의 확률로 두 번 출발점을 다녀옵니다. 이때 이동한 거리는 정확히 \(4x_0 + x_1\)입니다.
- \(\cdots\)
- \(p^k(1-p)\)의 확률로는 \(k\) 번 출발점을 다녀옵니다. 이때는 \(2kx_0 + x_1\)의 거리를 움직입니다.
- \(\cdots\)
패턴을 알았으니 \(\rho_1\)을 계산해 보겠습니다. 아래의 공식을 먼저 살펴 보겠습니다. 이는 계산할 때 유용하게 활용됩니다.
공식 1. 멱급수
임의의 \(0 \leq p < 1\)에 대해, \[ \sum_{k = 1}^\infty kp^k = p + 2p^2 + 3p^3 + \cdots = \frac{p}{(1-p)^2}\]를 만족한다.
[증명] 무한 급수를 \(S\)라고 부르겠습니다. 그러면 \[ pS = \sum_{k = 1}^\infty kp^{k + 1} = p^2 +2 p^3 + \cdots \]를 만족합니다. \(S\)에서 \(pS\)를 빼면 정확히 \[ (1-p)S = p + p^2 + p^3 + \cdots = \frac{p}{1-p} \]를 얻게 됩니다. 여기서 마지막 등식은 \(0 \leq p < 1\)에서의 등비 급수 공식을 통해 곧장 얻을 수 있습니다. 좌변의 \((1-p)\)만 넘겨주면 공식의 수식과 동일해집니다. ■
이제 \(\rho_1\)을 계산할 수 있습니다. \[ \begin{array}{rl} \rho_1 &\displaystyle = (1-p) x_1 + p(1-p) (2x_0 + x_1) + p^2(4x_0 + x_1) + \cdots \\ &\displaystyle = \left((1-p) + p(1-p) + p^2(1-p) + \cdots \right) \cdot x_1 + \left(p + 2p^2 + 3p^3 + \cdots \right) \cdot 2(1-p)x_0 \\ &\displaystyle = x_1 + 2\frac{p}{(1-p)}x_0 \end{array}\] 마지막 등식의 첫 번째 항에서 \(((1-p) + p(1-p) + p^2(1-p) + \cdots) = 1\)인 이유는 디비디비딥을 무한히 수행하다 보면 언젠가는 (거의) 확실하게 성공할 것이기 때문입니다. 또 마지막 등식에서 두 번째 항은 공식 1을 통해서 유도할 수 있습니다.
\(\rho_0\)과 \(\rho_1\)을 구했으나 아직 \(\rho_i\)들이 어떤 패턴을 갖고 있는지 정확하게 보이지 않습니다. 이를 확인하기 위해 \(\rho_2\)도 한번 계산해 보겠습니다. 이는 앞에서와 같이 다음의 경우로 나누어 생각해 보겠습니다.
- \((1-p)\)의 확률로 바로 통과합니다. 이때는 정확히 \(x_2\)의 거리를 이동합니다.
- \(p(1-p)\)의 확률로 첫 번째 수비수에게 한 번 다녀옵니다. 이때 움직인 거리는 다음과 같이 계산할 수 있습니다. 먼저 \(x_1\)의 거리를 이동하여 첫 번째 수비수가 있는 곳까지 갑니다. 다음 첫 번째 수비수에서 두 번째 수비수까지 확률 과정을 거쳐 다시 도달합니다. 매 디비디비딥의 결과는 독립적으로 결정되므로 이 거리의 기댓값은 \(\rho_1\)과 같습니다. 마지막으로 세 번째 수비수가 있는 곳까지 \(x_2\)의 거리를 이동합니다. 이를 계산하면 평균적으로 \( x_1 + \rho_1 + x_2 \)의 거리를 이동한다고 기대할 수 있습니다.
- \( p^2(1-p) \)의 확률로 첫 번째 수비수에게 두 번 다녀옵니다. 이때 위 논의를 확장하면 평균적으로 \(2(x_1 + \rho_1) + x_2\)의 거리를 이동한다고 기대할 수 있습니다. 특히 \(2\rho_1\)을 얻는 이유는 매 디비디비딥이 독립적으로 이루어지기 때문입니다.
- \(\cdots\)
- \(p^k(1-p)\)의 확률로 첫 번째 수비수에게 \(k\) 번 다녀옵니다. 이때 움직인 거리의 기댓값은 \( k(x_1 + \rho_1) + x_2 \)입니다.
- \(\cdots\)
이를 통해 \(\rho_2\)를 구해 보면 \[ \begin{array}{rl} \rho_2 &\displaystyle = x_2 + \frac{p}{1-p} (x_1 + \rho_1) \\ &\displaystyle = x_2 + 2\frac{p}{1 - p}x_1 + 2\left( \frac{p}{1-p} \right)^2 x_0 \end{array} \]임을 이끌어낼 수 있습니다. 여기서 첫 번째 등식은 이전과 비슷한 논의에 기댓값의 선형성을 적용하면 유도할 수 있고, 두 번째 등식은 앞에서 구한 \(\rho_1\)을 대입하여 얻을 수 있습니다.
이를 일반화하면 모든 \(i = 0, \cdots, n\)에 대해, \[ \rho_i = x_i + 2\frac{p}{1 - p}x_{i - 1} + 2\left( \frac{p}{1-p} \right)^2 x_{i - 2} + \cdots + 2\left( \frac{p}{1-p} \right)^i x_0 \]가 된다는 것을 쉽게 유추할 수 있습니다. 이에 대한 증명은 위의 논의로 갈음합니다. 직접 해보시는 것도 추천합니다. 식을 간단히 적기 위해 \(q := \frac{p}{1-p}\)라고 하겠습니다. 그러면, \[ \rho_i = 2\sum_{j = 0}^i q^{i - j}x_j - x_i \tag{3}\]로 쓸 수 있게 됩니다.
이제 술래가 움직인 거리의 기댓값을 \(x_0, \cdots, x_n\)으로 표현할 수 있습니다. 식 2와 식 3에 의해 이는 \[ \sum_{i = 0}^n \rho_i = \sum_{i = 0}^n \left[ 2\sum_{j = 0}^i q^{i - j}x_j - x_i \right] = 2\sum_{i = 0}^n \sum_{j = 0}^i q^{i - j}x_j - 1 \tag{4}\]를 얻을 수 있습니다. 여기서 마지막 등식은 식 1을 통해 유도할 수 있습니다. 이제 \(\sum_{i = 0}^n \sum_{j = 0}^i q^{i - j}x_j\)를 고민해 봅시다. 이를 모든 항에 대해 따로 생각해 보면 다음과 같은 표로 적어볼 수 있습니다.
| \(i\) \ \(j\) | 0 | 1 | 2 | \(\cdots\) | \(n\) |
| 0 | \(x_0\) | ||||
| 1 | \(qx_0\) | \(x_1\) | |||
| 2 | \(q^2x_0\) | \(qx_1\) | \(x_2\) | ||
| \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\ddots\) | |
| \(n\) | \(q^nx_0\) | \(q^{n-1}x_1\) | \(q^{n-2}x_2\) | \(\cdots\) | \(x_n\) |
이를 각 \(x_0, \cdots, x_n\)으로 묶어 주겠습니다. 표현을 간단히 하기 위해 \( S(j) := \sum_{i = 0}^j q^i \)라고 부르겠습니다. 그러면 \[ \sum_{i = 0}^n \sum_{j = 0}^i q^{i - j}x_j = \sum_{j = 0}^n S(n - j) x_j \]로 쓸 수 있습니다. 이를 앞에서 구한 식 4에 대입하여 보면 \[ \sum_{i = 0}^n \rho_i = 2\sum_{j = 0}^n S(n - j) x_j - 1 \]이 되는 것을 이끌어낼 수 있습니다.
자명하게 \(S(0) \leq S(1) \leq \cdots \leq S(n)\)을 만족합니다. 또한 식 1에서 \(x_0 + x_1 + \cdots + x_n = 1\)이라고 하였으므로 술래가 움직인 거리의 기댓값이 최대가 되기 위해서는 \(x_0 = 1\), \(x_1 = \cdots = x_n = 0\)이 되어야 합니다. 다시 말해 모든 수비수가 결승점에서 버티고 있다는 뜻이죠. 그 값은 \[ 2\sum_{j = 0}^n \left( \frac{p}{1-p} \right)^j - 1 \]이 되겠습니다.
본문에서는 형독이 디비디비딥에서 가장 많이 움직이도록 하려면 수비수가 어떻게 위치해야 하는지에 대해 알아 보았습니다. 만약 매 디비디디딥 판의 승패가 독립적으로 결정된다면 모든 수비수들이 결승점에서 뻗대고 있는 게 가장 긴 거리를 움직이도록 만들 것으로 기대할 수 있습니다. 실제 게임에서는 \(n = 7\), \(p = \frac{1}{3}\)이므로 이를 적용해 보면 \[2 \sum_{j = 0}^7 \frac{1}{2^j} - 1 = 3 - \frac{1}{2^6} = 2.983475 \]가 됩니다. 즉, 평균적으로 원래 트랙의 2.983475 배의 거리를 주행해야 한다는 뜻이죠.
영상에서 첫 번째 수비수가 출발점에 위치한 것으로 보아 첫 번째 수비수한테 졌을 때 출발점으로 돌아가지 않는 것으로도 보이는데, 이 경우에는 수비수 한 명은 출발점에, 나머지 여섯 명은 모두 결승점에 두면 됩니다. 그때 형독이 움직일 거리의 기댓값은 트랙 거리의 2.96875 배가 됩니다. 이는 앞의 경우보다 약간 작은 수치이나 어찌 되었든 거의 세 배의 거리를 움직여야 한다는 것에는 변함이 없습니다. 물론 모든 수비수가 결승점에 있는다면 영상이 과연 지금처럼 재밌게 나오지는 않을 것 같습니다. 본문에서 제시하는 수비수 위치 방법은 이론적인 최대치를 제시할 뿐이니 참고만 하시면 될 것 같습니다.
사실 수비수의 목표는 이동 거리를 최대로 만드는 것이 아니라 소요 시간을 최대로 만드는 것입니다. 이 목표를 보다 잘 표현하기 위해서는 본문의 모델에 다음의 두 요소를 추가하는 것이 좋아 보입니다.
- 트랙의 어느 구간을 정방향으로 달릴 때와 역방향으로 달릴 때 소요되는 시간이 다를 수 있음
- 디비디비딥을 진행하는데 (짧지만) 어느 정도 시간이 필요함.
위 요소를 모두 고려하면 어떻게 될까요? 저는 여전히 결승점에 수비수가 모두 존재하는 것이 가장 많은 시간을 소요하게 하는 방법이라고 예상합니다. 정말로 그럴까요?
문제의 모델에서는 매 디비디비딥 판의 승패가 독립적으로 결정된다고 하였습니다. 이를 통해 술래가 움직인 거리의 기댓값을 닫힌 형태 공식(closed form formula)으로 표현할 수 있었죠. 하지만 실제로는 참여자마다 전략이 다르며, 과거의 결과와 매우 밀접한 연관성을 띨 것입니다. 독립은 아니지만 여전히 증명 가능한 수준의 현실성 있는 참여자들의 전략은 무엇일까요? 과연 술래가 세 배보다 짧은 거리를 움직여 게임을 끝낼 수 있을까요? 반대로 수비수들은 술래로 하여금 세 배보다 먼 거리를 움직이게 만들 수 있을까요? 이는 컴퓨터 과학적으로도 흥미로운 주제라고 생각합니다.
읽어 주셔서 고맙습니다.
'연습 노트' 카테고리의 다른 글
| 이분 매칭에 관한 몇 가지 반례들 (5) | 2022.07.16 |
|---|---|
| 알고리즘 덕후의 「투 더 문」 퍼즐 푸는 방법 (2) | 2021.08.31 |
| 표류 중인 어부 문제 (Lost Fisherman Problem) (0) | 2020.05.16 |
| C++ Windows 멀티스레딩 (0) | 2019.09.27 |
