1

元の問題の参照: Poker-Monte-Carlo-Simulation の手評価アルゴリズムの最適化

5 から 7 枚のカードのリストがあり、それらの値をハッシュテーブルに格納したいと考えています。ハッシュテーブルは 32 ビット整数の配列であり、インデックスとしてハッシュ関数値によって直接アクセスする必要があります。52 枚のカード デッキで可能な組み合わせの量が多いことに関しては、あまり多くのメモリを浪費したくありません。

数字:

  • 7 カードの組み合わせ: 133784560
  • 6 カードの組み合わせ: 20358520
  • 5 カードの組み合わせ: 2598960
  • 合計: 156.742.040 可能な組み合わせ

1 億 5700 万の 32 ビット整数値を保存するには、約 580MB のコストがかかります。したがって、不要な値のために配列内のメモリを予約することで、この数を増やすことを避けたいと思います。

問題は次のとおりです: ハッシュ関数はどのように見えるでしょうか? 可能性のある重複していないカードの組み合わせを 0 から 156.742.040 までの連続した値にマッピングするか、少なくともそれに近い値にしますか?

4

2 に答える 2

1

Paul Senzee は、これについて 7 枚のカードについて素晴らしい投稿をしています。

彼のコードは基本的に、事前に計算された一連のテーブルと、指定された 7 枚のカードのハンド (カードを表す最下位 52 ビットの 64 ビットの数値として表される) の配列インデックスを検索する 1 つの関数です。

inline unsigned index52c7(unsigned __int64 x)
{
    const unsigned short *a = (const unsigned short *)&x;
    unsigned A    = a[3],                B    = a[2],                        C    = a[1],            D   = a[0],
             bcA  = _bitcount[A],        bcB  = _bitcount[B],                bcC  = _bitcount[C],    bcD = _bitcount[D],
             mulA = _choose48x[7 - bcA], mulB = _choose32x[7 - (bcA + bcB)], mulC = _choose16x[bcD];
    return _offsets52c[bcA]                      + _table4[A] * mulA + 
           _offsets48c[ (bcA << 4)        + bcB] + _table [B] * mulB +
           _offsets32c[((bcA + bcB) << 4) + bcC] + _table [C] * mulC + 
                                                   _table [D];
}

簡単に言えば、完全ハッシュに基づいて事前に計算されたルックアップ テーブルを利用した一連のルックアップとビット単位の演算です。

戻ってこのウェブサイトを見ると、Senzee が 7 カード ハッシュを作成するために使用した完全なハッシュ コードを取得し、5 カード テーブルと 6 カード テーブルのプロセスを繰り返すことができます (基本的index52c7.hに、それぞれに新しいテーブルを作成します)。3 つすべてを 1 つのテーブルにまとめることができるかもしれませんが、私は試していません。

全部で 628 MB (4 バイト * 157 M エントリ) になるはずです。または、それを分割したい場合は、それを 16 ビットの数値にマップし (ほとんどのポーカー ハンド評価者は 7,462 の一意のハンド スコアしか必要としないため)、それら 7,462 のハンド スコアから任意のハンド カテゴリへの別のマップを作成できます。欲しいです。それは 314 MB になります。

于 2016-01-21T11:59:01.137 に答える