быстрый покер рука рейтинг

Question

Я работаю над моделированием покера и теперь я должен эффективно ранжировать руки:

Каждая рука представляет собой комбинацию из 5 карт и представлена ​​как uint64_t.
Каждый бит от 0 (Туз пик), 1 (Туз сердец) до 51 (Два из клубов) указывает, является ли соответствующая карта частью (бит == 1) или не является частью (бит == 0) рука. Биты от 52 до 63 всегда равны нулю и не содержат никакой информации.

Я уже знаю, как теоретически я мог бы создать таблицу, так что каждая действительная рука может быть отображена для отображения (представлена ​​как uint16_t) между 1 (2,3,4,5,7 - не одного цвета) и 7462 (Royal Flush), а остальные - до нулевого нуля.

Так наивная таблица поиска (с целочисленным значением карты в качестве индекса) будет иметь размер 2 bytes * 2^52 >= 9.007 PBогромных.
Большая часть этой памяти будет заполнена нулями, потому что почти все uint64_t - от 0 до 2^52-1 являются недопустимыми руками, и поэтому они имеют значение, равное нулю.
Ценные данные занимают только 2 bytes * 52!/(47!*5!) = 5.198 MB.

Какой метод я могу использовать для сопоставления, так что мне нужно сохранить только ряды от действительных карточек и некоторые накладные расходы (не более 100 МБ) и все равно не нужно делать дорогой поиск ... должен быть как можно быстрее!

Если у вас есть другие идеи, добро пожаловать! ;)

Answer 1

Если я правильно понимаю вашу схему, вам нужно только знать, что вес вздоха конкретной руки составляет ровно 5, чтобы она была действительной рукой. См. Calculating Hamming Weight in O(1) для получения информации о том, как рассчитать вес помех.

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

Answer 2

Вам нужна только таблица из 13^5 * 2, с дополнительным уровнем информации, диктующим, если все карты одного и того же костюма. Если по какой-либо причине «сердце» превосходит «бриллиант», вам все равно нужен стол размером 13^6, поскольку последний фрагмент информации кодируется как «0 = нет рисунка, 1 = все лопаты, 2 = все сердца, и т.д.'.

Хэш-таблица, вероятно, также является хорошим и быстрым подходом. Создание таблицы из комбинаций nCk (52,5) не занимает много времени (по сравнению со всеми возможными руками). Тем не менее, нужно было хранить 65 бит информации для каждой записи для хранения как ключа (52 бит), так и ранга (13 бит).

Ускорение оценки руки, сначала исключает незаконные комбинации из маски:
if (popcount(mask) != 5); после этого один раз может использовать достаточное количество бит, например. crc32 (маска), которая, по крайней мере, имеет поддержку уровня инструкций в i7-архитектуре.

Answer 3

Простая реализация, которая приходит на ум, состоит в том, чтобы изменить вашу схему на 5-значное число в базе 52. Полученная таблица для хранения всех этих значений будет по-прежнему больше, чем необходимо, но очень проста в реализации, и это будет легко вписываться в ОЗУ на современных компьютерах.

Редакция:

Редактирование: вы также можете сократить еще больше, только сохраняя ранг каждой карты и дополнительный флаг (например,, самый младший бит), чтобы указать, все ли карты одного и того же костюма (т. е. возможна флеш). Тогда это будет в базе 13 + один бит для представления ранжирования. Возможно, вам, вероятно, потребуется отдельно хранить конкретные макеты карт, чтобы восстановить точную руку для отображения и т. Д.

Answer 4

Я бы представлял вашу руку по-другому: Есть только 4 костюма = 2 бита и только 13 карт = 4 бита в общей сложности 6 бит * 5 = 30 - поэтому мы вписываемся в 32-битный int - мы можем также заставляйте это всегда сортироваться согласно вашему заказу.

[костюм 0] [костюм 1] [костюм 2] [костюм 3] [костюм 4] [значение 0] [значение 1] [значение 2] [значение 3 ] [значение 4]

Затем я хотел бы использовать отдельный хеш для:

• consectutive значений (очень маленький) [замаскировать костюмы]
• 1 или более кратные (пара, 2 пары, полный дом) [маска с костюмами]
• костюмов, которые все же (очень маленькими) [замаскировать значения]

Затем с помощью 3 хэши рассчитать свой рейтинг в 5МБ вы, вероятно, имеют достаточно проблем кэширования, которые будут иметь немного математики и три маленьких Lookups быстрее

Answer 5

Это является хорошим источником
Cactus Kev's

Для стороны, вы можете воспользоваться не более 4 любой масти
4 бита для ранга (0-12) и 2 бита для костюма
6 бит * 5 карточки только 30 бит
Называйте это 4 байта
Есть только 2598960 стрелки
Общая стоимость чуть меньше 10 мб