Tôi biết bạn đã nói rằng bạn muốn giữ chân bộ nhớ càng nhỏ càng tốt, nhưng có một bảng tối ưu hóa bộ nhớ hiệu quả mà tôi từng thấy ở một số người đánh giá bài xì phé và tôi đã sử dụng nó. Nếu bạn đang làm mô phỏng poker nặng và cần hiệu suất tốt nhất có thể, bạn có thể muốn xem xét điều này. Mặc dù tôi thừa nhận trong trường hợp này sự khác biệt không phải là lớn bởi vì thử nghiệm cho một vẽ thẳng không phải là hoạt động rất tốn kém, nhưng nguyên tắc tương tự có thể được sử dụng cho khá nhiều loại đánh giá tay trong lập trình poker.
Ý tưởng là chúng ta tạo ra một loại một hàm băm có các thuộc tính sau:
1) tính toán một giá trị duy nhất cho mỗi bộ khác nhau của thẻ đứng
2) là đối xứng theo nghĩa là nó doesn' t phụ thuộc vào thứ tự của các thẻ
Mục đích của việc này là giảm số lượng thành phần cần thiết trong bảng tra cứu.
Cách gọn gàng để thực hiện việc này là gán một số nguyên tố cho mỗi cấp bậc (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), và sau đó tính toán sản phẩm của số nguyên tố. Ví dụ nếu các thẻ là 39TJQQ, thì băm là 36536259.
Để tạo bảng tra cứu, bạn thực hiện tất cả các kết hợp xếp hạng có thể, và sử dụng một số thuật toán đơn giản để xác định xem chúng có tạo hình thẳng hay không. Đối với mỗi kết hợp, bạn cũng tính toán giá trị băm và sau đó lưu trữ các kết quả trong bản đồ trong đó Khóa là giá trị băm và Giá trị là kết quả của việc kiểm tra vẽ thẳng. Nếu số lượng thẻ tối thiểu nhỏ (4 hoặc ít hơn) thì ngay cả một mảng tuyến tính cũng có thể khả thi.
Để sử dụng bảng tra cứu, trước tiên bạn tính giá trị băm cho tập hợp thẻ cụ thể và sau đó đọc giá trị tương ứng từ bản đồ.
Đây là một ví dụ trong C++. Tôi không đảm bảo rằng nó hoạt động chính xác và nó có thể được tối ưu hóa rất nhiều bằng cách sử dụng một mảng được sắp xếp và tìm kiếm nhị phân thay vì hash_map. hash_map là kinda chậm cho mục đích này.
#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
}
Chỉ cần cho chúng tôi không chơi bài xì phé là gì? – Gorgen
@Gorgen Thẳng là 5 thẻ xếp hạng tiếp theo (ví dụ: A 2 3 4 5 hoặc 9 10 J Q K). Một trận hòa là bốn trong số 5 thẻ yêu cầu trong một thẳng. Một bản vẽ 'mở kết thúc' có nghĩa là 4 thẻ được tuần tự và không bao gồm A - ví dụ, 2 3 4 5 hoặc 8 9 10 J. An 'bên trong' vẽ có nghĩa là các thẻ không tuần tự hoặc bao gồm A - ví dụ, 2 3 5 6 hoặc A 2 3 4. –