Мне нужен совет о том, как решать алгоритмическую проблему (т.е. не программировать как таковую). Ниже приведены мои потребности и то, как я пытался их удовлетворить. Любые комментарии по улучшению будут приветствоваться.
Позвольте мне сначала начать с объяснения моей цели. Я бы хотел сыграть в покер около миллиарда раз. Может быть, я пытаюсь создать следующий PokerStars.net, может, я просто сумасшедший.
Я хотел бы создать программу, которая может производить более рандомизированные колоды карт, чем обычная программа, вызывающая random (). Это должны быть качественные колоды, созданные из высококачественных случайных чисел. Я слышал, что коммерческие покерные серверы используют 64-битные векторы для каждой карты, таким образом, обеспечивая случайность для всех миллионов покерных игр, в которые играют ежедневно.
Я бы хотел, чтобы все, что я пишу, было простым. Для этого программе требуется только один ввод для достижения указанной цели. Я решил, что всякий раз, когда программа начинается, она будет записывать текущее время и использовать его в качестве отправной точки. Я понимаю, что такой подход был бы невозможен для коммерческих сред, но до тех пор, пока он может выдержать несколько миллиардов игр, лучше, чем более простые альтернативы, я буду счастлив.
Я начал писать псевдокод, чтобы решить эту проблему, но столкнулся с непростой проблемой. Это понятно для меня, но может и не для вас, поэтому, пожалуйста, дайте мне знать.
Псевдо-код ниже:
Start by noting the system time.
Hash the current time (with MD5) around ten times (I chose the ten arbitrarily).
Take the resulting hash, and use it as the seed to the language-dependent random() function.
Call random() 52 times and store the results.
Take the values produced by random() and hash them.
Any hash function that produces at least 64-bits of output will do for this.
Truncate (if the hash is too big) so the hashes will fit inside a 64-bit double.
Find a way to map the 52 doubles (which should be random now, according to my calculations) into 52 different cards, so we can play some poker.
Моя проблема с последним шагом. Я не могу придумать, как правильно сопоставить каждое 64-битное значение с соответствующей картой, не беспокоясь о том, что два числа совпадают (маловероятно) или не теряют случайности (вероятно).
Моя первая идея состояла в том, чтобы разбить 0x0000000000000000 - 0xFFFFFFFFFFFFFFFF на четыре четных секции (для представления мастей). Но нет никакой гарантии, что мы найдем ровно тринадцать карт в разделе, что было бы плохо.
Теперь, когда вы знаете, где я застрял, как бы вы преодолели этот вызов?
- отредактировано -
Чтение байтов из / dev / random будет хорошо работать на самом деле. Но это все еще оставляет меня потерянным на том, как сделать преобразование? (при условии, что я прочитал достаточно байтов для 52 карт).
Мое настоящее желание - взять что-то простое и предсказуемое, например системное время, и превратить его в рандомизированную колоду карт. Заполнение random () системным временем - ПЛОХОЙ способ сделать это. Отсюда хэширование времени и хэширование значений, которые получаются случайными ().
Черт, если бы я захотел, я мог бы хэшировать байты из / dev / random, только для смеха и хихиканья. Хеширование улучшает случайность вещей, не так ли? Разве не поэтому современные менеджеры паролей хранят пароли, которые были хешированы тысячи раз?
- Редактировать 2 -
Итак, я прочитал ваши ответы, и меня смущает вывод, на который намекают многие из вас. Я намекнул на это в своем первом редактировании, но это действительно заставляет меня задуматься. Я просто хотел бы указать на это и двигаться дальше.
Существуют радужные таблицы, которые делают забавную математику и умную магию, по сути, выступая в качестве таблицы поиска общих хэшей, которые сопоставляются с определенным паролем. Насколько я понимаю, более длинные, более надежные пароли вряд ли будут отображаться в этих радужных таблицах. Но факт остается фактом: несмотря на то, что многие пользовательские пароли являются общими, хешированные пароли остаются безопасными после хеширования тысячи раз.
Так это тот случай, когда многие детерминированные операции увеличили случайность исходного пароля (или кажется?) Я не говорю, что я прав, я просто говорю, что это мое чувство.
Второе, на что я хочу обратить внимание: Я делаю это задом наперед.
Я имею в виду, что вы все предлагаете мне взять отсортированную, предсказуемую, неслучайную колоду карт и использовать на ней перетасовку Фишера-Йейтса.Я уверен, что Фишер-Йейтс - хороший алгоритм, но допустим, что вы не могли его использовать по какой-либо причине.
Не могли бы вы взять случайный поток байтов, скажем, в окрестности 416 байтов (52 картыс 8 байтами на карту), а BAM производит уже случайную колоду карт?Байты были случайными, поэтому это не должно быть слишком сложно.
Большинство людей начинали с колоды из 52 карт (случайных или нет) и обменивали их несколько раз (выбирая случайный индекс для обмена).Если вы можете сделать это, то вы можете взять 52 случайных числа, пробежать их один раз и создать рандомизированную колоду.
Как я могу описать, Алгоритм принимает поток случайных байтов и просматривает каждый 8-байтовый фрагмент.Он отображает каждый кусок на карту.
Пример.0x123 карты для пикового туза Ex.0x456 карты для короля бриллиантов Ex.0x789 сопоставляется с 3 клубами .... и т. Д.
Пока мы выбрали хорошую модель для сопоставления, это нормально.Перестановка не требуется.Программа будет сокращена до двух этапов.
Шаг 1: Получить достаточное количество случайных байтов из хорошего источника. Шаг 2: Разделить этот поток байтов на 52 блока, по одному для каждой карты в колоде. Шаг 2a: Выполните 52 фрагмента, преобразовав их в значения карт согласно нашей карте.
Имеет ли это смысл?