Я знаю, что вы сказали, что хотите сохранить как можно меньший объем памяти, но есть одна оптимизация таблицы поиска с эффективным использованием памяти, которую я видел в некоторых оценщиках покерных рук, и я использовал ее сам.Если вы занимаетесь тяжелыми покерными симуляциями и вам нужна максимальная производительность, вы можете подумать об этом.Хотя я признаю, что в этом случае разница не так уж велика, потому что тестирование на стрит-дро не очень дорогая операция, но тот же принцип можно использовать практически для любого типа оценки рук в покерном программировании.
Идея состоит в том, что мы создаем своего рода хеш-функцию, которая имеет следующие свойства:
1) вычисляет уникальное значение для каждого различного набора рангов карт
2) является симметричной в том смысле, что она независит от порядка карточек
Цель этого состоит в том, чтобы уменьшить количество элементов, необходимых в справочной таблице.
Удобный способ сделать это - назначить простое число каждому рангу (2-> 2, 3-> 3, 4-> 5, 5-> 7, 6-> 11, 7-> 13, 8-> 17, 9-> 19, T-> 23, J-> 29, Q-> 31, K-> 37, A-> 41), а затем вычислите произведение простых чисел.Например, если карты 39TJQQ, то хеш 36536259.
Чтобы создать таблицу поиска, вы проходите все возможные комбинации рангов и используете некоторый простой алгоритм, чтобы определить, образуют ли они стрит-дро.Для каждой комбинации вы также вычисляете значение хеша, а затем сохраняете результаты на карте, где Key - это хеш, а Value - результат проверки на прямую ничью.Если максимальное количество карточек невелико (4 или меньше), то возможен даже линейный массив.
Чтобы использовать таблицу поиска, сначала необходимо вычислить хеш для определенного набора карточек, а затем прочитать соответствующее значение.с карты.
Вот пример на C ++.Я не гарантирую, что он работает правильно и, вероятно, его можно было бы оптимизировать, используя отсортированный массив и бинарный поиск вместо hash_map.hash_map довольно медленный для этой цели.
#include <iostream>
#include <vector>
#include <hash_map>
#include <numeric>
using namespace std;
const int MAXCARDS = 9;
stdext::hash_map<long long, bool> lookup;
//"Hash function" that is unique for a each set of card ranks, and also
//symmetric so that the order of cards doesn't matter.
long long hash(const vector<int>& cards)
{
static const int primes[52] = {
2,3,5,7,11,13,17,19,23,29,31,37,41,
2,3,5,7,11,13,17,19,23,29,31,37,41,
2,3,5,7,11,13,17,19,23,29,31,37,41,
2,3,5,7,11,13,17,19,23,29,31,37,41
};
long long res=1;
for(vector<int>::const_iterator i=cards.begin();i!=cards.end();i++)
res *= primes[*i];
return res;
}
//Tests whether there is a straight draw (assuming there is no
//straight). Only used for filling the lookup table.
bool is_draw_slow(const vector<int>& cards)
{
int ranks[14];
memset(ranks,0,14*sizeof(int));
for(vector<int>::const_iterator i=cards.begin();i!=cards.end();i++)
ranks[ *i % 13 + 1 ] = 1;
ranks[0]=ranks[13]; //ace counts also as 1
int count = ranks[0]+ranks[1]+ranks[2]+ranks[3];
for(int i=0; i<=9; i++) {
count += ranks[i+4];
if(count==4)
return true;
count -= ranks[i];
}
return false;
};
void create_lookup_helper(vector<int>& cards, int idx)
{
for(;cards[idx]<13;cards[idx]++) {
if(idx==cards.size()-1)
lookup[hash(cards)] = is_draw_slow(cards);
else {
cards[idx+1] = cards[idx];
create_lookup_helper(cards,idx+1);
}
}
}
void create_lookup()
{
for(int i=1;i<=MAXCARDS;i++) {
vector<int> cards(i);
create_lookup_helper(cards,0);
}
}
//Test for a draw using the lookup table
bool is_draw(const vector<int>& cards)
{
return lookup[hash(cards)];
};
int main(int argc, char* argv[])
{
create_lookup();
cout<<lookup.size()<<endl; //497419
int cards1[] = {1,2,3,4};
int cards2[] = {0,1,2,7,12};
int cards3[] = {3,16,29,42,4,17,30,43};
cout << is_draw(vector<int>(cards1,cards1+4)) <<endl; //true
cout << is_draw(vector<int>(cards2,cards2+5)) <<endl; //true
cout << is_draw(vector<int>(cards3,cards3+8)) <<endl; //false
}