From 9b77ec15e5beeff3f57f845be883416d2a68b84d Mon Sep 17 00:00:00 2001 From: Sébastien Dailly Date: Mon, 30 Nov 2020 22:56:26 +0100 Subject: New article on rst & Latex. Changed theme --- content/Perso/poker.rst | 221 ------------------------------------------------ 1 file changed, 221 deletions(-) delete mode 100644 content/Perso/poker.rst (limited to 'content/Perso') diff --git a/content/Perso/poker.rst b/content/Perso/poker.rst deleted file mode 100644 index 44a011b..0000000 --- a/content/Perso/poker.rst +++ /dev/null @@ -1,221 +0,0 @@ -.. -*- 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: -- cgit v1.2.3