python

Вероятность того, что 2 шахтёра имеют одинаковый мир

  • суббота, 20 июля 2019 г. в 00:22:14
https://habr.com/ru/post/460629/
  • Python
  • Математика
  • Игры и игровые приставки


Всем привет! Недавно меня заинтересовал вопрос: «может ли быть такое, что 2 игрока в Minecraft имеют один и тот же одиночный мир?»

Дело в том, что мир Minecraft генерируется случайным образом из заданного семени. Его можно задать вручную или получить казённый псевдослучайный. Стоит отметить, что одно и то же семя генерирует один и тот же мир.

Эта игра очень популярна, поэтому напрямую опросить всех игроков и сравнить их одиночные миры не представляется возможным. Однако, мы всегда можем посчитать вероятность этого события. Казалось бы: всё, что нам нужно — это посчитать количество элементарных исходов, удовлетворяющих данному событию, и поделить на множество всех элементарных исходов. К сожалению, это весьма нетривиальная задача, поэтому я вспомнил про «Парадокс дней рождения».

Сам парадокс заключается в том, что в группе из 23 человек с вероятностью 50% у двух людей совпадает день рождения. Очевидно, что задача похожа на нашу. Как же она была решена? Очень просто: оказалось, что посчитать вероятность того, что у каждого человека в группе уникальный день рождения намного проще. Для этого нужно взять одного человека и запомнить его день рождения, затем взять второго, причём вероятность того, что его день не совпадает с первым будет равна

$$display$$p_2=1-\frac{1}{365}$$display$$

Т.е. 100% минус вероятность, того, что их день рождения совпадает. Берём третьего и считаем вероятность того, что его день рождения не совпадает с двумя предыдущими

$$display$$p_3=1-\frac{2}{365}$$display$$

И так далее до n-го человека

$$display$$p_n=\frac{n-1}{365}$$display$$

Тогда вероятность того, что не совпадёт ни у одного человека в группе

$$display$$p = 1*(1-\frac{1}{365})*(1-\frac{2}{365})*...*(1-\frac{n-1}{365})$$display$$

А вероятность того, что хотя бы у 2 совпадает

$$display$$p_{искомое}=1-p$$display$$



Осталось только применить это решение для нашего случая. В Minecraft всего 2^64 возможных семян, а игроков около двухсот миллионов. Таким образом, наша формула будет выглядеть

$$display$$p = 1*(1-\frac{1}{2^{64}})*(1-\frac{2}{2^{64}})*...*(1-\frac{2*10^8}{2^{64}})$$display$$

Вручную это считать весьма трудоёмко, поэтому я написал небольшую программу на языке Python 3, которая сделала это вместо меня.

image

Если кому-то интересно — вот код программы, но он очень простой.

a = 2**64
n = 200000000
p = 1

for i in range(n):
    p *= (1 - i/a)

print('Chance that 2 players of minecraft have the same seed: ' + str((1-p)*100) + '%')


Получилось 0.1%, что, кстати, довольно много, учитывая количество возможных семян.

Спасибо за внимание!

Ссылки:

Парадокс дней рождения
Сколько людей играют в Minecraft
Сколько семян в Minecraft