java - El algoritmo más simple para la evaluación manual de póquer
algorithm data-structures (7)
Estoy pensando en la evaluación de la mano de póker (5 cartas) en Java . Ahora estoy buscando simplicidad y claridad en lugar de rendimiento y eficiencia. Probablemente pueda escribir un algoritmo "ingenuo" pero requiere mucho código.
También vi algunas bibliotecas de evaluación de póker, que usan hashing y operaciones bit a bit, pero parecen bastante complejas.
¿Cuál es el algoritmo "más limpio y simple" para la evaluación manual de póker?
Aquí hay una versión modificada del programa de dansalmo que funciona para manos holdem:
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 () devuelve una lista de índices de la (s) mano (s) ganadora (s). En el ejemplo de prueba () que es [1, 3, 6], dado que las tres manos con ases dividen el bote, o [8] si la mano de descarga no está comentada.
En realidad, no necesita funciones avanzadas, puede hacerlo todo en bits: (fuente: http://www.codeproject.com/Articles/569271/A-Poker-hand-analyzer-in-JavaScript-using-bit-math )
(Esta en realidad está escrita en JavaScript, pero puede evaluar JavaScript desde Java si es necesario, por lo que no debería ser un problema. Además, esto es lo más corto posible, por lo que si es solo una ilustración del enfoque ...) :
Primero divides tus cartas en dos matrices: rangos (cs) y palos (ss) y para representar a los palos, usarás 1,2,4 u 8 (es decir, 0b0001, 0b0010, ...):
var J=11, Q=12, K=13, A=14, C=1, D=2, H=4, S=8;
Ahora aquí está la magia:
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];
}
Uso:
evaluateHand([A,10,J,K,Q],[C,C,C,C,C]); // Royal Flush
Ahora lo que hace (muy brevemente) es que pone 1 en el 3er bit de s cuando hay un 2, en el 4to cuando hay 3, etc., entonces para el ejemplo anterior s se ve así:
0b111110000000000
para [A, 2,3,4,5] se vería así
0b100 0000 0011 1100
etc.
v usa cuatro bits para registrar múltiples ocurencies de la misma tarjeta, por lo que tiene 52bits de longitud y si tienes tres Ases y dos reyes, sus 8 bits de MSB son como:
0111 0011 ...
La última línea luego verifica si hay color o escalera real (0x7c00).
Esta es una función de puntuación de póker de 5 cartas basada en un histograma muy corta pero completa en Python (2.x). Se convertirá considerablemente más largo si se convierte a 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''
Este es un enfoque ingenuo para la comparación de cinco tarjetas con la mano que estoy usando para ayudar a poblar inicialmente una tabla de búsqueda:
En lugar de ser lo más terminante posible, prioricé la seguridad del tipo y el código claro y autodocumentado. Si no está familiarizado con los tipos de guayaba que estoy usando, puede buscar su documentation .
E incluiré el código aquí (menos las importaciones estáticas para las constantes enum en la parte inferior), aunque es realmente demasiado largo para ver cómodamente en una respuesta.
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;
}
}
}
Las tablas de búsqueda son la solución más simple y directa al problema, y también la más rápida. El truco está en gestionar el tamaño de la mesa y mantener el modo de uso lo suficientemente simple como para procesarlo rápidamente ( compensación de espacio-tiempo ). Obviamente, en teoría, podría codificar cada mano que podría sostenerse y tener un conjunto de evaluaciones, luego --poof-- una tabla de búsqueda y listo. Desafortunadamente, una mesa de este tipo sería enorme e inmanejable para la mayoría de las máquinas y, de todos modos, invariablemente te obligaría a agotar discos a medida que la memoria se intercambia.
La denominada solución dos más dos tiene una gran tabla de 10M, pero literalmente implica una búsqueda de tabla para cada carta en la mano. No es probable que encuentre un algoritmo más rápido y simple de entender.
Otras soluciones implican más tablas comprimidas con indexación más compleja, pero son fácilmente comprensibles y bastante rápidas (aunque mucho más lentas que 2 + 2). Aquí es donde ves el lenguaje sobre hashing y demás: trucos para reducir el tamaño de una tabla a tamaños más manejables.
En cualquier caso, las soluciones de búsqueda son mucho más rápidas que las soluciones histograma-sort-dance-on-your-head-compare-special-case-and-by-the-way-was-it-a-flush, casi ninguna de los cuales son dignos de una segunda mirada.
Si representas una mano como una matriz de, por ejemplo, objetos de la Card , tendré métodos para recorrer esta matriz y determinar si tiene un tipo 2, un color, etc., y si lo hace, qué escribirlo es; por lo que podría hacer que el método 3ofaKind() devuelva 5 si una mano tiene tres 5s. Luego establecería una jerarquía de posibilidades (por ejemplo, 3 de un tipo es superior a 2 de un tipo) y trabajaría desde allí. Los métodos mismos deberían ser bastante sencillos de escribir.
Si solo quieres entender cómo funciona aquí, es un algoritmo simple:
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)
}
Es de "ALGORITMOS Y EVALUACIÓN EN COMPUTER POKER" por Darse Billings.