1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
|
.. -*- 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:
|
