Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Нахождение лучшей комбинации карт

Автор: azesmcar 21.5.2009, 14:01

Добрый день, есть 5 карт, нужно найти лучшую комбинацию которую можно составить из этих карт в соответствии с правилами игры в покер. Т.е. 10 J Q K A - Royal Flush 7 8 9 10 J - Straight Flush 4 4 4 4 - Four of a Kind 3 3 3 2 2 - Full House ... и так далее нужно написать функцию которая принимает массив из 5 карт и возвращает комбинацию. есть идеи, но мне не нравятся проверки будут какие-то запутанные, т.е. например проверка pair, 3 of a kind и 4 of a kind практически одно и тоже..но проверка на флэш - очень сильно отличается, если все делать в одной функции - будет запутанно..если разделить - будет медленно. пятой точкой чую что можно красивее и быстрее. Есть такая мысль, сгенерировать какие-то комбинации, хранить хэш, можно текстовый, можно числовой..не актуально. Короче из карт вычислять какое-то значение и проверять с заранее сгенерированными. Хочу сделать что-то вроде этого.. Код hash_type hash = calc_hash(cards); CComb::iterator it = combinations.find( hash ); if (it != combinations.end())     return it->second; return 0; есть идеи как можно сгенерировать и этот хранить хэш? хранить все возможные комбинации разумеется нереально

Автор: Akina 21.5.2009, 14:22

Формализуй карты и проверяй по шаблонам.

Автор: azesmcar 21.5.2009, 14:25

Цитата(Akina @  21.5.2009,  14:22 ) Формализуй карты и проверяй по шаблонам.  ээээ...можно подробнее?

Автор: azesmcar 21.5.2009, 20:14

задача решена следующим методом берем массив размером в 13 элементов, инициализируем нулями. пробегаемся по нашим картам и инкрементируем значение по индексу - соответствующему значению нашей карты т.е. (туз - 0 элемент, 2 - первый элемент, 3 - второй элемент...итд) одновременно в цикле устанавлиаем булевый флаг в true - если все карты одной масти и в false если соответственно нет. Потом остается пробежатся по полученному массиву и устанавливаем еще один булевый флаг в true если в массиве есть очередь из 5 карт или очередь из 4 карт начинающаяся с десятки с условием что в картах есть туз (т.е. первый элемент массива - установлен в 1). Дальше все просто. if (is_flash && is_sequence && m[0].is_ace)    return royal_flush; else if (is_flash && is_sequence)     return straight_flush; ...и так далее. это в принципе решение для будущего поколения. Но все же  1. хотелось бы услышать мнения    2. хотелось бы все таки описанным в самом начале методе (хэшированием)

Автор: LOD77 22.5.2009, 17:18

Предлагаю следующий принцип представления данных Я не очень знаком с правилами покера. Предполагается что масти карт в нем равнозначны. Тогда каждую карту (ее номинал) кодируем в пятиричной системе счисления. То есть 2-ки будут единицами, 3-ки пятерками, 4-ки 25-ками 5- 125 6 - 625 7 - 3125 8 - 15625 9 - 78125 10 - 390625 J - 1953125 Q - 9765625 K - 48828125 A - 244140625 Все как раз укладывается в длинное целое (32 разряда) После этого каждую покерную комбинацию кодируем. То есть для 10 J Q K A - Royal Flush получим: 1*390625+1*1953125+1*9765625+1*48828125+1*244140625, а для 3 3 3 2 2 - Full House получим: 3*5+2*1 после этого исходную комбинацию карт тоже кодируем, а дальше (внимание!) выполняем над исходной комбинацией карт и  очередной покерной комбинацией (можно по возрастанию до конца, но лучше по убыванию до первой встречной) операцию аналогичную "логическому И" (AND). И если результат совпал с покерной комбинацией, то это она и есть. Теперь поподробнее об операции "логическое И" Выполняется поразрядно без переноса. Принцип следующий: результатом соответствующего разряда является "пересечение" множеств элементов в операндах. То есть в нашем случае это классический MIN. То есть если в исходной комбинации 3 двойки, а в покерной только 1, то результатом будет одна двойка. Ну например: Разряды:                        A Q J 10 9 8 7 6 5 4 3 2 Покерная комбинация: 0 0 1 1   1 1 1 0 0 0 0 0 Исходная комбинация: 1 0  2 0  1 0 1 0 0 0 0 0 Результат:                     0 0 1  0  1 0 1 0 0 0 0 0  Как мы видим, результат не совпал с покерной комбинацией, следовательно ее там нет. Ну вот где-то так видится...

Автор: azesmcar 23.5.2009, 09:39

LOD77,     большое спасибо за старания Цитата(LOD77 @  22.5.2009,  17:18 ) Я не очень знаком с правилами покера. Предполагается что масти карт в нем равнозначны. они равносильны, но... 1. таких комбинаций очень много это не только  3 3 3 2 2 а еще и 4 4 4 2 2, 4 4 4 3 3, 4 4 4 5 5 ... их очень много, это первая проблема 2. насчет масти, если все карты одной масти - это влияет на комбинацию. В любом случае большое спасибо, буду думать насчет того как изменить чтобы избавится от вышеупомянутых недостатков.

Автор: Soah 23.5.2009, 19:22

azesmcar, если изменить немного твой вариант, то можно сделать с комбинациями. Разделяем хэш на четыре части: 1. сколько раз повторяется каждая карта - 5 символов 2. очередь из 5 карт - 1 символ(нет-0, да-1) 3. все 5 карт одинаковой масти - 1 символ(нет-0, да-1) 4. очередь из 5 карт, все 5 карт одинаковой масти, есть туз и 10 - 1 символ(нет-0, да-1) Получаем такую таблицу: 11111:1:1:1 - royal flush 11111:1:1:0 - straight flush 41000:0:0:0 - four of a kind 14000:0:0:0 - four of a kind 32000:0:0:0 - full house 23000:0:0:0 - full house 11111:0:1:0 - flush 11111:1:0:0 - straight 11300:0:0:0 - three of a kind 13100:0:0:0 - three of a kind 31100:0:0:0 - three of a kind 12200:0:0:0 - two pairs 21200:0:0:0 - two pairs 22100:0:0:0 - two pairs 11120:0:0:0 - one pairs 11210:0:0:0 - one pairs 12110:0:0:0 - one pairs 21110:0:0:0 - one pairs Получаем комбинацию: 1. Сортируем карты 2. берем массив размером в 13 элементов, инициализируем нулями 3. пробегаемся по нашим картам и инкрементируем значение по индексу - соответствующему значению нашей карты 4. берем строку размером в 5 элементов, инициализируем нулями("00000") 5. пробегаемся по массиву, и если там не нуль, то добавляем число в строку - получаем первую часть хэша 6. проверяем есть ли очередь из 5 карт - получаем вторую часть хэша 7. проверяем если одинаковая масти - получаем третью часть хэша 8. проверяем если royal flush(очередь из 5 карт, все 5 карт одинаковой масти, есть туз и 10) 9. соединяем все части

Автор: azesmcar 25.5.2009, 14:35

Soah  то что надо, а теперь становится видно самое главное, это медленее чем мой вариант, так как считать это все так и так надо, а тут еще поиск по хэшу   если вдуматься - все что написано делать надо - хочешь не хочешь. т.е. это минимум, дальше либо искать, либо просто возвращать через условия. Условий не так много, в принципе смысла хешировать я так думаю нет, быстрее все равно не выйдет  Спасибо.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)