|
|
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
Есть колода карт. Как определить, хорошо ли она перемешана? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2015, 10:17 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
Я бы критерий инверсии проверял для мастей и карт одного достоинства. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2015, 10:52 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
scf, 1) нужно определить критерий "что такое хорошо" - и вперед 2) с задачей об алгоритме перемешивания будет гораздо проще - она стандартная ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2015, 14:33 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
Надо определить критерий качеаства перемешивания и вычислить его для заданной перестановки карт в колоде. Об этом недавно была тема в С++. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2015, 18:15 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
Критерий качества перемешивания? Да запросто: Сколько индивидуальных шагов потребуется для восстановления сортировки? Берешь свой любимый метод сортировки и прогоняешь колоду через него подсчитывая количество сколько раз ты поменял две карты местами. Полученную цифру делишь на максимально возможное количество перестановок (мы его знаем из определения алгоритма сортировки) и получаешь искомый "процент перемешанности". Хотя, наверное надо будет еще поделить максимум на два перед делением. Потому что максимум шагов мы можем получить если начальный массив (колода) находится в идеально-обратном порядке, что не может считаться перемешанным... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2015, 19:25 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
White Owl, В этом случае колода, строго упорядоченная обратно "начальной" будет считаться идеально перемешанной. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2015, 19:42 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
Упс, недочитал до конца. ИМХО, с перестановками ничего путного не выйдет, очень много будет "особых" ситуаций. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2015, 19:45 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
в идеале не должно быть 1) повторяющихся мастей 2) повторяющихся достоинств 3) возрастающих/убывающих по порядку достоинств 4) повторяющихся последовательностей ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2015, 19:59 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
Всё немного интереснее)  ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2015, 20:24 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
eNoseв идеале не должно быть 1) повторяющихся мастей 2) повторяющихся достоинств 3) возрастающих/убывающих по порядку достоинств 4) повторяющихся последовательностей совсем немного из всего этого, все-таки должо быть, иначе это будет каким-то упорядочиванием. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.11.2015, 23:20 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
eNoseв идеале не должно быть 1) повторяющихся мастей 2) повторяющихся достоинств 3) возрастающих/убывающих по порядку достоинств 4) повторяющихся последовательностейруки сдающему надо за такие сдачи отрывать, и канделябром по голове ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2015, 01:52 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
White OwlКритерий качества перемешивания? Да запросто: Сколько индивидуальных шагов потребуется для восстановления сортировки? Берешь свой любимый метод сортировки и прогоняешь колоду через него подсчитывая количество сколько раз ты поменял две карты местами. Полученную цифру делишь на максимально возможное количество перестановок (мы его знаем из определения алгоритма сортировки) и получаешь искомый "процент перемешанности". Хотя, наверное надо будет еще поделить максимум на два перед делением. Потому что максимум шагов мы можем получить если начальный массив (колода) находится в идеально-обратном порядке, что не может считаться перемешанным... Значит если использовать quicksort все колоды будут иметь примерно одинаковую меру "перемешанности" ? На самом деле практически любой метод сортировки в большинстве случаев будет давать примерно одинаковые между собой результаты данного критерия. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2015, 07:19 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
SashaMercuryЗначит если использовать quicksort все колоды будут иметь примерно одинаковую меру "перемешанности" ? Нет, при использовании quicksort самой перемешанной будет считаться изначально упорядоченная колода. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2015, 14:59 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
Ну... я к сдыду должен признаться что нифига не понимаю в карточных играх. И умею играть только в дураки. Но вроде-бы я читал что для некоторых игр типа Покер или Блек Джек нужно собирать "правильные" комбинации. Разумеется колода, отсортированная машинным детерминированным псевдо-случайным обменом может иметь некоторые под-последовательности которые приведут к слишком-уж подозрительному порядку сдачи. Поэтому конечно-же Надо брать Secured-Random. Особенно если учесть тот факт что карточные игроки и лудоманы проявляют дьявольскую наблюдательность в оценке того как сдаёт тот или иной игровой автомат или интернет-казино. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2015, 16:07 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
ИМХУ "Хорошо перемешано" невозможно оценить. И это главное с точки зрения оценивающих перемешивание. Любая оценка, т.е. подгонка под оценку однозначно приводит к результату "плохо перемешано". Хорошо перемешано должно быть так, чтобы невозможно было оценить как перемешано. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2015, 20:07 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
Можно еще перенумеровать все карты в колоде и считать тестируемый вариант результатом работы генератора случайных чисел. Методов для оценки их качества множество. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2015, 21:08 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
Dima TИМХУ "Хорошо перемешано" невозможно оценить. И это главное с точки зрения оценивающих перемешивание. Любая оценка, т.е. подгонка под оценку однозначно приводит к результату "плохо перемешано". Хорошо перемешано должно быть так, чтобы невозможно было оценить как перемешано. Для симметричного шифрования был критерий который я запомнил. Вобщем смена 1 бита в открытом тексте должна порождать 50% изменившихся битов к шифро-блоке. +Там еще была куча стат-показателей типа автокорреляции и т.п. Но не суть. Вобщем. Мне кажется к тасованию карт можно применить нечто вроде критерия "добротности" как в шифрах и хешах. Ну примеру. 1. Отсортированная колода (по мастям и по рангу) после одного раудна тасования должна порождать 50% изменившихся бит. 2. Повторный раунд тасования - тоже самое. 3. Не должно быть технической возможности узнать ГДЕ будет нужная карта через 1 раунд тасования. Это мне кажется ключевой момент для всех карточных игр. 4. Для ГПСЧ период должен быть достаточно большой. Эээ.... еще больше. Нет еще-еще больше. Как-тот так. По поводу битов ... эээ я еще не могу придумать чо как. Для 36/53 карт надо подумать. Возможно это нетривиально. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2015, 23:40 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
maytonОсобенно если учесть тот факт что карточные игроки и лудоманы проявляют дьявольскую наблюдательность в оценке того как сдаёт тот или иной игровой автомат или интернет-казино. В казино есть хорошее истинно случайное число - точное время очередной сдачи. Думаю, достаточно грамотно внести его во входные данные, чтобы получить надёжное средство против любой "дьявольской наблюдательности". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2015, 14:08 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
Для онлайн-казино (а я думаю мы скорее всего будем обсуждать именно такой кейс) я-бы не стал использовать время как аргумент для случайного числа. Системное время в мс конечно иногда используют для seed. Но думаю что это может быть как сильной так и слабой стороной алгоритма. Пока не готов аргументировать. Надо подумать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2015, 15:08 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
softwarer, нужна будет синхронизация по времени с сервером он-лайн казино ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2015, 22:21 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
mayton, use case: пусть он-лайн казино использует время раздачи как случайную величину всего комбинаций 36! (36 факториал) т.е имеем цикл с периодом Т=36! Пусть одна комбинация соответствует одному моменту времени, это означает, что точно установив время раздачи можно точно узнать комбинацию. Установив приблизительно время раздачи, узнаем диапазон возможных комбинаций. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2015, 22:44 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
mini.weblabпусть он-лайн казино использует время раздачи как случайную величину всего комбинаций 36! (36 факториал) т.е имеем цикл с периодом Т=36! Мысль потерял. Между временем и "всего комбинаций". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 09:30 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
mayton, посмотри основы работы псевдо ГСЧ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 11:16 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
mini.weblabПусть одна комбинация соответствует одному моменту времени, Вот это уже вряд ли разумно. Время нужно использовать для внесения "непредсказуемости" в раздачу ГСЧ, а не как номер комбинации. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 11:33 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
softwarer, использование времени раздачи в качестве случайной величины, означает, что seed = момент времени разве нет? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 11:50 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
mini.weblabmayton, посмотри основы работы псевдо ГСЧ Подумай о том что в 1 секунду казино выдало 2 сеансам игры 2 одинаковые сдачи. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 11:51 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
mini.weblabиспользование времени раздачи в качестве случайной величины, означает, что seed = момент времени разве нет? Совершенно не обязательно. Существует сколько угодно других вариантов. Ну просто для примера - брать последовательность чисел, выдаваемую ГСЧ, и xor-ить каждое с младшими байтами времени раздачи. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 12:16 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
Народ, вы серьезно не в курсе, откуда берутся псевдослучайные числа? В особенности, псевдослучайные числа для криптографии? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 12:32 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
mayton, обсуждаем реализацию алгоритма перемешивания авторВ казино есть хорошее истинно случайное число - точное время очередной сдачи определим реализацию случайной величины: перетасованная определенным образом колода карт если раздачи на разных столах начались одновременно , то колоды на первом и втором столе будут перетасованы одинаково ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 12:37 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
mini.weblabесли раздачи на разных столах начались одновременно , то колоды на первом и втором столе будут перетасованы одинаково Кстати, а что в этом страшного? Прежде чем пугать, дадите осмысленный сценарий использования этой уязвимости? Нет, не будут, если у разработчика есть хотя бы десять грамм мозгов - достаточно, чтобы заксорить старший байт времени с номером стола. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 12:41 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
softwarermini.weblabиспользование времени раздачи в качестве случайной величины, означает, что seed = момент времени разве нет? Совершенно не обязательно. Существует сколько угодно других вариантов. Ну просто для примера - брать последовательность чисел, выдаваемую ГСЧ, и xor-ить каждое с младшими байтами времени раздачи. если я знаю точное время раздачи, то у меня появляется дополнительная информация о реализации случайной величины PS: по поводу временных сидов: я рассмотрела самый простой случай, потому что там все ясно и понятно ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 12:53 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
softwarer, давайте, я с вами соглашусь, а вы мне за это дадите адрес он-лайн казино :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 12:55 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
mini.weblabесли я знаю точное время раздачи, то у меня появляется дополнительная информация о реализации случайной величины Во-первых, точного времени Вы не знаете. Оно закопано внутри сервера, наружу не выходит, и если Вы можете до него добраться - Вам незачем тратить на это время, проще сразу брать тёпленькую ГСЧ. Во-вторых, Вы не забыли, о чём вообще речь? Напомню, речь о том, что временем можно подсолить ГСЧ так, чтобы "сверх-наблюдательный игрок", стоя перед автоматом, не получил материала для анализа. О том, что перед автоматом три года заседает команда упакованных криптоаналитиков, речь не идёт. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 13:01 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
mini.weblabsoftwarer, давайте, я с вами соглашусь, а вы мне за это дадите адрес он-лайн казино :) Воспринимаю это как "Ой, всё". Адреса онлайн-казино можете нагуглить самостоятельно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 13:02 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
softwarermini.weblabесли я знаю точное время раздачи, то у меня появляется дополнительная информация о реализации случайной величины Во-вторых, Вы не забыли, о чём вообще речь? Напомню, речь о том, что временем можно подсолить ГСЧ так, чтобы "сверх-наблюдательный игрок", стоя перед автоматом, не получил материала для анализа. О том, что перед автоматом три года заседает команда упакованных криптоаналитиков, речь не идёт. вообще-то речь шла об он-лайн казино ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 13:09 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
softwarer, авторО том, что перед автоматом три года заседает команда упакованных криптоаналитиков, речь не идёт. не, не сидят, все хорошо прекрасная маркиза =) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 13:14 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
eNoseв идеале не должно быть 1) повторяющихся мастей 2) повторяющихся достоинств 3) возрастающих/убывающих по порядку достоинств 4) повторяющихся последовательностей Чем больше подобных ограничивающих условий - тем, на самом деле, меньше допустимых вариантов тасовки, и больше определенности в последовательности карт. Усилив требования, например, чтобы "через одну карту" тоже не повторялись масти, мы можем добиться, что всем этим требованиям будет удовлетворять только одна последовательность карт в колоде. Как в анекдоте про сисадмина, который предъявил столько требований и ограничений к паролям пользователей, что подходящим остался только один пароль. Под хорошим перемешиванием игроки скорее понимают минимум функции автокорреляции в колоде, то есть никакие масти или достоинства отдельных карт или их последовательностей не должны быть "похожи" на другие карты или последовательности в других частях колоды. "Похожесть" описывается формулой, ее сумма считается для данного расклада колоды, чем меньше она выходит - тем лучше перемешана, в идеале автокорреляция=ноль. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 14:47 |
|
||
|
Я тут задумался
|
|||
|---|---|---|---|
|
#18+
maytonПодумай о том что в 1 секунду казино выдало 2 сеансам игры 2 одинаковые сдачи. Во-первых, не "секунду", а "миллисекунду". Не надо использовать time() как seed. В лучшем случае GetTickCount(), в худшем - timeb. Вероятность получить одинаковые раздачи стремится к нулю. Во-вторых, инициализировать ГСЧ на каждой раздаче это не самая хорошая идея. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2015, 15:12 |
|
||
|
|
start [/forum/topic.php?all=1&fid=16&tid=1340879]: |
0ms |
get settings: |
7ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
150ms |
get topic data: |
10ms |
get forum data: |
3ms |
get page messages: |
80ms |
get tp. blocked users: |
2ms |
| others: | 204ms |
| total: | 477ms |
| 0 / 0 |
