From 3bd64117093777c9708e7ba73b94ee52d0ecce98 Mon Sep 17 00:00:00 2001 From: Sébastien Dailly Date: Wed, 17 Apr 2013 13:09:21 +0200 Subject: Created article on poker --- content/Perso/poker.rst | 221 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 221 insertions(+) create mode 100644 content/Perso/poker.rst (limited to 'content/Perso') diff --git a/content/Perso/poker.rst b/content/Perso/poker.rst new file mode 100644 index 0000000..7583347 --- /dev/null +++ b/content/Perso/poker.rst @@ -0,0 +1,221 @@ +.. -*- rst -*- +.. -*- coding: utf-8 -*- + +Évaluation des mains au poker +############################# + +:date: 2013-04-17 +:tags: Programmation + +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: -- cgit v1.2.3