Évaluation des mains au poker

Publié le dans « Perso ». Mots-clefs : ocaml, Programmation, Jeux

J’ai entrepris il y a quelques temps de mettre en place un moteur d’évaluation des mains de poker. Je n’ai pas trouvé beaucoup de codes ou librairies permettant ça, à l’exception de pokersource qui est assez utilée dans des projets libres.

Cette librairie permet d’évaluer le pourcentage de chance pour chaque joueur de gagner le pot, en fonction du type de jeu, du board, ou des cartes brulées. Elle est fiable et assez rapide si l’on en croit les critiques.

Par contre, dès qu’il s’agit d’évaluer des groupes de mains, aucune optimisation n’est réalisée, et c’est à la charge du développeur de s’en occuper. J’ai donc commencé une petite librairie en Ocaml qui se charge de faire les calculs, en réalisant les optimisations nécessaires pour accélerer le calcul.

Je ne vais pas présenter ici le code, mais plutôt comment sont réalisées les différentes optimisations mises en places par la librairie.

Couleurs de libertés

Présentation

Il s’agit de la première optimisation et s’inspire des degrés de libertés l’on peut retrouver dans les équations. On part du principe que évaluer les probabilité entre AhAs contre KsKc est équivalent a AcAd contre KdKh c’est à dire que les couleurs peuvent être substituées les unes aux autres sans changer les probabilités.

Tant qu’une couleur n’a pas été «posée», elle peut être substituée par n’importe quelle autre. Cela simplifier les calculs répétitifs, par exemple:

AhAs contre KsKc

AhAs contre KsKh

AhAs contre KsKd

AhAs contre KcKh

AhAs contre KcKd

AhAs contre KhKd

va pouvoir être simplifié en

1 * AhAs contre KsKh (les deux mains partagent les couleurs)

4 * AhAs contre KsKc (les deux mains partagent une couleur)

1 * AhAs contre KcKd (les deux mains ne partagent pas de couleur)

Selon le nombre de joueurs disutant la confrontation, le nombre de calculs à faire peut déjà être diminué par 2 ou plus: il est possible d’appliquer récursivement cette opération pour chacun des joueurs, en fonction des couleurs qui ont été utilisées précédemment.

Implémentation

Il «suffit» de tenir une table de correspondance entre les couleurs réelles, et les couleurs utilisées dans le calcul. Puis, de regrouper les mains du joueur:

  1. Au début, la table est vide: aucune couleur n’est fixée, donc deux mains ayant des valeurs identiques (par exemple AhAs et AcAd) vont se retrouver regroupée sous la même main, qui sera comptabilisée deux fois.
  2. Ensuite, pour chaque main ainsi générée, on va regrouper les mains du joueur suivant. Sauf que cette fois-ci la table de correspondance n’est plus vide: elle a déjà été rempli lors de la phase 1; certaines mains ne pourront donc pas être regroupées entre elles.
  3. On répète la phase 2 pour chaque joueur, à chaque fois le nombre de couleurs libre est réduit. Quand on arrive au dernier joueur, on lance le calcul, auquel on applique le facteur de multiplication, calculé en fonction du nombre de mains qui ont étés regroupées pour l’ensemble des joueurs.

Calcul combinatoires

Cette première opération permet déjà de réduire les calculs, mais ça n’est pas suffisant. Quand on essaie de calculer les probabilité, il arrive souvent que les adversaires aient des mains en communs, parmi leur possibité de jeu.

Imaginons les possibité suivantes:

  • joueur 1: {AA, KK, AK}
  • joueur 2: {AA, KK}
  • joueur 3: {KK, AK}

évaluer les probabilité de chaque joueur va conduire a des répétitions lors évaluations:

  • (AA, KK, AK) et (AA, AK, KK)
  • (AK, AA, KK) et (KK, AA, AK)

Quand on a calculé le premier arrangement, on peut déduire les résulats du second sans faire les calculs, il suffit d’éffectuer une permutation pour obtenir, mutatis mutandis, le résulat attendu.

Partitions

La première étape est de réaliser une partition des mains possibles du joueur. Pour chaque joueur, il faut commencer par créer des groupes de mains tel que:

  • chaque groupe pris pair à pair ne contient aucune carte en commun
  • il est possible de reconstituer l’ensemble des mains des joueurs par une combinaison de ces groupes.

On va se servir des opérations de base pour découper un ensemble pair à pair, en prenant à chaque fois l’élément unique que l’on applique ensuite à l’ensemble suivant.

let explode =

  let rec partition clean current = function
    | [] -> current, clean
    | hd::tl ->
        if S.disjoint current hd || S.equal current hd then
          partition (hd::clean) current tl
        else
          let s1::s2 = split current hd
          in List.unique ~eq:S.equal (partition s2 s1 ((tl @ clean)))

  and process_list checked = function
    | []       -> checked
    | hd :: tl -> (
        match partition [] hd tl with
        | cleaned, []  -> cleaned::checked
        | cleaned, tl' -> process_list (cleaned::checked) tl'
      )

  in process_list []
  %> List.unique ~eq:S.equal

Énumérer

Ensuite, nous allons énumérer l’ensemble des combinaisons possible de ces groupes. Il existe quelques algorithmes permettant de générer la liste des combinaisons données pour un rang donné.

Toutefois, nous travaillons ici sur des combinaisons avec répétitions (une même partition peut êre présente plusieurs fois), ce qui change le nombre de combinaisons disponibles.

Pour chacune de ces combinaison, il faut maintenant tester toutes les permutations possibles, et, pour chacune d’elle, vérifier si cette permutation peut être présente ou non dans la confrontation. Si l’une d’entre elle est possible, alors on peut lancer le calcul, et garder le résultat au cas où une autre permutation de la même combinaison pourrait correspondre.

Assembler

Pour terminer, il faut pouvoir assembler les résulats. Il suffit de garder le nombre de mains évaluées, et le nombre de mains gagnées pour chaque joueur, cela peut se faire au fil de l’eau, en additionnant chaque nouveau résulat au résultat final. La probabilité de gagner se fait en calculant le rapport.

Le code

Il est disponible sur mon dépôt git. Je ne vois pas d’autres optimisations possibles pour l’instant (sauf à partir sur de la parallélisation de code, ce qui est faisable, mais l’on n’est plus dans l’algorithme), mais suit preneur de toute nouvelle idée!

À lire aussi :

Commentaires :

Aucun commentaire pour l'instant.