.. -*- rst -*- .. -*- coding: utf-8 -*- Évaluation des mains au poker ############################# :date: 2013-04-19 :tags: 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. .. _pokersource: http://svn.gna.org/svn/pokersource/ .. _critiques: http://www.codingthewheel.com/archives/a-pokersource-poker-eval-primer 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 |Ah|\ |As| contre |Ks|\ |Kc| est équivalent a |Ac|\ |Ad| contre |Kd|\ |Kh| 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 : |Ah|\ |As| contre |Ks|\ |Kc| |Ah|\ |As| contre |Ks|\ |Kh| |Ah|\ |As| contre |Ks|\ |Kd| |Ah|\ |As| contre |Kc|\ |Kh| |Ah|\ |As| contre |Kc|\ |Kd| |Ah|\ |As| contre |Kh|\ |Kd| va pouvoir être simplifié en 1 * |Ah|\ |As| contre |Ks|\ |Kh| (les deux mains partagent les couleurs) 4 * |Ah|\ |As| contre |Ks|\ |Kc| (les deux mains partagent une couleur) 1 * |Ah|\ |As| contre |Kc|\ |Kd| (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 |Ah|\ |As| et |Ac|\ |Ad|\ ) 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. .. code-block:: ocaml 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 .. _ensemble: https://fr.wikipedia.org/wiki/Ensemble .. _`opérations de base`: https://fr.wikipedia.org/wiki/Alg%C3%A8bre_des_parties_d%27un_ensemble É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. .. _algorithmes: http://jean-paul.davalan.pagesperso-orange.fr/mots/comb/comb/combalgo.html .. _combinaisons avec répétitions: http://fr.wikipedia.org/wiki/Combinaison_avec_r%C3%A9p%C3%A9tition 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 ! .. _git: http://git.chimrod.com/?p=poker-evaluation.git;a=summary .. |As| image:: {filename}../images/poker/as.jpeg :width: 30 .. |Ad| image:: {filename}../images/poker/ad.jpeg :width: 30 .. |Ac| image:: {filename}../images/poker/ac.jpeg :width: 30 .. |Ah| image:: {filename}../images/poker/ah.jpeg :width: 30 .. |Ks| image:: {filename}../images/poker/ks.jpeg :width: 30 .. |Kc| image:: {filename}../images/poker/kc.jpeg :width: 30 .. |Kd| image:: {filename}../images/poker/kd.jpeg :width: 30 .. |Kh| image:: {filename}../images/poker/kh.jpeg :width: 30 .. |nbsp| unicode:: 0xA0 :trim: