Пилю программку по обсчёту китайского покера

Цитата (Ivikt @ 2.6.2019)
Jak, почему отличаются первые два варианта?

Тут, правда, ускоренный приблизительный расчет, но и полный расчет показывает разные числа.
При полном переборе
1 сл (4 в середину, 8 вниз) - 76,84% / 1,442 ** 1,108 noscoop 1'504'096'776, cnt 1'957'374'720, 509sec
2 сл (3 в середину, 8 вниз) - 76,67% / 1,431 ** 1,097 noscoop 1'500'808'176, cnt 1'957'374'720, 512sec
3 сл (когда 43 в середину) - 28,45% / 1,156 ** 0,329 noscoop 278'406'072, cnt 978'687'360, 274sec; тут даже бонусы меньше.

Цитата (БиллиУбили @ 2.6.2019)
считаю комбинации при каждом запуске проги и трачу на это ~1 мин

вот положил ты 5 карт вниз, как определяешь силу руки? берешь 5 карт, сортируешь их, из массива берешь комбинацию, так? это долго, хоть и сразу все посчитал. Или надо иметь 5-тимерный массив 52^5= 380млн, а тут 5,7млн элементов.

пусть внизу пока 4 карты, я беру из массива значение для 4 карт, запоминаю. Потом добавляю сколько надо раз любую карту и сразу из массива беру силу руки. Ничего не сортирую, только одно обращение к массиву HR5.

Цитата (БиллиУбили @ 2.6.2019)
Не понятно, откуда ты берёшь очки? Вдобавок ещё они и разные для разных линий. Флаш внизу - 4 очка, а в средней линии - 8

ну разумеется для каждой линии свои бонусы. все учитывается.

Jak, я к тому, что варианты равнозначные же, должно быть одинаково

Я понял, значит не равнозначные.

Jak, почему, можешь обьяснить?

ОП(предварительный расчёт!!)
Разложение


+0,17 очка



-0,0002 очка




Получается, что ниже дна упасть нельзя если есть зацепка на фантазию, то выгоднее разменять её на теоретические +6 очков за фулхаус. А вы как считаете, норм результаты или ещё проверять?

Цитата (Jak @ 2.6.2019)
Или надо иметь 5-тимерный массив 52^5= 380млн, а тут 5,7млн элементов

Друг, извини меня, но что-то я туплю. Рассмотрим пример с флашом.
Пусть у карт есть какие-то порядковые номера в колоде(11ая, 13ая и т.д.).
Ты делаешь мощное предположение, что от перемены мест(например ) их сумма не меняется(переместительный закон арифметики) Тут всё по красоте, где-то далеко заплакал один c00l0ne
А вот дальше я не догоняю. Предположим, у тебя получилась сумма 555.
А с чего ты взял, что существует единственное разложение на слагаемые? С таким же успехом, 555 может дать и каре, и Ахай. Извини, но обьясни подробнее, голова забита немного.

Цитата (БиллиУбили @ 3.6.2019)
Друг, извини меня, но что-то я туплю.

Согласен. Причем тут сумма? Ты вообще скобки видишь в моей функции? Это не сумма! return HR5[ HR5[ HR5[ HR5[ HR5[53+c1]+c2]+c3]+c4]+c5]
Похоже ты начинающий программист, не можешь читать чужие тексты.

Ты, наверно, думаешь, что ВСЕ массивы устроены так: Берешь какой-то адрес/номер и элемент по этому адресу - твой ответ!

Представляешь, но есть массивы устроенные по-другому. Этот одномерный массив заменяет пятимерный массив.
Можно сделать массив A[1..52][1..52][1..52][1..52][1..52] и при обращении A[c1][c2][c3][c4][c5] взять силу руки c1,c2,c3,c4,c5.

А тут при первом обращении HR5[53+c1] (оно внутри формулы), мы получим не ответ, а ссылку на адрес внутри массива. К этому адресу добавляем смещение с2 (HR5[53+c1]+c2) и берем следующий адрес в этом же массиве HR5[ HR5[53+c1]+c2] и так далее. Массив устроен таким образом, что если мы поменяем местами с1,с2,с3,с4,с5 и будем брать с2,с5,с1,с4,с3 - все равно ответ будет таким-же. Все эти ссылки попадут в одно место. Первые ЧЕТЫРЕ обращения к массиву дают не ответ, а ссылку на продолжение и ТОЛЬКО ПЯТЫЙ запрос даст ответ!

Цитата (Jak @ 3.6.2019)
Массив устроен таким образом, что если мы поменяем местами с1,с2,с3,с4,с5 и будем брать с2,с5,с1,с4,с3 - все равно ответ будет таким-же. Все эти ссылки попадут в одно место.

ок. давай разбираться. Ты- сильный программиста(даже очень сильный), с этим никто не спорит. Что даёт строчка

Цитата (Jak @ 3.6.2019)
HR5[ HR5[ HR5[ HR5[ HR5[53+c1]+c2]+c3]+c4]+c5]

в конце концов? индекс в массиве HR5, так? Так а что поменяется, если мы к итоговой сумме расположений в колоде добавим 53? Разве от этого разложение на слагаемые станет однозначным?
Например, занимают 6ое и 7ое место в колоде. Да, мы можем присвоить этой "паре" индекс 6+7+53=7+6+53= 66ое место в массиве. Но разве к этому числу не приведут другие карты? Например, 1ая и 12ая

Для тех, кто в танке, распишу оператор еще раз.

int a=HR5[ HR5[ HR5[ HR5[ HR5[53+c1]+c2]+c3]+c4]+c5];

int b1=HR5[53+c1]; // получили ссылку для первой карты c1 в массиве, некое число. Это число - кусок в массиве с которого начинаются ВСЕ комбинации в которых первая карта c1.
далее int b2=HR5[b1+c2]; // получили ссылку для второй карты c2 в массиве, некое другое число. Теперь получили ссылку в массиве, в которой ВСЕ комбинации которые начинаются с c1,c2.
далее int b3=HR5[b2+c3]; // получили ссылку для третьей карты c3 в массиве, некое другое число.
далее int b4=HR5[b3+c4]; // получили ссылку для четвертой карты c4 в массиве, некое другое число.
далее int a=HR5[b4+c5]; // получили ссылку для пятой карты c5 в массиве, некое другое число, ПО ЭТОМУ АДРЕСУ СИДИТ ОТВЕТ - сила комбинации.
Мы несколько раз обращаемся в один массив.

Ничего не суммируется, нет тут

Цитата (БиллиУбили @ 3.6.2019)
Да, мы можем присвоить этой "паре" индекс 6+7+53=7+6+53= 66ое место в массиве. Но разве к этому числу не приведут другие карты? Например, 1ая и 12ая

Все эти ссылки при перестановке (c1,c2,c3,c4,c5) приведут в одно место. Так устроен массив. Это сложно понять, но это так. Придумали его в 2005г, один умный программист. Придумал это не я, долго не мог понять, как это работает, потом разобрался.

Цитата (Jak @ 4.6.2019)
ВСЕ комбинации в которых первая карта c1

Цитата
первая карта

Цитата
Все эти ссылки при перестановке (c1,c2,c3,c4,c5) приведут в одно место

Да, пока сложно понять. Надо будет думать. Ещё раз спасибо за разьяснения.

ну, появилась гипотеза, как заполнить этот массив(ы).
Для у нас осталось возможность для стрита и флаша.
То есть нам хватит 2ух "участков" ёмкостью 52+51+50+49+48 = 250 ячеек, чтобы запихнуть туда эти комбинации.
Начнём класть стриты с 1000 индекса, а флаши - с 2000.
ТОгда, если на 0 шаге к сумме позиций карт мы добавили 2000, то на 4ом шаге действуем по след. алгоритму
а) если пришла флашовая карта, прибавляем её "место" в колоде
б) если пришла стритовая карта, отнимаем от индекса 2000, добавляем 1000 и прибавляем "место" карты в колоде
в) в других случаях отнимаем от текущей суммы 2000 и снова прибавляем "место" карты в колоде
На 5ом шаге действуем аналогично.
Тогда в итоге мы для флаша получим индекс 2000 + сумма позиций карт, для стрита 1000 + сумма позиций карт и просто сумма позиций карт в других случаях.
ТОгда да, сумма позиций карт будет однозначно идентифицировать комбинацию.
Ну, можно заполнять и задом наперёд.
Берём готовый флаш, суммируем позиций карт и добавляем 2000. Далее будем удалять карты по одной. Для карт "в масть" будем просто отнимать позицию карты, а если попалась "немастевая" - дополнительно отнимать 2000(но только один раз).
Попробую сделать это для топа(благо там всего 3 карты, даже не все ранги доступны)

Цитата (Jak @ 4.6.2019)
Все эти ссылки при перестановке (c1,c2,c3,c4,c5) приведут в одно место.

Тут ошибочка. Они не ПРИВЕДУТ в одно место, а ответ будет одним и тем же.

Попробую объяснить устройство массива.
В нашем случае массив имеет параметры (x=52 - кол-во карт в колоде, y=5 - кол-во карт в руке).
Возьмем массив x=9, y=2. Карт в колоде всего 9 и карт всего 2. Так проще, потом по аналогии поймешь.

Карты в колоде отсортированы и имеют индексы от 1 до 9. С нуля нельзя, нужно чтобы первая карта давала смещение, хотя бы 1.
массив [0,1,2,3,4,5,6,7,8,9,10,...] - красным выделена колода уровня 0. Назовем ее К0.
с номера 10 (х+1) начинаются колоды уровня 1, их будет 9 штук по количеству карт в колоде. К1,К2,...,К9. Место К1 в массиве сразу за К0, начало 10, конец 19.
т.е. [0,1,2,...,9, (K0) 10,11,12,...,18,19 (K1) 20,21,22,23,...,29 (K2) и т.д. до 90,91,92...99 (К9)].
Теперь заполним массив.
[0,10,20,30,40,50,60,70,80,90, 0, 0,s12,s13,s14,s15,s16,s17,s18,s19, 0,s21, 0,s23,s24,s25,s26,....] - где s23-сила комбинации из карт 2 и 3. Комбинации, где есть одинаковые карты стоит 0. s11,s22,s33 и т.д.

При первом обращении к массиву мы получим адрес пой колоды в которой первая карта наша. Например первая карта 2. Получим 20 - адрес начала 2-й колоды. Там прибавим смещение - вторую карту, например 3, получим 23, там сидит s23, а это сила комбы (2,3). По адресу 32 будет сидеть сила комбы (3,2) - она такая-же и заранее посчитана.

Надеюсь понятно объяснил для 2 карт.

Теперь представь, что карт в комбе не 2, а 5. Тогда вместо 2-й колоды в посчитанными силами будет сидеть смещение на колоды третьего уровня и т.д. Вместо s12 - будет смещение на колоду третьего уровня в которой все комбы начинаются на (1 и 2). А там уже по смещению 1,2,3,4,5 ... будет сидеть сила комб s121,s122,s123,s124 и т.д.

Ну и 9 карт расширим до 52. Колоды будут кусками по 53 ячейки (52+1).
Самое главное заполнить правильно адреса/смещения в массиве между колодами, а потом посчитать один раз в начале все варианты комбинаций - и вуаля! И не важно стрит там или флеш.

Цитата (Jak @ 4.6.2019)
Надеюсь понятно объяснил для 2 карт

Мне кажется, но ты объяснил устройство какого-то другого массива, не HR5 из твоей программы.
Твои построения для колоды из 9 карт равносильны
а) введению 2ухмерного массива 9Х9, где первый индекс отвечает за первую карту комбинации, второй - за вторую, а в ячейках хранятся "силы" комбинаций
б) развертыванию его в "длину", то есть представлению в виде одномерного массива размерностью 100, по правилу
B[j*10+k] = A[j][k]
Такой подход НЕ экономит память, так как общие затраты на хранение не только не уменьшаются, а даже увеличиваются. 100 vs 81ячеек
В отличии от массива HR5, который для хранения всех возможных комбинаций ограничивается

Цитата (Jak @ 1.6.2019)
всего 5720182 - 32бит чисел

против

Цитата (Jak @ 2.6.2019)
52^5= 380млн

Ну, и далее твои объяснения

Цитата
А там уже по смещению 1,2,3,4,5 ... будет сидеть сила комб s121,s122,s123,s124

ничем по сути не отличаются от 5-мерного массива [9][9][9][9][9]
В общем, мне пока не понятно, как автору удался один и тот же ответ вне зависимости от перестановки c1,c2,c3,c4,c5 - копать нужно здесь

Забудь про эти массивы. Делай как делал.

Чтобы пользоваться телевизором не обязательно знать, как он устроен. Чтобы пользоваться массивом HR5, не обязательно понимать как его создали. Достаточно его иметь и знать как из него извлекать информацию. Jak уже выше полностью разжевал как это сделать.
Но если очень хочется понять как экономится место в этом массиве, то попробую еще раз объяснить.

В этом массиве хранятся адреса (или ссылки) куда следует прыгать при определенной карте из колоды. После пяти таких прыжков мы попадаем в конечную ячейку, в которой хранится уже не следующий адрес, а уже готовое, заранее рассчитанное, значение ранга пяти карт. Например, возьмем три карты с1, с2, с3, после трех прыжков, мы получим адрес А, который соответствует этим трем картам. С этого адреса А, следующие 52 ячейки, хранят адреса, куда следует прыгать при следующей четвертой карте. Для трех карт существует 6 равносильных перестановок, которые ведут в шесть разных мест в массиве, но во всех шести адресах хранится один и тот же адрес А, который соответствует картам с1, с2, с3. Т..е из шести ячеек массива мы попадаем в одну и ту же ячейку. Для четырех карт есть 24 перестановки и соответственно из 24 разных ячеек мы получим ссылку на одну и ту же ячейку. (На самом деле не будет 24 ячейки, но это не важно, важно понять суть). Так экономится место за счет того, что для покерной руки не важен порядок карт.
Но это еще не все. На каждом шагу проверяется, может ли быть флеш для данного набора карт. И если флеш уже не возможен (не все карты одной масти), то все последующие карты уже не имеют значение какой они масти. Т.е все четыре карты одного ранга будут ссылаться на один и тот же адрес. Это еще экономит место в четыре раза.
Эти трюки позволили сжать размер массива до разумных размеров. Особенно важно это было для 7-ми карточной руки (5 карт борда плюс две карты в руке). Для обычного массива понадобилось бы 52 в седьмой степени ячеек - нереальный размер для современных компьютеров. После сжатия - 130 Мбайт - вполне разумный размер.

Jak, ты не поверишь, но твой пост с предложением использовать HR5 появился тогда, когда я смог применить метод ОП для https://forum.gipsyteam.ru/index.php?viewtopic=142685&st=60#entry5978018
ведь там тоже нужны массивы(из 6 карт) для подсчёт комбинаций уже для ВСЕЙ руки. Так вот для 32 карт, оставшихся в колоде, мне ещё хватает памяти, а для большего кол-во(35, 40 и т.д.) - уже нет. Так что рано или поздно эти массивы пришлось бы "сворачивать". Кстати, как ты прокомментируешь свой результат, что "выгоднее" класть 4(или 3) в мидл, 8 вниз. А у меня получилось, что положить 43 в мидл хоть ненамного, но выгоднее. У меня ошибка?


Galax,

Цитата (Galax @ 5.6.2019)
Но это еще не все. На каждом шагу проверяется, может ли быть флеш для данного набора карт

Правильно, это ровно то, что я пишу здесь https://forum.gipsyteam.ru/index.php?viewtopic=142685&st=60#entry5978018
В начале добавляем 2000(произвольное число) к сумме положений карт(порядок не важен) и не отнимаем их до тех пор, пока 2ая, 3яя и т.д. карты сохраняют флаш.
Таким образом, для флаша мы получим адрес ячейки с рангом комбинации под номером (2000+сумма положений карт в колоде), а если хотя бы одна карта не той масти - просто сумму положений карт в колоде(без добавленных 2000).
Таким образом, мы развели комбинацию флаш и остальные, но и сохранили однозначное соответствие (сумма положений карт в колоде) <--> (набор из 5 карт)

Цитата (Galax @ 5.6.2019)
После сжатия - 130 Мбайт - вполне разумный размер

Беспокоит меня другое. Ну, ведут различные комбинации одних и те же карт, образующих к флашу, и что? как это сэкономит память? Только за счёт того, что 5!=120 адресов занимает меньше места, чем хранение 120 рангов комбинации(одного и того же для 5карточного флаша. Но почему тогда ВСЕ ячейки в массиве HR5 - 32битные числа(для записи именно ранга комбинации)? Будет тогда экономия или всё-таки не будет?
ЗЫ

Цитата (Galax @ 5.6.2019)
Чтобы пользоваться телевизором не обязательно знать, как он устроен

Обьясняешь, как боженька. У Мавроди тоже как-то спросили, как работает МММ(в частности, откуда там берутся экстра деньги на выплаты). На что он сказал "а зачем вам знать, как работает?". Достаточно знать, что работает. И привёл аналогию с сотовыми телефонами: нажимаешь кнопку, и вот ты уже слышишь человека с Дальнего Востока. А в это время сигнал где-то там путешествует. Лишние детали, согласись

Ты все таки хочешь понять, как получился этот массив? Но это не имеет практического значения, так как программа которая создает этот массив запускается только один раз и после всех расчетов (относительно длительных) сохраняет его на диске. В дальнейшем вы просто загружаете этот массив из диска в оперативку и извлекаете готовый ранг 5-ти карт из оперативки. Это самый быстрый способ узнать силу 5-ти карточной руки. Ни каких сортировок при этом не делается, никаких промежуточных проверок на флеш или стрит - ничего ресурсно-затратного. Просто пять обращений к массиву и на выходе ранг пяти карт. Причем в старших байтах этого ранга хранится информация о комбинации (фулл-хаус, флеш, стрит и т.д.), в младших - порядковый номер этой руки внутри комбинации.
Если же все-таки хочешь сам разобраться, то рекомендую скачать исходник ( я давал ссылку выше). Я в свое время распечатал его и штудировал строчка за строчкой. Там много интересных программистских трюков, оптимальные методы сортировки, использование внешних библиотек для расчета ранга готовой руки... Но ты вряд ли сможешь это сам повторить, да и за чем изобретать велосипед.

Но попробуй в двух словах - как это работает.
Перебираете в цикле все возможные комбинации из 52-х карт - сначала однокарточные, потом двух-карточные и т.д. до 5-ти карточных. каждый раз сортируете полученные карты и проверяете встречалась ли вам ранее такая комбинация карт. Если не встречалась такая комбинация то присваиваете ей первый свободный адрес в массиве и сразу резервируете за этим адресом еще 52 ячейки для хранения следующих ссылок. Если же такая комбинация уже была, то мы ищем ее адрес и ссылаемся уже на него. Таким образом мы резервируем в массиве место только для новых комбинаций и не повторяем уже существующие. Благодаря сортировке, все перестановки одних и тех же карт будут иметь одну и ту же комбинацию и будут ссылаться на один адрес. Параллельно мы проверяем комбинацию карт на возможность флеша. Если флеш не возможен, то все варианты карт (например АК) идентичны и ссылаются на один адрес соответствующий АхКх. Если флеш возможен то есть четыре варианта , ,, и мы будем ссылаться на эти варианты по-отдельности на четыре разных адреса.

Итак какая экономия места? Возьмем к примеру те же АК. их можно получить 16 способами (4 туза и 4 короля) учитывая порядок карт (КА) еще в два раза больше. Итого 32 способа - чтобы хранить все ссылки без оптимизации, нужно 32 ячейки в массиве. После оптимизации - только 5 ячеек (четыре одномастных АК и один разномастный).
Для трех карт еще круче. АКQ - всего вариантов 4*4*4= 64, перестановок 6, итого 64*6=384. После оптимизации все те же 5 ячеек массива ( , , , , ).

Цитата (Galax @ 5.6.2019)
Ты все таки хочешь понять, как получился этот массив?

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

2All
Появилась другая идея.
Нам нужно отобразить 52^5 комбинаций на C(52,5) уникальных
Операция "сумма" не подходит - она не взаимооднозначная
Операция "перемножение" подходит - но требует слишком много памяти
А что если попробовать компромисс?
Например, сумму квадратов? (с1^c1+с2^c2+с3^c3+с4^c4+c5^с5)
Но тут слишком маленькое пространство для манёвра, нужно 2,6КК возможностей. Значит, по идее, будут пересечения.
Возьмём сумму кубов. Ну, или сумму квадратов для (сi + 100)
Как тебе такое, Илон Маск?

Цитата (БиллиУбили @ 5.6.2019)
Нам нужно отобразить 52^5 комбинаций на C(52,5) уникальных

Сначала, после поста Galax испугался. Это что же получается, придётся на каждом шаге надо проверять, образует ли 3ёх карточная комбинация "остов" для какой-нибудь очковой комбинации или нет, но потом перечитал Jak. Его подход симпатичнее. По его методе не важно, что мы получаем на конечном этапе: флаш, стрит или риблстрайп, главное, что уникальную комбинацию. Мы просто сокращаем ВСЕ возможные комбинации на 5!=120, то есть, грубо говоря, производим сортировку "на лету".
Попробую повторить.

Зачем изобретать велосипед с определением покерных комбинаций?

Если дело дойдет до оптимизации, советую сюда заглянуть