New article on rst & Latex. Changed theme

1 files changed, 0 insertions, 221 deletions

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: