Poker en Python

Dénombrer

On demande souvent au lycée de faire des simulations et de tenter de bidouiller quelque chose avec deux ou trois résultats de statistique inférentielle admis ou « démontrés » par observation...

Nous allons plutôt rester dans un domaine mathématique non magique et ne plus faire un sondage sur des résutats partiels mais dénombrer tous les résultats.

Cela nous permettra de rester dans un domaine « démontrable » et non plus seulement « observable », mais aussi de faire quelques calculs et d'un point de vue programmation, d'être un peu confronté à des problèmes d'efficacité.

Nous allons pourtant utiliser un langage peu réputé pour sa vitesse, Python, mais largement utilisé et facile d'accès.

Nous verrons dans un deuxième temps une approche plus constructive en utilisant cette fois le langage Haskell.

Les itérateurs et l'évaluation paresseuse

Pour celles et ceux impliqués dans les options informatiques ISN en S ou SIN en STI2D, il peut être intéressant de faire découvrir un concept difficile mais largement utilisé dans les langages modernes, celui d'évaluation paresseuse. C'est une idée importante qui fait la force d'un langage comme Haskell et que Python a repris sous la forme des itérateurs. Leur rôle est même devenu prépondérant en Python 3.

Nous n'entrerons pas dans les détails, mais ce qui nous intéresse ici c'est, entre autre, qu'un itérateur pythonesque est évalué paresseusement, c'est-à-dire qu'on peut le créer sans forcément l'évaluer en entier ni tout de suite : c'est une sorte d'objet potentiellement évaluable. On peut prévoir des opérations sans les faire tout de suite mais on peut l'utiliser comme si ces opérations étaient faites : c'est en cela que l'évaluation est paresseuse. Cela permet d'avoir une meilleure gestion de la mémoire mais cela est un problème purement informatique. Revenons à notre mathématique...

Le Poker : un tour d'horizon de la mathématique discrète

Nous allons essayer de comptabiliser les différentes combinaisons du jeu de poker pour calculer la probabilité de les obtenir dans des conditions non truquées de jeu.

On traitera le cas d'un jeu de 32 cartes et celui d'un jeu de 52 cartes. Voici un petit rappel des différentes mains:

PokerHandRankings

On rentre d'abord la liste des symboles et la liste des valeurs:

Python
# Liste des symboles des cartes
symboles = ['Trefle','Carreau','Coeur','Pique']
 
# Liste des valeurs dans un jeu de 32 cartes
vals_32 = ['Sept','Huit','Neuf','Dix','Valet','Dame','Roi','As']
 
# Ensemble des valeurs dans un jeu de 52 cartes
vals_52 = ['Deux','Trois','Quatre','Cinq','Six'] + vals_32

Il s'agit ensuite de créer l'ensemble de toutes les mains possibles de cinq cartes.
Il faut d'abord se demander comment on va modéliser une carte : choisissons par exemple de le faire sous forme d'un couple . Nous voulons donc créer le produit cartésien Valeurs $\times$ Symboles.

Une première idée serait d'utiliser les listes par compréhension que l'on retrouve dans les langages de programmation modernes : Python, Haskell, Scala...mais aussi CarMetal.

Python
[(valeur,couleur) for valeur in vals_32 for couleur in symboles]

Nous allons plutôt utiliser des outils présents dans la bibliothèque itertools qui, comme son nom l'indique, fournit des outils pour utiliser les itérateurs.
Il existe en particulier une fonction product(iter1,iter2) qui renvoie justement le produit de deux itérateurs. On en profite pour créer une fonction qui fabrique notre jeu de carte en mettant les hauteurs disponibles en argument:

Python
from itertools import product
 
def jeu(vals):
    """Ensemble des cartes selon les valeurs choisies (2 -> As ou 7 -> As) """
    return product(vals,symboles)

On peut alors comparer les temps si l'on travaille avec ipython:

Python
In [2]: %timeit [(valeur,couleur) for valeur in vals_32 for couleur in symboles]
100000 loops, best of 3: 2.52 us per loop
 
In [3]: %timeit jeu(vals_32)
1000000 loops, best of 3: 352 ns per loop

352 nanosecondes au lieu de 2,52 millisecondes: on va dix fois plus vite même si c'est théoriquement équivalent d'après la documentation:

Text
itertools.product(*iterables, repeat=1)
 
Cartesian product of input iterables.
 
Equivalent to nested for-loops in a generator expression. 
For example, product(A, B) returns the same as ((x,y) for x in A for y in B).
 
The nested loops cycle like an odometer with the rightmost element advancing 
on every iteration. 
This pattern creates a lexicographic ordering so that if the input’s iterables 
are sorted, the product tuples are emitted in sorted order.
 
To compute the product of an iterable with itself, specify the number of 
repetitions with the optional repeat keyword argument. 
For example, product(A, repeat=4) means the same as product(A, A, A, A).
 
This function is equivalent to the following code, except that the actual 
implementation does not build up intermediate results in memory:
 
    def product(*args, repeat=1):
        # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
        # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
        pools = [tuple(pool) for pool in args] * repeat
        result = [[]]
        for pool in pools:
            result = [x+[y] for x in result for y in pool]
        for prod in result:
            yield tuple(prod)

La dernière remarque nous indique que la gestion de la mémoire est meilleure avec product.

En fait, sur Python, nous allons voir que la gestion de la mémoire (qui ne devrait pas parasiter nos idées mathématiques) produit d'étranges différences de performances aux yeux d'un(e) mathématicien(ne).

Il est normalement plus clair de travailler en créant des fonctions intermédiaires mais cela semble ralentir Python.

Cela va être marquant au moment de créer l'ensemble des mains de 5 cartes. On va utiliser la fonction combinations de itertools :

Text
itertools.combinations(iterable, r)
 
Return r length subsequences of elements from the input iterable.
 
Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, 
the combination tuples will be produced in sorted order.
 
Elements are treated as unique based on their position, not on their value. 
So if the input elements are unique, there will be no repeat values in each combination.
 
The number of items returned is n! / r! / (n-r)! when 0 <= r <= n or zero when r > n.

C'est bien ce qu'il nous faut : le nombre de mains de 5 cartes dans un jeu de $n$ cartes est en effet $n \choose 5$. On peut alors proposer:

Python
def mains(vals):
    """Ensemble des sous-ensembles de jeu de cardinal 5 :
    c'est donc l'ensemble des mains de 5 cartes"""
    return combinations(jeu(vals), 5)

ou

Python
def mains(vals):
    return combinations(product(vals,symboles), 5)

ou

Python
mains_32 = combinations(product(vals_32,symboles), 5) 

Lançons la course:

Python
In [14]: %timeit mains(vals_32)
100000 loops, best of 3: 2.29 us per loop
 
In [15]: %timeit combinations(product(vals_32,symboles),5)
100000 loops, best of 3: 2.06 us per loop
 
In [16]: %timeit mains_32
10000000 loops, best of 3: 25.7 ns per loop

La dernière solution est 100 fois plus rapide. Le problème, c'est que mains_32 est à usage unique : une fois que l'itérateur a été utilisé, il a en même temps été vidé...ah...Python.

Mais bon, il faut rester simple et proche du problème mathématique donc nous utiliserons les fonctions "mains" sans rentrer dans les détails.

Dénombrer les mains

Il ne reste plus qu'à faire des tests sur nos ensembles de mains et compter les mains qui les passent.

Nous aurons besoin de dresser la liste des hauteurs d'une main et celle des couleurs d'une main.

Nous allons utiliser la très importante fonction map qui applique une fonction à tous les éléments d'un itérateur.

Par exemple, si je "map" la liste [1,2,3] par la fonction carrée, j'aurai [1,4,9].

Ici :

Python
def hauteurs(main):
    """Liste des hauteurs d'une main"""
    return map(hauteur,main)
 
def couleurs(main):
    """Ensemble des couleurs d'une main"""
    return map(couleur,main)

Ensuite, il me faut compter les sorties identiques. Il existe un outil Python tout fait pour ça : la fonction Counter de la bibliothèque collections. Par exemple:

Python
In [62]: from collections import Counter
 
In [63]: Counter("maman papa")
Out[63]: Counter({'a': 4, 'p': 2, 'm': 2, ' ': 1, 'n': 1})

On reçoit donc un dictionnaire des éléments de l'itérateur classés selon leurs fréquences.
Ici, les clés du dictionnaire sont les lettres et les valeurs associées sont les fréquences.

On utilisera aussi le test in qui répond vrai si l'élément testé est dans l'itérateur:

Python
In [65]: 'a' in "maman"
Out[65]: True
 
In [66]: 'z' in "maman"
Out[66]: False

Un carré au poker contient donc un 4 dans son ensemble de valeurs (obtenu avec la méthode values en Python).

Python
def est_carre(main):
    """Teste si une main contient quatre cartes de même hauteur"""
    return 4 in Counter(hauteurs(main)).values()

Le résultat est un booléen : True ou False.

Python
In [69]: m = (('Sept', 'Trefle'),
 ('Sept', 'Carreau'),
 ('Sept', 'Coeur'),
 ('Sept', 'Pique'),
 ('Huit', 'Trefle'))
 
In [70]: est_carre(m)
Out[70]: True

Ensuite, nous voudrions compter le nombre de carrés dans un jeu. Une fonction bien surchargée à la mode Python va être ici bien pratique : c'est la fonction sum.

Elle fait ce qu'on attend d'elle:

Python
In [71]: sum([1,2,3])
Out[71]: 6

et même plus, pour ce qui est des booléen:

Python
In [72]: sum([True,True,True,False,True])
Out[72]: 4

Elle nous permet donc de compter les mains qui ont passé le test:

Python
def compte_mains(test,vals):
    """Compte combien de fois le prédicat est vrai dans l'itérable"""
    return sum(map(test, mains(vals)))

Cela nous permet de compter les carrés d'un jeu de 32 ou 52 cartes (mais pour 52, c'est un peu long...):

Python
In [75]: compte_mains(est_carre,vals_32)
Out[75]: 224
 
In [76]: %timeit compte_mains(est_carre,vals_32)
1 loops, best of 3: 1.7 s per loop
 
In [77]: compte_mains(est_carre,vals_52)
Out[77]: 624
 
In [78]: %timeit compte_mains(est_carre,vals_52)
1 loops, best of 3: 22.1 s per loop

On aurait pu procéder autrement. Par exemple, en s'occupant de l'ensemble des hauteurs qui sera donc constitué de 1 et 4:

Python
def est_carre(main):
    return {1,4} == set(Counter(hauteurs(main)).values())

Ou encore, en ordonnant la liste des hauteurs (avec la fonction sorted qui trie une liste en Python) qui doit donc être [1,4]:

Python
def est_carre(main):
    return [1,4] == sorted(list(Counter(hauteurs(main)).values()))

On trouve dans tous les cas 224 qui est ${8 \choose 1} \times {4 \choose 4} \times {{32-4} \choose 1}$: une hauteur parmi 8, quatre cartes dans cette hauteur et 1 carte parmi les 28 qui restent.

Pour la plupart des autres mains, on agit de manière similaire:

Python
def est_full(main):
    """Teste si une main contient trois cartes de même hauteur
    et deux d'une autre"""
    return {2,3} == set(Counter(hauteurs(main)).values())
 
def est_double_paire(main):
    """Teste si une main contient 2 cartes de même hauteur
    et deux d'une autre"""
    return [1,2,2] == sorted(list(Counter(hauteurs(main)).values()))
 
def est_brelan(main):
    """Teste si une main contient 3 cartes de même hauteur"""
    return [1,1,3] == sorted(list(Counter(hauteurs(main)).values()))
 
def est_paire(main):
    """Teste si une main contient 2 cartes de même hauteur"""
    return [1,1,1,2] == sorted(list(Counter(hauteurs(main)).values()))

On obtient:

Python
In [79]: compte_mains(est_full,vals_32)
Out[79]: 1344
 
In [80]: compte_mains(est_brelan,vals_32)
Out[80]: 10752
 
In [81]: compte_mains(est_double_paire,vals_32)
Out[81]: 24192
 
In [82]: compte_mains(est_paire,vals_32)
Out[82]: 107520

Il ne reste plus qu'à s'occuper des couleurs et des quintes, en faisant attention aux quintes flush : une couleur ne doit pas être une quinte en même temps et vice-versa.

Pour trouver les quintes, on peut utiliser islice qui, comme son nom l'indique, coupe un itérateur en tranches:

Text
 itertools.islice(iterable, start, stop[, step])
 
 Make an iterator that returns selected elements from the iterable. 
 If start is non-zero, then elements from the iterable are skipped until 
 start is reached. 
 Afterward, elements are returned consecutively unless step is set higher 
 than one which results in items being skipped. If stop is None, then 
 iteration continues until the iterator is exhausted, if at all; otherwise, 
 it stops at the specified position. Unlike regular slicing, islice() does 
 not support negative values for start, stop, or step. Can be used to extract 
 related fields from data where the internal structure has been flattened 
 (for example, a multi-line report may list a name field on every third line). 
 
 Equivalent to:
 
    def islice(iterable, *args):
        # islice('ABCDEFG', 2) --> A B
        # islice('ABCDEFG', 2, 4) --> C D
        # islice('ABCDEFG', 2, None) --> C D E F G
        # islice('ABCDEFG', 0, None, 2) --> A C E G
        s = slice(*args)
        it = iter(range(s.start or 0, s.stop or sys.maxsize, s.step or 1))
        nexti = next(it)
        for i, element in enumerate(iterable):
            if i == nexti:
                yield element
                nexti = next(it)
 
    If start is None, then iteration starts at zero. 
    If step is None, then the step defaults to one.

Ce qui donne:

Python
def meme_couleur(main):
    """Teste si une main contient cinq cartes de même couleur"""
    return len(Counter(couleurs(main)).keys()) == 1
 
def suites(vals):
    """Ensemble d'ensembles de hauteurs de mains contenant une quinte"""
    return [set(islice(vals,k,k+5,1)) for k in range(len(vals) - 4)]
 
def est_quinte_32(main):
    """Teste si une main de 32 cartes contient une quinte avec des couleurs différentes"""
    return (set(hauteurs(main)) in suites(vals_32)) and not meme_couleur(main)
 
def est_quinte_52(main):
    """Teste si une main de 52 cartes contient une quinte avec des couleurs différentes"""
    return (set(hauteurs(main)) in suites(vals_52)) and not meme_couleur(main)
 
def est_couleur_32(main):
    """Teste si une main de 32 cartes contient une couleur qui n'est pas une quinte"""
    return not (set(hauteurs(main)) in suites(vals_32)) and meme_couleur(main)
 
def est_couleur_52(main):
    """Teste si une main de 52 cartes contient une couleur qui n'est pas une quinte"""
    return not (set(hauteurs(main)) in suites(vals_52)) and meme_couleur(main)
 
def est_flush_32(main):
    """Teste si une main de 32 cartes contient une couleur qui est une quinte"""
    return (set(hauteurs(main)) in suites(vals_32)) and meme_couleur(main)
 
def est_flush_52(main):
    """Teste si une main de 52 cartes contient une couleur qui est une quinte"""
    return (set(hauteurs(main)) in suites(vals_52)) and meme_couleur(main)

On obtient:

Python
In [84]: compte_mains(est_quinte_32,vals_32)
Out[84]: 4080
 
In [85]: compte_mains(est_couleur_32,vals_32)
Out[85]: 208
 
In [86]: compte_mains(est_flush_32,vals_32)
Out[86]: 16

Il ne reste plus qu'à le vérifier en travaillant sur les coefficients binomiaux.

le code complet

Python
from collections import Counter
from itertools import product,combinations, islice
 
# Liste des symboles des cartes
symboles = ['Trefle','Carreau','Coeur','Pique']
 
# Liste des valeurs dans un jeu de 32 cartes
vals_32 = ['Sept','Huit','Neuf','Dix','Valet','Dame','Roi','As']
 
# Ensemble des valeurs dans un jeu de 52 cartes
vals_52 = ['Deux','Trois','Quatre','Cinq','Six'] + vals_32
 
def jeu(vals):
    """Ensemble des cartes selon les valeurs choisies 2 -> As ou 7 -> As"""
    return product(vals,symboles)
 
def hauteur(carte):
    """Hauteur d'une carte. Une carte est un couple (valeur,symbole)"""
    return carte[0]
 
def couleur(carte):
    """Couleur d'une carte. Une carte est un couple (valeur,symbole)"""
    return carte[1]
 
def mains(vals):
    """Ensemble des sous-ensembles de jeu de cardinal 5 : c'est donc l'ensemble des mains de 5 cartes"""
    return combinations(jeu(vals), 5) 
 
 
def hauteurs(main):
    """Liste des hauteurs d'une main"""
    return map(hauteur,main)
 
def couleurs(main):
    """Ensemble des couleurs d'une main"""
    return map(couleur,main)
 
 
def est_carre(main):
    """Teste si une main contient quatre cartes de même hauteur"""
    return 4 in Counter(hauteurs(main)).values()
 
def est_full(main):
    """Teste si une main contient trois cartes de même hauteur et deux d'une autre"""
    return {2,3} == set(Counter(hauteurs(main)).values())
 
def est_double_paire(main):
    """Teste si une main contient 2 cartes de même hauteur et deux d'une autre"""
    return [1,2,2] == sorted(list(Counter(hauteurs(main)).values()))
 
def est_brelan(main):
    """Teste si une main contient 3 cartes de même hauteur"""
    return [1,1,3] == sorted(list(Counter(hauteurs(main)).values()))
 
def est_paire(main):
    """Teste si une main contient 2 cartes de même hauteur"""
    return [1,1,1,2] == sorted(list(Counter(hauteurs(main)).values()))
 
def meme_couleur(main):
    """Teste si une main contient cinq cartes de même couleur"""
    return len(Counter(couleurs(main)).keys()) == 1
 
def suites(vals):
    """Ensemble d'ensembles de hauteurs de mains contenant une quinte"""
    return [set(islice(vals,k,k+5,1)) for k in range(len(vals) - 4)]
 
def est_quinte_32(main):
    """Teste si une main de 32 cartes contient une quinte avec des couleurs différentes"""
    return (set(hauteurs(main)) in suites(vals_32)) and not meme_couleur(main)
 
def est_quinte_52(main):
    """Teste si une main de 52 cartes contient une quinte avec des couleurs différentes"""
    return (set(hauteurs(main)) in suites(vals_52)) and not meme_couleur(main)
 
def est_couleur_32(main):
    """Teste si une main de 32 cartes contient une couleur qui n'est pas une quinte"""
    return not (set(hauteurs(main)) in suites(vals_32)) and meme_couleur(main)
 
def est_couleur_52(main):
    """Teste si une main de 52 cartes contient une couleur qui n'est pas une quinte"""
    return not (set(hauteurs(main)) in suites(vals_52)) and meme_couleur(main)
 
def est_flush_32(main):
    """Teste si une main de 32 cartes contient une couleur qui est une quinte"""
    return (set(hauteurs(main)) in suites(vals_32)) and meme_couleur(main)
 
def est_flush_52(main):
    """Teste si une main de 52 cartes contient une couleur qui est une quinte"""
    return (set(hauteurs(main)) in suites(vals_52)) and meme_couleur(main)
 
 
def compte_mains(test,vals):
    """Compte combien de fois le prédicat est vrai dans l'itérable"""
    return sum(map(test, mains(vals)))

courtesy of webmatter.de