Вопрос по java, algorithm, r – Самый простой алгоритм оценки покерных рук

21

Я думаю об оценке покерной руки (5 карт) вJava, Теперь я ищу простоту и ясность, а не производительность и эффективность. Я, вероятно, могу написать «наивный» алгоритм, но он требует много кода.

Я также видел несколько библиотек для оценки покера, которые используют хеширование и побитовые операции, но они выглядят довольно сложными.

Что является «самым чистым и простым»? алгоритм оценки покерных рук?

@iccthedral Мне не очень понравилось, оценка всех 21 комбинаций из 5 карт в наборе из 7 карт кажется очень неэффективной. Существуют алгоритмы для определения лучшей раздачи из 7 карт без необходимости рассматривать каждую комбинацию, и алгоритм немного сложнее, чем алгоритм для 5 карт. DPM
В разделе «связанные» есть много (вероятно) релевантных вопросов. боковая панель справа. Никто из них не отвечает на ваш вопрос? Oliver Charlesworth
Это очень просто, чисто и хорошо объяснено:nsayer.blogspot.com/2007/07/… nullpotent
@OliCharlesworth Я видел в основном ссылки на существующие библиотеки Michael

Ваш Ответ

9   ответов
1

R, протестирован с колодой из 6 карт, что соответствует 42,504 комбинациям, полученным в результате:

C65

комбинации покерных комбинаций Не тестировалось с колодой из 13 карт из-за ограничений по обработке (это будет соответствовать 2.598.960 комбинациям).

Алгоритм представляетvalue of a hand by a stringсостоит из 2 частей:

5 character with ordered card count (ex. "31100" means three of a kind) The card numbers are valued by letters from 'B' (Deuce) to 'N' (Ace) (ex. 'NILH' means Ace, Queen, Nine and Eight). It starts in letter 'B' because of the A2345 poker hand where the Ace comes before the '2' which (the Ace) will have the value 'A'.

Так, например, «32000NB» будет фулл-хаус из трех тузов и двух двойок.

Строка значения покерной руки удобнаfor comparative and ordering purposes.

library(tidyverse)
library(gtools)

hand_value <- function(playerhand) {

  numbers <- str_split("23456789TJQKA", "")[[1]]
  suits <- str_split("DCHS", "")[[1]]

  playerhand <- data.frame(card = playerhand) %>% separate(card, c("number", "suit"), sep = 1)

  number_values <- data.frame(number = numbers, value = LETTERS[2:14], stringsAsFactors = FALSE)

  playerhand_number <- playerhand %>% 
    group_by(number) %>% 
    count(number) %>%
    inner_join(number_values, by = "number") %>%
    arrange(desc(n), desc(value))

  playerhand_suit <- playerhand %>% 
    group_by(suit) %>% 
    count(suit) %>%
    arrange(desc(n))

  if (nrow(playerhand_number) == 5)
    {
      if (playerhand_number[1,1] == 'A' & playerhand_number[2,1] == '5')
        playerhand_number <- data.frame(playerhand_number[,1:2], value = str_split("EDCBA", "")[[1]], stringsAsFactors = FALSE)
      straight <- asc(playerhand_number[1,3]) - asc(playerhand_number[5,3]) == 4
    } else
      straight = FALSE

  flush <- nrow(playerhand_suit) == 1

  if (flush)
    {
    if (straight)
      playerhand_number <- data.frame(playerhand_number[,c(1,3)], n = c(5, 0, 0, 0, 0), stringsAsFactors = FALSE) else
      playerhand_number <- data.frame(playerhand_number[,c(1,3)], n = c(3, 1, 1, 2, 0), stringsAsFactors = FALSE)
    } else
    {
    if (straight)
      playerhand_number <- data.frame(playerhand_number[,c(1,3)], n = c(3, 1, 1, 1, 0), stringsAsFactors = FALSE)
    }  

  playerhand_value <- append(append(c(playerhand_number$n), rep("0", 5 - nrow(playerhand_number))), c(playerhand_number$value))
  playerhand_value <- paste(playerhand_value, collapse = '')

  playerhand_value

}

Тестирование функции теми же руками, что и в примере выше:

l <- c("8C TS KC 9H 4S", "7D 2S 5D 3S AC", "8C AD 8D AC 9C", '7C 5H 8D TD KS')
t <- as_tibble(l)
t <- t %>% mutate(hand = str_split(value, " ")) %>% select(hand)
t <- t %>% mutate(value = sapply(t[,1]$hand, hand_value)) %>% arrange(desc(value))
paste(t[[1]][[1]], collapse = " ")

Который возвращает тот же результат:

[1] "8C AD 8D AC 9C"

Надеюсь, поможет.

5

все это может быть сделано побитовым: (source:http://www.codeproject.com/Articles/569271/A-Poker-hand-analyzer-in-JavaScript-using-bit-math)

(This one is actually written in JavaScript, but you can evaluate JavaScript from Java if needed, so it shouldn't be a problem. Also, this is as short as it gets, so if even for illustration of the approach...):

Сначала вы разбиваете свои карты на два массива: ранги (cs) и масти (ss), и для представления мастей вы будете использовать 1,2,4 или 8 (то есть 0b0001, 0b0010, ...):

var J=11, Q=12, K=13, A=14, C=1, D=2, H=4, S=8;

Теперь вот магия:

function evaluateHand(cs, ss) {
    var pokerHands = ["4 of a Kind", "Straight Flush","Straight","Flush","High Card","1 Pair","2 Pair","Royal Flush", "3 of a Kind","Full House"];

    var v,i,o,s = 1 << cs[0] | 1 << cs[1] | 1 << cs[2] | 1 << cs[3] | 1 << cs[4];
    for (i = -1, v = o = 0; i < 5; i++, o = Math.pow(2, cs[i] * 4)) {v += o * ((v / o & 15) + 1);}
    v = v % 15 - ((s / (s & -s) == 31) || (s == 0x403c) ? 3 : 1);
    v -= (ss[0] == (ss[1] | ss[2] | ss[3] | ss[4])) * ((s == 0x7c00) ? -5 : 1);
    return pokerHands[v];
}

Использование:

evaluateHand([A,10,J,K,Q],[C,C,C,C,C]); // Royal Flush

Теперь то, что он делает (очень кратко), это то, что он помещает 1 в 3-й битs когда есть 2, в 4-е, когда есть 3 и т. д., так что для приведенного выше примераs выглядит так:

0b111110000000000

для [A, 2,3,4,5] это будет выглядеть так

0b100 0000 0011 1100

и т.п.

v использует четыре бита для записи нескольких вхождений одной и той же карты, поэтому ее длина составляет 52 бита, и если у вас три туза и два короля, его 8 бит MSB выглядят следующим образом:

0111 0011 ...

Последняя строка затем проверяет наличие флеша, стрит-флеша или королевского флеша (0x7c00).

Я думаю, что было бы разумно включить ваш источник:codeproject.com/Articles/569271/… Большая статья, кстати.
Конечно, извините за это. Сделал правку для ссылки на статью также в ответе.
1

class PokerHand constructor(hand: String) : Comparable<PokerHand> {

companion object {
    const val WIN = 1
    const val TIE = 0
    const val LOSS = -1
}

val cards: List<Card>

val isStraightFlush: Boolean
    get() = isStraight && isFlush

val isFourOfAKind: Boolean
    get() = cards.groupBy { it.weight }.map { it.value }.any { it.size == 4 }

val isFullHouse: Boolean
    get() = cards.groupBy { it.weight }.map { it.value }.size == 2

val isFlush: Boolean
    get() = cards.groupBy { it.suit }.map { it.value }.size == 1

val isStraight: Boolean
    get() = cards.map { it.weight.ordinal } == (cards[0].weight.ordinal..cards[0].weight.ordinal + 4).toList()

val isThreeOfAKind: Boolean
    get() = cards.groupBy { it.weight }.map { it.value }.any { it.size == 3 }

val isTwoPair: Boolean
    get() = cards.groupBy { it.weight }.map { it.value }.filter { it.size == 2 }.count() == 2

val isPair: Boolean
    get() = cards.groupBy { it.weight }.map { it.value }.any { it.size == 2 }

init {
    val cards = ArrayList<Card>()
    hand.split(" ").forEach {
        when (it.length != 2) {
            true -> throw RuntimeException("A card code must be two characters")
            else -> cards += Card(Weight.forCode(it[0]), Suit.forCode(it[1]))
        }
    }
    if (cards.size != 5) {
        throw RuntimeException("There must be five cards in a hand")
    }
    this.cards = cards.sortedBy { it.weight.ordinal }
}

override fun compareTo(other: PokerHand): Int = when {
    (this.isStraightFlush || other.isStraightFlush) ->
        if (this.isStraightFlush) if (other.isStraightFlush) compareByHighCard(other) else WIN else LOSS
    (this.isFourOfAKind || other.isFourOfAKind) ->
        if (this.isFourOfAKind) if (other.isFourOfAKind) compareByHighCard(other) else WIN else LOSS
    (this.isFullHouse || other.isFullHouse) ->
        if (this.isFullHouse) if (other.isFullHouse) compareByHighCard(other) else WIN else LOSS
    (this.isFlush || other.isFlush) ->
        if (this.isFlush) if (other.isFlush) compareByHighCard(other) else WIN else LOSS
    (this.isStraight || other.isStraight) ->
        if (this.isStraight) if (other.isStraight) compareByHighCard(other) else WIN else LOSS
    (this.isThreeOfAKind || other.isThreeOfAKind) ->
        if (this.isThreeOfAKind) if (other.isThreeOfAKind) compareByHighCard(other) else WIN else LOSS
    (this.isTwoPair || other.isTwoPair) ->
        if (this.isTwoPair) if (other.isTwoPair) compareByHighCard(other) else WIN else LOSS
    (this.isPair || other.isPair) ->
        if (this.isPair) if (other.isPair) compareByHighCard(other) else WIN else LOSS
    else -> compareByHighCard(other)
}

private fun compareByHighCard(other: PokerHand, index: Int = 4): Int = when {
    (index < 0) -> TIE
    cards[index].weight === other.cards[index].weight -> compareByHighCard(other, index - 1)
    cards[index].weight.ordinal > other.cards[index].weight.ordinal -> WIN
    else -> LOSS
}

}

Детали реализации:

Instantiate with a coded hand, eg 2H 3H 4H 5H 6H Methods to evaluate whether the hand is a 'Straight Flush', 'Four of a Kind', 'Full House' etc. These are easy to express in Kotlin. Implements Comparable<PokerHand> to evaluate against another hand using a simple rules approach, eg a straight flush beats four of a kind, which beats a full house, and so forth.

Источникиздесь.

спасибо, открыл проблему, чтобы исправить.
Вы не можете сравнивать по старшей карте, чтобы решить, когда обе руки - пары, поездки и т. д. 4S 4C AS 2D 2H, бьет 8D 8H 3H 4H 5H, старшая пара должна выиграть
11

а также самое быстрое. Хитрость заключается в том, чтобы управлять размером таблицы и поддерживать режим использования достаточно простым для очень быстрой обработки (пространство & # x2013; компромисс времени). Очевидно, что теоретически вы можете просто закодировать каждую руку, которую можно держать, и получить массив оценок, а затем --poof-- поиск одной таблицы, и все готово. К сожалению, такая таблица была бы огромной и неуправляемой для большинства машин, и в любом случае она всегда приводила бы к перегрузке дисков, когда объем памяти менялся.

Так называемое решение «два плюс два» имеет большой 10М стол, но буквально предполагает поиск по одной таблице для каждой карты в руке. Вы вряд ли найдете более быстрый и простой для понимания алгоритм.

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

В любом случае, решения для поиска на несколько порядков быстрее, чем решения для гистограммы «сортируй-танцуй-на-голове-сравни---------то-и-то-то-все-все», почти нет из которых достойны второго взгляда.

30

но полная гистограмма, основанная на пятикарточной покерной функции в Python (2.x). Это будет значительно дольше, если преобразовать в Java.

def poker(hands):
    scores = [(i, score(hand.split())) for i, hand in enumerate(hands)]
    winner = sorted(scores , key=lambda x:x[1])[-1][0]
    return hands[winner]

def score(hand):
    ranks = '23456789TJQKA'
    rcounts = {ranks.find(r): ''.join(hand).count(r) for r, _ in hand}.items()
    score, ranks = zip(*sorted((cnt, rank) for rank, cnt in rcounts)[::-1])
    if len(score) == 5:
        if ranks[0:2] == (12, 3): #adjust if 5 high straight
            ranks = (3, 2, 1, 0, -1)
        straight = ranks[0] - ranks[4] == 4
        flush = len({suit for _, suit in hand}) == 1
        '''no pair, straight, flush, or straight flush'''
        score = ([1, (3,1,1,1)], [(3,1,1,2), (5,)])[flush][straight]
    return score, ranks

 >>> poker(['8C TS KC 9H 4S', '7D 2S 5D 3S AC', '8C AD 8D AC 9C', '7C 5H 8D TD KS'])
 '8C AD 8D AC 9C'
Python 3 не позволяет сравнивать разные типы, как это делал 2.x. Это, вероятно, связано с родом. Увидетьpeterbe.com/plog/sorting-mixed-type-lists-in-python-3
Код из вышеупомянутой dansalmo, безусловно, является самой элегантной версией, однако он не работает в Python 3, поскольку выдает ошибку: & quot; TypeError: неупорядоченные типы: tuple () & lt; Int () & Quot ;. Может быть, в этом есть ошибка, когда кортеж сравнивается с int?
Это не работает, оно выберет тройку по сравнению со стритом.poker(['JC JH JD 5C 8D', '2D 3C 4S 5D 6C']) вернусь'JC JH JD 5C 8D'
Вы должны быть в состоянии исправить это простым использованиемscore = ([1, (3,1,1,1)], [(3,1,1,2), (5,)])[flush][straight]
Неверный язык.
4

которая работает для холдем-рук:

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], поскольку три руки с тузами делят банк, или [8], если флеш-рука не прокомментирована.

3

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)
}

Это от "Алгоритмы и оценки в компьютерном покере" Дарс Биллингс.

4

который я использую для начального заполнения таблицы поиска:

https://gist.github.com/gdejohn/8293321#file-hand-java

Вместо того, чтобы быть как можно более кратким, я поставил во главу угла безопасность типов и четкий, самодокументированный код. Если вы не знакомы с типами гуавы, которые я использую, вы можете просмотреть ихдокументация.

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

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.collect.Ordering.from;
import static com.google.common.collect.Ordering.natural;
import static java.util.Comparator.comparing;
import static java.util.Comparator.comparingInt;

import java.util.Comparator;
import java.util.EnumSet;
import java.util.LinkedList;
import java.util.Set;
import java.util.function.Function;

import com.google.common.collect.EnumMultiset;
import com.google.common.collect.Multiset;
import com.google.common.collect.Multiset.Entry;
import com.google.common.collect.Ordering;

public class Hand implements Comparable<Hand> {
    public final Category category;

    private final LinkedList<Rank> distinctRanks = new LinkedList<>();

    public Hand(Set<Card> cards) {
        checkArgument(cards.size() == 5);
        Set<Suit> suits = EnumSet.noneOf(Suit.class);
        Multiset<Rank> ranks = EnumMultiset.create(Rank.class);
        for (Card card : cards) {
            suits.add(card.suit);
            ranks.add(card.rank);
        }
        Set<Entry<Rank>> entries = ranks.entrySet();
        for (Entry<Rank> entry : byCountThenRank.immutableSortedCopy(entries)) {
            distinctRanks.addFirst(entry.getElement());
        }
        Rank first = distinctRanks.getFirst();
        int distinctCount = distinctRanks.size();
        if (distinctCount == 5) {
            boolean flush = suits.size() == 1;
            if (first.ordinal() - distinctRanks.getLast().ordinal() == 4) {
                category = flush ? STRAIGHT_FLUSH : STRAIGHT;
            }
            else if (first == ACE && distinctRanks.get(1) == FIVE) {
                category = flush ? STRAIGHT_FLUSH : STRAIGHT;
                // ace plays low, move to end
                distinctRanks.addLast(distinctRanks.removeFirst());
            }
            else {
                category = flush ? FLUSH : HIGH_CARD;
            }
        }
        else if (distinctCount == 4) {
            category = ONE_PAIR;
        }
        else if (distinctCount == 3) {
            category = ranks.count(first) == 2 ? TWO_PAIR : THREE_OF_A_KIND;
        }
        else {
            category = ranks.count(first) == 3 ? FULL_HOUSE : FOUR_OF_A_KIND;
        }
    }

    @Override
    public final int compareTo(Hand that) {
        return byCategoryThenRanks.compare(this, that);
    }

    private static final Ordering<Entry<Rank>> byCountThenRank;

    private static final Comparator<Hand> byCategoryThenRanks;

    static {
        Comparator<Entry<Rank>> byCount = comparingInt(Entry::getCount);
        Comparator<Entry<Rank>> byRank = comparing(Entry::getElement);
        byCountThenRank = from(byCount.thenComparing(byRank));
        Comparator<Hand> byCategory = comparing((Hand hand) -> hand.category);
        Function<Hand, Iterable<Rank>> getRanks =
                (Hand hand) -> hand.distinctRanks;
        Comparator<Hand> byRanks =
                comparing(getRanks, natural().lexicographical());
        byCategoryThenRanks = byCategory.thenComparing(byRanks);
    }

    public enum Category {
        HIGH_CARD,
        ONE_PAIR,
        TWO_PAIR,
        THREE_OF_A_KIND,
        STRAIGHT,
        FLUSH,
        FULL_HOUSE,
        FOUR_OF_A_KIND,
        STRAIGHT_FLUSH;
    }

    public enum Rank {
        TWO,
        THREE,
        FOUR,
        FIVE,
        SIX,
        SEVEN,
        EIGHT,
        NINE,
        TEN,
        JACK,
        QUEEN,
        KING,
        ACE;
    }

    public enum Suit {
        DIAMONDS,
        CLUBS,
        HEARTS,
        SPADES;
    }

    public enum Card {
        TWO_DIAMONDS(TWO, DIAMONDS),
        THREE_DIAMONDS(THREE, DIAMONDS),
        FOUR_DIAMONDS(FOUR, DIAMONDS),
        FIVE_DIAMONDS(FIVE, DIAMONDS),
        SIX_DIAMONDS(SIX, DIAMONDS),
        SEVEN_DIAMONDS(SEVEN, DIAMONDS),
        EIGHT_DIAMONDS(EIGHT, DIAMONDS),
        NINE_DIAMONDS(NINE, DIAMONDS),
        TEN_DIAMONDS(TEN, DIAMONDS),
        JACK_DIAMONDS(JACK, DIAMONDS),
        QUEEN_DIAMONDS(QUEEN, DIAMONDS),
        KING_DIAMONDS(KING, DIAMONDS),
        ACE_DIAMONDS(ACE, DIAMONDS),

        TWO_CLUBS(TWO, CLUBS),
        THREE_CLUBS(THREE, CLUBS),
        FOUR_CLUBS(FOUR, CLUBS),
        FIVE_CLUBS(FIVE, CLUBS),
        SIX_CLUBS(SIX, CLUBS),
        SEVEN_CLUBS(SEVEN, CLUBS),
        EIGHT_CLUBS(EIGHT, CLUBS),
        NINE_CLUBS(NINE, CLUBS),
        TEN_CLUBS(TEN, CLUBS),
        JACK_CLUBS(JACK, CLUBS),
        QUEEN_CLUBS(QUEEN, CLUBS),
        KING_CLUBS(KING, CLUBS),
        ACE_CLUBS(ACE, CLUBS),

        TWO_HEARTS(TWO, HEARTS),
        THREE_HEARTS(THREE, HEARTS),
        FOUR_HEARTS(FOUR, HEARTS),
        FIVE_HEARTS(FIVE, HEARTS),
        SIX_HEARTS(SIX, HEARTS),
        SEVEN_HEARTS(SEVEN, HEARTS),
        EIGHT_HEARTS(EIGHT, HEARTS),
        NINE_HEARTS(NINE, HEARTS),
        TEN_HEARTS(TEN, HEARTS),
        JACK_HEARTS(JACK, HEARTS),
        QUEEN_HEARTS(QUEEN, HEARTS),
        KING_HEARTS(KING, HEARTS),
        ACE_HEARTS(ACE, HEARTS),

        TWO_SPADES(TWO, SPADES),
        THREE_SPADES(THREE, SPADES),
        FOUR_SPADES(FOUR, SPADES),
        FIVE_SPADES(FIVE, SPADES),
        SIX_SPADES(SIX, SPADES),
        SEVEN_SPADES(SEVEN, SPADES),
        EIGHT_SPADES(EIGHT, SPADES),
        NINE_SPADES(NINE, SPADES),
        TEN_SPADES(TEN, SPADES),
        JACK_SPADES(JACK, SPADES),
        QUEEN_SPADES(QUEEN, SPADES),
        KING_SPADES(KING, SPADES),
        ACE_SPADES(ACE, SPADES);

        public final Rank rank;

        public final Suit suit;

        Card(Rank rank, Suit suit) {
            this.rank = rank;
            this.suit = suit;
        }
    }
}
2

Card объекты, тогда у меня были бы методы для обхода этого массива и определения, имеет ли он 2-в-роде, сбросить и т. д. - и если да, то какой это тип; чтобы вы могли иметь3ofaKind() метод вернуть 5, если у руки было три 5s. Затем я бы установил иерархию возможностей (например, 3 вида выше, чем 2 вида) и работал бы оттуда. Сами методы должны быть довольно простыми для написания.

Не забывайте, что некоторые 3 в своем роде лучше, чем другие

Похожие вопросы