java - ポーカーハンド評価の最も単純なアルゴリズム

Question

でポーカーハンド（5枚）の評価を考えていJavaます。今は、パフォーマンスや効率よりも単純さと明快さを求めています。おそらく「素朴な」アルゴリズムを書くことはできますが、それには多くのコードが必要です。

ハッシュとビット演算を使用するいくつかのポーカー評価ライブラリも見ましたが、かなり複雑に見えます。

ポーカーハンド評価の「最もクリーンでシンプルな」アルゴリズムは何ですか?

Answer 1

ルックアップ テーブルは、この問題に対する最も簡単で簡単な解決策であり、最速の解決策でもあります。秘訣は、テーブルのサイズを管理し、非常に迅速に処理できるように使用モードをシンプルに保つことです (空間と時間のトレードオフ)。明らかに、理論的には、保持できる各ハンドをエンコードし、評価の配列を持つことができます。それから --poof- 1 つのテーブル ルックアップで完了です。残念なことに、そのようなテーブルは巨大で、ほとんどのマシンでは管理しきれず、メモリが大量にスワップ アウトされるため、いずれにせよ常にディスクをスラッシングすることになります。

いわゆる 2 プラス 2 ソリューションは、10M の大きなテーブルを備えていますが、文字通り、ハンド内のカードごとに 1 つのテーブル ルックアップが必要です。より高速で簡単に理解できるアルゴリズムを見つけることはまずありません。

他のソリューションでは、より複雑なインデックスを使用してより圧縮されたテーブルが使用されますが、それらは簡単に理解でき、非常に高速です (ただし、2+2 よりもはるかに低速です)。ここでは、ハッシュなどに関する言語 (テーブル サイズをより管理しやすいサイズに縮小するためのトリック) について説明します。

いずれにせよ、ルックアップ ソリューションは、ヒストグラム ソート ダンス オン ユア ヘッド比較スペシャル ケース アンド バイ ザ ウェイ ワス イット ア フラッシュ ソリューションよりも桁違いに高速であり、ほとんどありません。そのうち、一見に値するものがあります。

Answer 2

これは、ホールデムの手で機能する dansalmo のプログラムの修正版です。

def holdem(board, hands):
    scores = [(evaluate((board + ' ' + hand).split()), i) for i, hand in enumerate(hands)]
    best = max(scores)[0]
    return [x[1] for x in filter(lambda(x): x[0] == best, scores)]

def evaluate(hand):
    ranks = '23456789TJQKA'
    if len(hand) > 5: return max([evaluate(hand[:i] + hand[i+1:]) for i in range(len(hand))])
    score, ranks = zip(*sorted((cnt, rank) for rank, cnt in {ranks.find(r): ''.join(hand).count(r) for r, _ in hand}.items())[::-1])
    if len(score) == 5: # if there are 5 different ranks it could be a straight or a flush (or both)
        if ranks[0:2] == (12, 3): ranks = (3, 2, 1, 0, -1) # adjust if 5 high straight
        score = ([1,(3,1,2)],[(3,1,3),(5,)])[len({suit for _, suit in hand}) == 1][ranks[0] - ranks[4] == 4] # high card, straight, flush, straight flush
    return score, ranks

def test():
    print holdem('9H TC JC QS KC', [
        'JS JD', # 0
        'AD 9C', # 1 A-straight
        'JD 2C', # 2
        'AC 8D', # 3 A-straight
        'QH KH', # 4
        'TS 9C', # 5
        'AH 3H', # 6 A-straight
        '3D 2C', # 7
      # '8C 2C', # 8 flush
    ])

test()

holdem() は、勝ったハンドのインデックスのリストを返します。test() の例では、[1, 3, 6] です。これは、エースを持つ 3 つのハンドがポットを分割するためです。または、フラッシュ ハンドがコメントされていない場合は [8] です。

Answer 3

たとえば、Cardオブジェクトの配列として手を表現している場合は、この配列をループして、2種類のフラッシュなどがあるかどうか、ある場合はどのタイプかを判断するためのメソッドがあります。それは; 3ofaKind()したがって、ハンドに5が3つある場合、メソッドは5を返すことができます。次に、可能性の階層を確立し（たとえば、ある種の3つはある種の2つよりも高い）、そこから作業します。メソッド自体は非常に簡単に記述できるはずです。

Answer 4

ここでどのように機能するかを理解したい場合は、単純なアルゴリズムを次に示します。

HandStrength(ourcards,boardcards)
{
    ahead = tied = behind = 0
    ourrank = Rank(ourcards,boardcards)
    /* Consider all two-card combinations
    of the remaining cards. */
    for each case(oppcards)
    {
        opprank = Rank(oppcards,boardcards)
        if(ourrank>opprank)
            ahead += 1
        else if(ourrank==opprank)
            tied += 1
        else /* < */
            behind += 1
    }
    handstrength = (ahead+tied/2) / (ahead+tied+behind)
    return(handstrength)
}

Darse Billings 著「ALGORITHMS AND ASSESSMENT IN COMPUTER POKER」より。