Всем привет! Недавно меня заинтересовал вопрос: «может ли быть такое, что 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

Комментарии (9)


  1. vedenin1980
    19.07.2019 12:03

    Получилось 0.1%, что, кстати, довольно много, учитывая количество возможных семян… В Minecraft всего 2^64 возможных семян, а игроков около двухсот миллионов

    Тут в рассуждениях ошибка, так как вполне очевидно, что у игроков чаще всего не один единственный мир, зачастую их может быть сотни и тысячи.

    Среднее значение найти сложно, но я бы взял, например, 10 миров на игрока (так как на игроков у которых тысячи миров, приходитеся много бросивших играть после генерации 2-3 первых миров).


    1. hunroll
      19.07.2019 13:00
      +1

      Если считать по 10 миров на человека — то вероятность уже 11%! А если по 20 — то 35%. Жалко что проверить это не так просто как дни рождения(


    1. HEYNOW Автор
      20.07.2019 14:31

      Я произвел оценку снизу, так как это сделать проще, чем искать статистику по среднему количеству миров у игроков


  1. nur_ke2
    19.07.2019 12:22

    Если я не ошибаюсь, то вы посчитали только вероятность одинакового семя у игроков, от которого уже прорастает дерево мира. А дерево, в свою очередь, тоже генерируется по своим алгоритмам. Тогда 0,1% — это не является вероятностью генерации одинакового мир у двух игроков.


    1. SirEdvin
      19.07.2019 12:25
      +1

      Если я не ошибаюсь, алгоритмы как раз полностью детерминированные, что бы можно было обмениваться семенами в сети.


      1. mayorovp
        19.07.2019 13:27
        +1

        Прежде всего они детерминированы для того, чтобы мир игрока не зависел от того, в каком порядке он этот самый мир открывает. Тем самым создается иллюзия генерации всего мира при старте, а не по мере подгрузки чанков.


      1. andreymal
        19.07.2019 21:54

        К сожалению, не полностью, вот, например, одно и то же место с одним и тем же сидом, к которому подлетели просто с разных сторон в двух разных мирах


        Спойлер


  1. eugene_e
    19.07.2019 17:15

    Зачем было писать программу, если эта формула сводится к формуле геометрической прогрессии?


    1. HEYNOW Автор
      20.07.2019 14:40

      Чему будет равно q?