Created article on poker

9 files changed, 221 insertions, 0 deletions

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:

diff --git a/content/images/poker/ac.jpeg b/content/images/poker/ac.jpeg
new file mode 100644
index 0000000..0b26895
--- /dev/null
+++ b/content/images/poker/ac.jpeg
diff --git a/content/images/poker/ad.jpeg b/content/images/poker/ad.jpeg
new file mode 100644
index 0000000..62efda2
--- /dev/null
+++ b/content/images/poker/ad.jpeg
diff --git a/content/images/poker/ah.jpeg b/content/images/poker/ah.jpeg
new file mode 100644
index 0000000..d158981
--- /dev/null
+++ b/content/images/poker/ah.jpeg
diff --git a/content/images/poker/as.jpeg b/content/images/poker/as.jpeg
new file mode 100644
index 0000000..9a6765e
--- /dev/null
+++ b/content/images/poker/as.jpeg
diff --git a/content/images/poker/kc.jpeg b/content/images/poker/kc.jpeg
new file mode 100644
index 0000000..6cc19a3
--- /dev/null
+++ b/content/images/poker/kc.jpeg
diff --git a/content/images/poker/kd.jpeg b/content/images/poker/kd.jpeg
new file mode 100644
index 0000000..b86fc41
--- /dev/null
+++ b/content/images/poker/kd.jpeg
diff --git a/content/images/poker/kh.jpeg b/content/images/poker/kh.jpeg
new file mode 100644
index 0000000..58b95a4
--- /dev/null
+++ b/content/images/poker/kh.jpeg
diff --git a/content/images/poker/ks.jpeg b/content/images/poker/ks.jpeg
new file mode 100644
index 0000000..ca6e804
--- /dev/null
+++ b/content/images/poker/ks.jpeg