En una partida de cartas, la tarea de calcular el valor de una mano para saber si gana a otra se llama evaluación de manos (hand evaluation). Para un ser humano que ha aprendido las reglas de un juego de cartas cualquiera, la evaluación de manos es una tarea trivial, nada mas ver las cartas sabe que un poker es mas que una pareja, o que dos reyes caballo ganan a dos reyes sota.
Pero para un ordenador la tarea no es tan sencilla si se quiere hacer de manera eficiente y la gente se estruja el cerebro para conseguir dar con algoritmos que realicen esta tarea rápidamente y sin errores.
Yo ya me vi una vez en esta tesitura cuando hice el juego de mus multijugador de Teknoland, el mus de Commm, y la verdad es que inventé un sistema bastante bueno que con las cartas ordenadas asignaba a cada una un valor que dependía de la fase que se jugaba y lo multiplicaba por una potencia de su posición en la mano. De este modo conseguía un número entero que me permitía comparar manos de distintos jugadores, la del entero mayor era la que ganaba (salvo en la chica, claro).
Ahora me veo en la misma tesitura pero para otro juego mucho mas popular que el Mus… el Poker.
Por ser tan popular existen variopintos algoritmos de cálculo de manos en internet, pero unos me han parecido demasiado complejos y otros demasiado simples y lentos, por eso he decidido poner las neuronas a funcionar y he dado con una formula, que puede que no sea tan rápida como la de Cactus Kev, pero que si es mucho mas elegante desde el punto de vista algorítmico y además permite solucionar el problema de cálculo de manos a partir de 7 cartas, que son las que se usan en la variante Texas Hold’em (después de la cantidad de spam que he borrado con estas dos palabras nunca pensé que llegaría a usarlas en un post :)).
Voy a usar una máquina de estados (autómata finito determinista) para leer las cartas una tras otra, teniendo en cuenta el hecho de que la mano está ordenada de mayor a menor valor de carta, que estamos hablando de poker jugado con una sola baraja, sin comodines y sin quitarle las cartas bajas. Cuando acabe de leer las cartas, el valor de la mano me lo dará el estado en el que se encuentre la máquina. Es el mismo método que se usa en los reconocedores de patrones.
El diseño de este autómata de Moore contemplando todas las posibilidades se me ha antojado bastante complejo, por eso he decidido usar las reglas del poker para simplificar el problema teniendo en cuenta lo siguiente:
Si en las 7 cartas 5 son del mismo color, ya solo puedo conseguir “color” (Flush), “escalera de color” (Straight flush) o “escalera real” (Royal Flush).
Técnicamente también puedo conseguir un trio y una pareja si tengo color, pero color es siempre mejor que estas dos anteriores, por lo tanto las puedo ignorar.
Si no se cumple esta condición, entonces verifico si hay una “escalera simple”, y si tampoco, paso al autómata que me dirá si lo que hay en las cartas es una “pareja” (one pair), “doble pareja” (two pair), “trio” (Three of a kind), “ful” (full house) o “poker” (four of a kind).
Luego viene el autómata en si. Este autómata lee las cartas de una en una y las compara con la última que leyó. Tiene dos posibles entradas, que la última carta y la actual sean iguales, o que sean distintas. Dependiendo de estas entradas se va variando el estado de salida.
El diagrama de transiciones del autómata sería el siguiente.
En él se puede observar que de cada estado salen siempre 2 flechas, los dos posibles inputs. Los estados marcados como STOP hacen detenerse al autómata porque ya es imposible ningún otro estado.
La única excepción se da en el caso del “poker”, el estado 4, ya que después de haber leído 4 cartas iguales, es imposible que venga otra 5 igual (no hay 5 palos) por lo que el autómata irá a STOP irremediablemente en la siguiente lectura.
El resultado viene indicado por el estado en el que quede el autómata al terminar de leer todas las cartas o bien por el anterior al último en caso de que el último sea el STOP (normalmente antes de acabar de leer todas las cartas, con lo que nos ahorramos alguna iteración que otra).
En el diagrama se pueden observar unos estados marcados como “Fulín” y “Fulón”. Estas denominaciones las he tomado prestadas de las que mis amigos (Sireno, Cabezón, Tabique, Payaso, Gon, Joan…) daban en el juego del poker mentiroso con dados. Fulín significa que se trata de un full house en el que el trio lo forman las cartas de menor valor, mientras que el fulón es lo contrario, el trio lo forman las cartas de mayor valor. Un fulón no tiene sin embargo por qué ganar siempre a un fulín, por lo que en realidad ambos son tratados simplemente como “Full house” en el autómata (p.ej. 55533 es un fulón, y AAKKK un fulín… claramente el segundo gana). La distinción es simplemente semántica.
Para hacer mas eficiente el algoritmo de evaluación de manos, en la primera pasada solo calculo el tipo de jugada que hay en la mano, lo que denomino “major rank”. En la mayoría de los casos este dato es suficiente para determinar la mano ganadora y por tanto la resolución es muy rápida (p.ej. el major rank de AKJJ5 es “Pareja” y el de KQ7773 es “Trio”). En caso de que las manos a comparar tengan el mismo “major rank” (p.ej. dos manos con “Trio”) entonces pasaríamos a comprobar el “minor rank” (p.ej KQ7773 y QQQ52, el minor rank es 7 y Q respectivamente), para el que se necesitan mas cálculos. El minor rank depende del valor de las cartas que acompañan a aquellas que conforman el major rank.
Por último, en los casos que la mala suerte vestida de estadística nos proporcione dos manos con el mismo major rank y minor rank (p.ej. AAQQ5 y AAQQ6, el major es dobles parejas, el minor es ases y cues) tenemos que calcular un valor mas, el kicker, que servirá para deshacer el desempate. En el caso de que el kicker también sea igual, entonces las manos son iguales y hay un empate que obliga a repartir el bote a partes iguales.
Hay gente que calcula todo, el major rank, el minor y el kicker en una sola vez. Es una pérdida de tiempo ya que la mayoría de las veces no es necesario llegar tan lejos en las comparaciones para hacer una valoracion correcta de la mano ganadora.
Muy interesante el algoritmo.
Sólo un apunte: en la transición del estado 8 (trío) al estado 10 (fulón), debería haber un igual, no?
Un saludo.
Gracias roger y… tienes toda la razón del mundo, en efecto la transición del estado 8 al 10 se hace mediante un = ya que el mismo input no puede desencadenar dos acciones distintas. Ha sido un fallo, lo malo es que al ser un gráfico me da un poco de pereza editarlo 😀
En el caso del primer flujo.
Si hay color y ademas ha y escalera..al preguntar si hay “AS” la res´puesta positiva no implica Escalera Real, pues puede ser
“A 2 3 4 5” de color ..y eso no es “Real”
Me encanta cuando alguien se lee las entradas y las disecciona :). Tienes toda la razón del mundo, habrÃa que completar la comprobación verificando si a continuación del as, hay una K.
Es muy poco probable,pero tambien habria que comprobar si esta la reina o ver el numero de cartas de color que hay.Puesto que se podria dar la siguiente situacion:
AK5432
Que sea poco probable no significa que no vaya a suceder 🙂
Lo que pasa es este caso es que cuando verifico si forman escalera, solo pasaría al siguiente paso las cartas que forman la escalera, que son solo 5, A5432 , por lo que la comprobación de la K seguiría siendo válida
en el gestor de pares, cuando estamos en el estado 12 (con doble pareja) en caso de recibir una carta igual deberiamos pasar a tener un full y no un trio
He revisado varias veces el diagrama y en efecto, tienes razón. Nos encontraríamos ante un fulín. Habria que pasar al estado 9.
Gracias por apuntarlo. Al final voy a tener que corregir el gráfico.
He cambiado el diagrama de pares para corregir los errores que habéis detectado. Muchas gracias por tomaros el tiempo de revisarlo.
Hola Makinolo, enhorabuena por el site y por este post tan interesante, por lo menos para mí. Resulta que yo también estoy realizando un algoritmo propio para evaluar manos que incluyen manos de Texas, Stud Hi-Lo y Razz (Omaha vendrá después), y gogleando he llegado hasta aquí. Coincido contigo al 100% en el orden de evaluar las jugadas y en los apuntes que te han dado en post anteriores. Pero te escribo porque llevo un día dándole vueltas al tema de las escaleras pues me parece que tal como yo entiendo tu diagrama me parece (puedo estar equivocado) que no tienes en cuenta, cuando haya repetidos, el número de escaleras que puede haber en la mano. Y esto es básico porque se puede dar el caso de que tengas hasta 4 (escaleras) en una mano y sólo una sea de color.Un ejemplo, 9876654, hay dos escaleras con el 4 y dos con el 5. Lo tienes solucionado ?. Si es así te agradecería, si te es posible, que me explicaras en pseudocodigo cómo lo has hecho porque me estoy volviendo majara, aunque cueste lo que cueste ha de salir. Un saludo y gracias por anticipado.
Bueno, ya solucioné lo de los repetidos y he puesto a currar una prueba de simulador de manos que he creado y me da una velocidad media de 17.868 de manos de 7 cartas evaluadas/por minuto en un AMD Turion a 2,2 Ghz, velocidad que espero reducir después de depurar el código. Después de varios bugs que he encontrado con casos especiales que no tenía contemplados ya funciona correctamente.
Un saludo Makinolo y felices fiestas.
Hola Makinolo, felicitaciones por tu algoritmo. Lo estoy usando para programar una sala de poker texas holdem sit’n’go. Lo que no entiendo es que a la primera rama en que determinas si hay color o no, discriminas las opciones de Poker y Full que valen más que el Color, como si por tener color ya no importaran los pokers y los fulls (como muy bien dices que ocurre con los trios y las parejas). Como lo has solucionado?
Discúlpame, lo he revisado caso a caso y efectivamente es imposible tener full o poker si tenemos 5 cartas del mismo palo.
Un saludo!