Вчера запекал баранью лопатку (вам же интересно мое чревоугодие? 🍖), и из этого вырос пост про случайность и скапулимантию.

Мы все знаем много алгоритмов, в которых случайность важна - в криптографии, оптимизации, ML, распределенных системах и так далее. А как насчет менее академических, более древних примеров? Теория вероятностей стартовала как прикладной инструмент для азартных игр, но я сейчас не про то, как Кардано играл в кости. Но кости в этом тексте еще будут упомянуты!

Давайте представим такую ситуацию: на некой территории живут племя охотников и стая вкусных животных (например, оленей или баранов). Охотники могут отходить от лагеря в поисках дичи в выбранном ими направлении. Олени хотят где-то пастись и избегать охотников. Предположим, что качество пастбищ на всей территории одинаковое. Каково оптимальное поведение для каждой группы с точки зрения базовой теории игр?

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

Например, гадание на лопатке. Алгоритм такой: охотник берет кость нужного зверя, нагревает на углях до образования трещин и трактует эти трещины как своего рода карту, выбирая направление для охоты. Поздравляю, теперь вы знаете, что ответить на интервью, если вас попросят задизайнить random number generator, имея остатки ужина и костер!

Фактоид честно украден из книги Джозефа Хенрика.