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