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

БиллиУбили, про евшку незаконченной руки ... я так понимаю ты делаешь солвер на последнии сдачи ... без учета руки оппа ...

c00l0ne @ 14.2.2019
я так понимаю ты делаешь солвер на последнии сдачи ... без учета руки оппа ...

да, солвер. С учётом карт соперника. Практически всегда рукой противника можно пренебречь, за исключением скупа, когда нужно уменьшить свои очки, но избежать -6(или, наоборот, получить +6). Крайне редкие ситуации, но их тоже можно учесть.

Чудны дела твои, господи. Переписал алгоритм в пользу перебора(без заглядывания вперёд) и наивно думал, что он будет работать быстрее. Но нет. На 50К комбинаций ушло почти 6 мин, что в 4 раза больше. А казалось бы...
Но зато вот эта задачка Из 12 девушек и 10 юношей выбирают команду, состоящую из пяти человек. Сколькими способами можно выбрать эту команду так, чтобы в нее вошло не более трех юношей? натолкнула меня на мысль полностью поменять алгоритм. В который раз подряд...

БиллиУбили, задачник) в колоде 22 карты , 10 карт белые остальные черные
какова вероятность что из 5 вытянут карт белых будет 3 и более ...
решается гипергеометрической прогрессией ...
могу вероятность в табличке глянуть , флеш трижды )

c00l0ne,

c00l0ne @ 15.2.2019
решается гипергеометрической прогрессией ...

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

БиллиУбили, ага чет словечко перепутал гипергеометрическим распределением решается точно
https://ru.wikipedia.org/wiki/%D0%93%D0%B8%D0%BF%D0%B5%D1%80%D0%B3%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5

пс мы все ждем когда же потухнет мотор )

Новый алгоритм

план Б


ты напиши где у тебя сортировка используется
с битовыми операциями там вообще какая сортировка возможна?

c00l0ne @ 15.2.2019
мы все ждем когда же потухнет мотор )

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

c00l0ne @ 15.2.2019
план Б

это уже план В

c00l0ne @ 15.2.2019
ты напиши где у тебя сортировка используется
с битовыми операциями там вообще какая сортировка возможна

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

Так, что-то я немного запутался. В этом примере https://forum.gipsyteam.online/index.php?viewtopic=142685&st=60#entry5978018
чему равно кол-во вариантов закончить руку? Неужели С(40,2)*C(38,2)*C(36,2)? Что-то уж больно большое число получается.
При заполнении возможных завершений использовал 3фильтра. Сначала внизу комбинация не младше "2пары", потом в мидл не младше "пара", а потом итоговый "очки руки > 0". Получилось 1.8 миллиона(!) комбинаций, которые отобрались за 7 мин. Подсчёт вероятностей их собрать занял 15 секунд. Получается, надо оптимизировать поиск "готовых" рук.

я, кажется, понял, о каких бинарных деревьях говорил c00l0ne. Алгоритм такой: сначала заполняем низ(например, фулхаус). Следующим "ходом" бахаем фанту наверх(любую, 2 одновременно собрать не получится). Вуаля, у нас уже отобраны 2 ветки. Фулхаус внизу и фанта И фулхаус внизу без фанты. (возможно, не надо считать путь до фулхаус без фанты. Он будет равен 1 - путь до фулхаус с фантой). Остаётся мидл. Для каждой из этих веток(с двумя законченными линиями) подсчёт один. Тут тоже всего 2 варианта: комбинация либо старше фантазии, либо младше. Тогда младшая идёт просто в очки(вместе с фулхаусом, но хоронит фулхаус и фантазию), а старшая приносит и свои очки, и фантазию, и фулхаус.
Остаётся вопрос, а как быть, если для трёх комбинаций нужно 2 карты какого-то достоинства, а в колоде их осталось всего одна. Но это учтётся в поиске пути до завершения. Если "на бумаге" получилось 3 линии, которые требуют больше карт, чем есть в колоде, то путь до их завершения будет равен 0 и такой расклад "помножиться на ноль". Так думаю.

БиллиУбили @ 16.2.2019
Неужели С(40,2)*C(38,2)*C(36,2)? Что-то уж больно большое число получается

почему так? помойму на порядки больше

diklee @ 16.2.2019
почему так? помойму на порядки больше

Ну, вряд ли на порядки. Если учесть порядок выбора линий для заполнения, то надо умножить на факт(3). Если не важен порядок 2 карт, которые добавили к каждой линии, то надо разделить на 2^3 = 8. Откуда порядки?
Лучше подскажи, как правильно построить дерево успешных завершений и как оптимально(с точки зрения быстродействия) его обходить

Откуда вообще эти числа берутся с(40,2)?
Твоя хитрая теория где достаются не 3 карты а две? 40 это что? Карты соперника веть видны, остается карт гораздо меньше

diklee, ну вот же ссылка на пример https://forum.gipsyteam.online/index.php?viewtopic=142685&st=60#entry5978018



я считаю ЕВ руки БЕЗ учёта трёх пришедших карт( пока отправляем обратно в колоду). Итого мы знаем 17 из 52. Сколько всего вариантов готовой руки мы можем получить? приблизительно С(35,2)*С(33,2)*C(31,2) или я ошибаюсь? По описанным мною фильтрам получилось 1.8 млн тех рук, которые набрали хоть какие-то очки. Понятно, что часть из них не стоят проверки на ЕВ(дорогостоящая операция), так какая разница, какие именно 2 карты мы добавили в топ, если мы знаем, что там не образовалась пара(или даже фантазия).

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

diklee, наверно тогда расскажу свою идею ещё раз.
Для любой(законченной и незаконченной линии) введём понятие успешного завершения.
Тогда те карты, которые понадобятся для завершения будут составлять "путь". Зная "путь" того или иного завершения можно посчитать вероятность. Она будет равна вероятности "собрать путь" за N подьёмов. И я предполагал, что эту вероятность трудно посчитать. Выяснилось, что она считается по элементарным формулам.
Соответственно, и задача нахождения Вэлью руки сводится к нахождению всех "успешных завершений". Затем для них надо найти "путь", найти вероятность его собрать, и умножить на кол-во очков, которое даём "успешное завершение".
Поэтому

diklee @ 16.2.2019
Брать по две карты, а не по три погрешность в еквити будет не меньше, чем если брать сразу шесть

путь за N подьёмов равен сумме N путей по 2 карты

diklee @ 16.2.2019
Но если бы мы всетаки модулировали такой покер, где берется только две карты, почему ты не перемножаешь на количество вариантов которыми мы можем их разложить?

А зачем мне (считать) число перестановок? А знаю все варианты, какими я могу собрать фантазию в топе. Если несколько из них симметричны(например + = + ), то я их НЕ разделяю, так как вероятность вытащить из колоды {,} равна вероятности вытащить {,}. Соответственно, что считать отдельные пути для перестановок, что считать один путь, не учитывая перестановки - общая вероятность получится такой же.

всего завершающих комбинаций для в топе = С(40,2) = 780
из них приносят очки 109
осталось только 2 вопроса:
1. Различать ли "пути" {,} и {,}?
2. Что делать с подьёмом {,,}? Хотя вероятность получить его из колоды не меняется, но он приведёт к 3ём различным завершениям: {}, {} и {}, то есть как бы включает в себя 3 "пути". И если сокращать путь до 2 карт, то надо будет вводить ограничения на 3ью карту

Я другие перестановки имел ваиду. То что полученую можно разложить 6ю разными способами.
Что значит завершающие комбинации для в топе? От куда опять 40 взялось?

Итак, господа, надо признать, что я ошибся. То, что я предполагал будет сложно посчитать(конкретно "путь" от незавершённой руки до завершённой) - считается легко. А вот сами успешные "завершения" - мало того, что их катастрофически много, так ещё и процесс их нахождения никак не оптимизировать: никуда от нахождения комбинаций в линиях и попарного их сравнения не деться. Об этом я в начале задачи и не помышлял. А, повторюсь, решал задачу заполнения руки за N подьёмов. Оказалось, что всё-таки не важно за сколько подьёмов и какими именно рука завершена - важно лишь её конечное состояние.
Поэтому в споре с кулон я прав(или НЕ прав) наполовину: посчитать разложение 3-4подьёма с абсолютной точностью на домашнем компе невозможно.
Но, что можно сделать, так это считать только нижнию линию(максимизировать набранные ею очки, либо минимизировать скуп). Но тогда фантазия будет так сказать "побочным продуктом": она либо уже будет лежать, либо наберётся сама по себе с неизвестными нами шансами.
Сейчас я возьму маленький перерыв, чуток покатаю.
А вы ставьте плюс, если такой инструмент вам нужен(я там добавлю флаш, если что)
Ну, или ставьте минус, если у меня всё-равно ничего не получится ))
В любом случае, спасибо за внимание!

Сыграл АнанасСуперстек, первый турнир после 2ухмесячного перерыва. 5ое место...

появилась следущая идея (по мотивам поста EternalRain)
1. Для линии в руке ввести "массив состояний", где размерность "массива" - число комбинаций(каре, стрит, флаш и т.д.), а каждый элемент может принимать всего 2 значения - да/нет
2. Для законченной линии массив сократится ровно до 1ого значения - "да" напротив собранной комбинации, "нет" на остальных местах
3. Для незаконченной линии массива можно ввести два. Первый - это массив уже собранной комбинации(ну, например тройка на трёх картах), и второй - массив возможных будущих "состояний". Для той же тройки их будет 2 - это каре и фулхаус.
Как это можно использовать?
а) ну, при выборе куда положить(в какую линию добавить) 2 карты из подьёма можно руководствоваться простым принципом:
класть так, чтобы уменьшение макс. будущего состояние было минимальным.
Например, имеем внизу. Совершенно очевидно, что если мы положим вниз, то уменьшим макс. будущее состояние с "роялфлаш" до "тройка(дам)". А если положить , то макс. будущее состояние упадёт всего лишь до флаша.
б) можно руководствоваться и другим принципом. Пытаться не уменьшать общее кол-во будущих состояний.
Так, в том же самом примере имеет шансы на все возможные комбинации: это роялфлаш, карэ, фулхаус, флаш, стрит, 2 пары и т.д. Всего, допустим, 9 "да". Положим , мы уничтожим всё, кроме тройки, 2 пары, пара. То есть потеряем 6 возможных будущих состояний. Положив , мы сохраним шанс на флаш, то есть потеряем "всего" 5 ВБС.
Пока попробую новинку по-старому, на строках...