Poker: analizador de manos IV

El analizador de manos parece que funciona bien. Con los archivos auxiliares (las tablas), que tienen que estar en la misma carpeta que el .jar (o en la carpeta del proyecto si se utiliza un IDE), es capaz de calcular manos a una velocidad bastante alta.

Con un procesador de 2.4GHz Intel Core 2 Duo, he ejecutado el código de ejemplo, que recorre todas las posibles manos de la baraja y calcula cuántas hay de cada tipo. La salida del programa ha sido:

Resultados:
Esc Color: 41584
Poker: 224848
Full: 3473184
Color: 4047644
Escalera: 6180020
Trio: 6461620
Dobles parejas: 31433400
Pareja: 58627800
Carta alta: 23294460

Totales: 133784560

Comprobando con la wikipedia la cantidad de manos distintas que hay según el tipo de mano, he llegado a la conclusión de que el funcionamiento parece correcto, ya que coincide en todos los casos.

La ejecución del programa ha tardado 31 segundos, lo cual son 4.300.000 manos/segundo aproximadamente… no está nada mal. Además, en esos 31 segundos el programa inicializa variables y instancias de clases, maneja la baraja, guarda los valores, etc. Ejecutando las mismas sentencias, pero esta vez sin evaluar las manos he comprobado que el tiempo que se tarda en realizar todo este trabajo «extra» es de entre 2 y 3 segundos.

Para finalizar, me gustaría comentar que si bien son unos buenos resultados, no son los mejores. El mismo programa implementado en C++ estaría más optimizado. Además, se han conseguido evaluadores sensiblemente más rápidos.

No obstante, creo que los puntos fuertes de este analizador es que está escrito en Java, y considero que es muy fácil extender este programa o crear nuevas funcionalidades. Además, 4.300.000 manos/segundo es un valor bastante alto, y rara vez necesitaremos una velocidad de cálculo mayor. Lo repito: no creo que sea el mejor, ni tampoco está basado en una idea original, pero es cómodo y se puede manejar fácilmente.

Si necesitas ayuda para hacerlo funcionar, te ha sido de utilidad, lo has modificado o lo has utilizado para cualquier cosa, estaría encantado de que me lo comentaras vía e-mail!

Editado. Puedes descargar los archivos haciendo click aqui:

Analizador de manos de póker (Java)
466.0 KiB
844 Downloads
Details

Poker: analizador de manos III

Una vez que ya está claro cómo va a ser exactamente el analizador, nos podemos poner manos a la obra. A mi personalmente me gusta programar en Java, porque creo que es fácil crear grandes proyectos poco a poco, ya que la estructura de programación ayuda (clases, herencia, etc.). También utilizo NetBeans.

El algoritmo completo podría resumirse así:

  1. La entrada son 7 cartas, cada una con un número y color determinado.
  2. Cada número tiene asignado un valor, y cada color tiene asignado otro valor (según las tablas de las entradas precedentes).
  3. Sumamos los valores de todos los números, y buscamos en la primera tabla el valor de la mano asociado (entre 1 y 7462).
  4. Sumamos los valores de todos los colores, y buscamos en la segunda tabla si hay o no color.
  5. Si no hay color, devolvemos el valor de la mano encontrado en el paso 3.
  6. Si hay color, sumamos todos los valores de las cartas con el palo determinado.
  7. Buscamos en la tercera tabla el valor de la mano teniendo en cuenta el color.
  8. Devolvemos el menos de los dos valores, el del paso 3 y el del paso 7 (ya que la mejor mano es la 1, y la peor la 7462).

Notemos que el hecho de tener en cuenta el color nos ha complicado bastante el algoritmo, pero dado que este es un caso poco habitual (aproximadamente un 0.19% de las manos) no influirá excesivamente en el rendimiento global.

La construcción de las tablas es mecánica y sin demasiado interés. En principio, no postearé el código utilizado ni haré más comentarios al respecto.

Lo único que falta es pasar el algoritmo a código y comprobar su correcto funcionamiento. Para ello, he creado unas cuantas clases en Java que implementen el algoritmo y que sean fácilmente interpretables. En Descargas podéis encontrar los archivos .java, las tablas utilizadas y un léeme para saber cómo utilizarlo. Si queréis utilizarlo para fines personales y/o modificarlo sóis libres de hacerlo, siempre que se respete la licencia GPL. En cualquier caso, si te ha resultado útil o lo has modificado de alguna manera te agradecería que me escribieras porque probablemente me intereserá!

Editado. También te puedes descargar los archivos directamente desde aqui:

Analizador de manos de póker (Java)
466.0 KiB
844 Downloads
Details

Poker: analizador de manos II

Una vez que ya está planteado el camino a seguir, hace falta concretar un poco más. El siguiente paso es especificar el algoritmo que seguirá el programa. Básicamente, la entrada al programa son un conjunto de 7 cartas (cada carta tiene un número del 1 al 13 y un color de entre 4 posibles), y la salida debe ser el número de mano asociado a la carta según la tabla de las relaciones de equivalencia.

El algoritmo está planteado de la siguiente manera:

  1. A cada carta, le asociamos el valor asociado a su número según la tabla del post anterior.
  2. Sumamos todos los valores, y obtenemos una expresión única para cada combinación de cartas.
  3. Vamos a una tabla en la que esté cada expresión asociada a su valor, y lo leemos.

En principio, parece simple. Sin embargo, no lo es tanto, ya que existen dos inconvenientes:

  • Habrá que crear la tabla, y eso llevará tiempo. Notemos que la longitud de la tabla no será excesiva porque nos aprovechamos de que la suma es conmutativa y, por tanto, no importa el orden en que introducimos las 7 cartas, ahorrándonos muchos registros (ordenar las cartas de menor a mayor antes de evaluar la mano ralentiza el algoritmo, y en nuestro caso no hace ninguna falta).
  • ¡No hemos tenido en cuenta el color! Habrá que modificar nuestro algoritmo para que detecte este caso y lo tenga en cuenta.

La solución a estos dos obstáculos es la siguiente:

  • En el primer caso, para crear la tabla necesitaríamos crear un analizador de manos «a lo bruto»: uno que primero mirara si hay escalera de color. Si no, si hay poker. Si no, si hay full, etc. Después, calcular el número que le correspondería a cada tipo de mano en función de la mano concreta (poker de as, poker de K, etc.), y que el programa lo introdujese automáticamente. Este es un trabajo muy laborioso, pero afortunadamente ya está hecho: utilizando, una vez más, el código fuente del analizador de Cactus Kev’s, disponible en su página web, podemos automatizar este trabajo.
  • El segundo es más problemático, porque es un problema estructural. La mejor solución que he encontrado es comprobar en cada caso si hay color o no, y en caso de que haya color crear otra tabla como la anterior en la que sólo se tengan que sumar los valores de las cartas del color en cuestión. Para hacer más eficiente el proceso en cuestión, he tenido que hacer un proceso muy similar al anterior: a cada color le asigno un valor, según la siguiente tabla, y al sumar los valores una tabla preprogramada me dirá si hay 5 cartas o más del mismo palo, y cual es el palo

La tabla para los colores es:

Color: Corazones Picas Espadas Tréboles
Valor asignado: 1 8 57 400

Los valores son distintos en este caso que en la tabla del post anterior, porque en este caso no ponemos el 0 (ya que así podremos utilizar la misma tabla para evaluar manos de 5, 6 ó 7 cartas), y además ahora pueden aparecer hasta 7 cartas con el mismo color, a pesar de que solo pueden aparecer 4 cartas con el mismo número.

Poker: analizador de manos I

Un analizador de manos no es ni más ni menos que un programa que es capaz de determinar cual es la mejor mano de entre varias posibles en el juego del Poker. La gracia de conseguir un buen analizador de manos (es decir, uno que analice muchas manos en un corto espacio de tiempo) es que es posible determinar las probabilidades de ganar o perder en una partida en cualquier momento, simplemente probando todas las posibilidades (o, por lo menos, muchas).

Hace un tiempo me encontré con un analizador de manos de 5 cartas: el Cactus Kev’s Poker Hand Evaluator. Ése analizador se basa en el hecho de que sólo existen 7462 «categorías» de manos diferentes, dónde dos manos de la misma categoría empatan (es decir, es lo mismo tener full de ases a la K de corazones que full de ases a la K de tréboles. Por tanto, ambas manos están en la misma «categoría»). Gracias a eso, asigna a cada mano un número y, si obtiene el número asociado a dos manos, simplemente comparándolos será capaz de decir cual es la ganadora. Los detalles están en su página web.

A cada número se le asigna un número primo (desde el DOS = 1 hasta el AS = 41). Si suponemos que no hay color, simplemente multiplicando todos los números y mirando en una tabla hecha previamente, es casi immediato obtener el valor de dicha mano. El caso de que hubiese color se trata de forma separada. Está implementado en C y es posible descargárselo desde su página web.

No obstante, se me ocurrió una posible mejora: para aplicar la misma idea a 7 cartas, habría que evitar la multiplicación, ya que el número más grande que se puede conseguir (41^4 * 37^3 = 143133271933) ocuparía 38 bits. Si consiguiésemos bajar este número a 32, podríamos utilizar tan solo un int, mejorando con ello el rendimiento.

La idea se basa en sumar en vez de multiplicar: a cada número le asignaremos igualmente un valor, de tal manera que dos manos distintas den números distintos al sumar los valores de cada una de las cartas:

Carta: As 2 3 4 5 6 7 8 9 10 J Q K
Valor asignado: 0 1 5 24 112 521 2421 11248 52256 242769 1127845 5239688 24342288

Entonces, si suponemos que no hay color, el máximo número al que llegaremos será 113088216, que lo podremos almacenar en 27 bits! No obstante, aún hay que tener en cuenta que:

  • Para el caso en el que haya color tendremos que buscar algún método alternativo.
  • Hay que fabricar las tablas para después comprobar qué número tiene asiganada nuestra mano.
  • No podremos utilizar el analizador con manos de 8 cartas o más, ya que entonces aparecerían colisiones.

En las próximas entradas buscaremos como solucionar estos y más problemas que vayan surgiendo.

Editado. puedes descargar los archivos haciendo click aqui:

Analizador de manos de póker (Java)
466.0 KiB
844 Downloads
Details