Probabilités sous contrainte

[Galax]

Bonjour

Un club de bridge a besoin (pour des raisons pédagogiques), d'un générateur aléatoire de donnes.
Il s'agit donc de distribuer au hasard 52 cartes, 13 pour chaque joueur.

Jusque la rien de très sorcier, il y a je pense plusieurs façons d'y parvenir :
Je prends le 1er joueur, je tire au hasard une à une chacune de ses 13 cartes parmi les cartes restantes, et je passe au joueur suivant.
On peut aussi prendre chaque cartes dans l'ordre (de l'as de pique au 2 de trèfle), et l'attribuer au hasard à un des 4 joueurs n'ayant pas encore ses 13 cartes.

Les résultats sont satisfaisants, les probabilités respectées, si l'on regarde les distributions par exemple (nb de cartes dans chaque couleur pour un joueur), on retrouve que la distribution la plus courante : 4432 apparait bien dans 21.55% des cas comme on s'y attendait.

Le problème se complique lorsqu'on veut rajouter des contraintes, sur le nombre minimum et/ou maximum de cartes par couleur pour chaque joueur. On veut par exemple que le joueur 1 ait entre 5 et 6 piques, et exactement 4 coeurs, et le joueur 2 au moins 4 carreaux.

Ma 1ere idée était de générer une donne aléatoire, puis de vérifier si toutes les contraintes étaient respectées, et si tel n'est pas le cas d'en générer une autre jusqu'à satisfaction. Cette méthode fonctionne parfaitement, les probabilités sont respectées, mais elle a le gros inconvénient d'être assez lente, surtout lorsque les contraintes sont un peu 'extrêmes'.

Peut on procéder autrement, arriver à trouver 'd'un seul coup' les cartes du joueur 1 par exemple (avec 5-6 piques et 4 coeurs), et comment faire pour que les probabilités soient respectées ?
Ou bien peut on tirer une carte au hasard, et l'attribuer ensuite à un joueur plus qu'à un autre en prenant justement en compte les contraintes ?

Mon soucis vous l'aurez compris n'est pas de trouver une donne qui respecte toutes les contraintes, mais bien de pouvoir en générer un grand nombre qui respectera en plus les probabilités générales.

Merci de votre aide

[Ben314]

Salut,
Déjà, avant de regarder la suite,

Jusque la rien de très sorcier, il y a je pense plusieurs façons d'y parvenir :
Je prends le 1er joueur, je tire au hasard une à une chacune de ses 13 cartes parmi les cartes restantes, et je passe au joueur suivant.
On peut aussi prendre chaque cartes dans l'ordre (de l'as de pique au 2 de trèfle), et l'attribuer au hasard à un des 4 joueurs n'ayant pas encore ses 13 cartes.

Il faut faire super gaffe : il y a effectivement des tas de façons de procéder dont beaucoup d'entre elles... ne donnent pas le bon résultat.
Par exemple ta "deuxième méthode" me semble foireuse : si tu tire au pif (avec équiprobabilité) le joueur à qui tu donne chaque carte (parmi ceux qui n'en n'ont pas déjà 13), il me semble qu'il y a une trop grosse proba que les deux dernières cartes (2 de carreau et 2 de tréfle) se retrouvent dans la même main du fait que, pour ces deux dernières cartes, il risque fort de n'y avoir plus qu'un seul joueur qui n'a pas ces 13 cartes.

[Doraki]

Il faut d'abord choisir la composition en couleurs des mains des joueurs, et ensuite choisir, parmi chaque couleur, l'agencement des 13 cartes de cette couleur. Tu peux permuter les cartes d'une même couleur entre elles sans que ça influe sur les contraintes vérifiées par la donne.

La difficulté est dans le choix de la composition en couleurs.
Là tu n'as plus que 37.478.624 compositions possibles, ça doit être à peu près faisable de compter toutes celles qui vérifient les contraintes, d'en tirer une au hasard, puis de terminer en choisissant l'agencement des cartes dans chaque couleur.

[Ben314]

Je suis (évidement...) d'accord avec Doraki mais ça me parrait assez coton...
En particulier, j'ai l'impression que ce que tu aimerais, c'est un programme où, en entrée de programme, on donne pour chaque joueur et chaque couleur un intervalle correspondant au nombre de carte de cette couleur que ce joueur doit avoir (par exemple, si on donne l'intervalle [0,13], cela signifie qu'il n'y a aucune contrainte).
L'impression que j'ai, c'est que, déjà, une fois ces 4x4=16 intervalles fixés, pour savoir si une telle distribution est possible ou non, ben c'est assez coton...

Effectivement, on peut regarder les 37.478.624 configurations possibles pour voir lesquelles marchent, mais je me rend pas bien compte si c'est "raisonable" en temps de calcul :
Avec les machines actuelles, si on fait une bète boucle "pour i de 1 à 37.478.624" en assembleur, ça prend trés trés peu de temps, mais il faut rajouter le temps de décodage (valeur de i)->(configuration) puis le temps de test "configuration O.K. ?" (ça, clairement, c'est rapide) et le temps de stokage (dans une structure adaptée) de l'info "la configuration est O.K" lorsque c'est le cas.

EDIT @doraki : je trouve 21.204.684 config pour les couleurs...

[Doraki]

Il me semblait que c'était le même nombre que là http://www.maths-forum.com/showthread.php?t=109741 alors je l'ai juste recopié.

Je pense que le temps pour construire une (grande) table qui répertorie toutes les combinaisons possibles reste raisonnable (de l'ordre de la minute). Et pareil pour indexer les combinaisons satisfaisant les contraintes.
Il y a un peu plus rapide en s'y prenant bien mais ça ne me semble pas nécessaire.

[Galax]

Par exemple ta "deuxième méthode" me semble foireuse : si tu tire au pif (avec équiprobabilité) le joueur à qui tu donne chaque carte (parmi ceux qui n'en n'ont pas déjà 13), il me semble qu'il y a une trop grosse proba que les deux dernières cartes (2 de carreau et 2 de tréfle) se retrouvent dans la même main du fait que, pour ces deux dernières cartes, il risque fort de n'y avoir plus qu'un seul joueur qui n'a pas ces 13 cartes.

Je suis d'accord avec toi

L'impression que j'ai, c'est que, déjà, une fois ces 4x4=16 intervalles fixés, pour savoir si une telle distribution est possible ou non, ben c'est assez coton...

Je fais un test préalable pour vérifier que toutes les contraintes sont compatibles entre elles, genre :
Somme des mini pour une couleur (ou pour un joueur) = 13
Je pense que ça doit suffire pour assurer qu'une telle distribution est possible ?

Il faut d'abord choisir la composition en couleurs des mains des joueurs, et ensuite choisir, parmi chaque couleur, l'agencement des 13 cartes de cette couleur.

Il y a en effet 37.478.624 repartitions de couleurs possibles entre les 4 joueurs, mais elles ne sont pas equiprobables (?), donc il ne suffit pas de relever celles qui sont compatibles avec les contraintes, il faudrait avoir en plus la probabilité d'une répartition donnée me semble t il.

Ceci dit partir sur le choix de la composition des couleurs me semble une bonne idée.

Dans mon exemple, on peut synthetiser les contraintes du joueur 1 par :

[5,6] [4,4] [0,4] [0,4], soit entre 5 et 6 cartes à pique, 4 à coeur, et ce qu'on veut (pas plus de 4 car déja surement 9 cartes prises entre les P et les C) pour les trefles et carreaux.

Ce joueur a donc 9 cartes connues (en terme de couleur), et de la place pour :

1 carte à P, 0 à C, 4 à K et 4 à T, sachant que sont disponibles dans le paquet :

8 cartes à P, 9 à C, 9 à K (car le joueur 2 en veut au moins 4) et 13 à T

Peut on alors affecter les poids suivants :

1*8=8 pour les P, 0*9=0 pour les C, 4*9=36 pour les K et 4*13=52 pour les T,

et donc de dire qu'il y a 8/96=8.33% pour P, 0% pour C, 37.5% pour K et 54.16% pour T,

et donc déterminer les 4 cartes qu'il manque à ce joueur en respectant ces probas la ?

[Doraki]

Peut on alors affecter les poids suivants :
1*8=8 pour les P, 0*9=0 pour les C, 4*9=36 pour les K et 4*13=52 pour les T,
et donc de dire qu'il y a 8/96=8.33% pour P, 0% pour C, 37.5% pour K et 54.16% pour T,
et donc déterminer les 4 cartes qu'il manque à ce joueur en respectant ces probas la ?

euh ... non ?

Il y a en effet 37.478.624 repartitions de couleurs possibles entre les 4 joueurs, mais elles ne sont pas equiprobables (?)

Pourquoi elles ne le seraient pas ?
Pour chaque répartition de couleur il y a toujours (13!)^4 manières de distribuer les 13 cartes dans chaque couleur, donc (13!)^4 donnes qui y correspondent.
Si tu veux que chaque donne soit équiprobable, alors toutes les répartitions de couleurs possibles doivent aussi être équiprobables.

[Ben314]

Il me semblait que c'était le même nombre que là http://www.maths-forum.com/showthread.php?t=109741 alors je l'ai juste recopié.

Effectivement : je me suis gourré...

Je suis en train de faire un petit programme (en pascal) qui liste les "cas favorables" : visiblement, au pire, c'est dans les 60 secondes pour tout lister...

[Galax]

Pourquoi elles ne le seraient pas ?
Pour chaque répartition de couleur il y a toujours (13!)^4 manières de distribuer les 13 cartes dans chaque couleur, donc (13!)^4 donnes qui y correspondent.
Si tu veux que chaque donne soit équiprobable, alors toutes les répartitions de couleurs possibles doivent aussi être équiprobables.

J'avais dans l'idée qu'il y a (52)!/(13!)^4 donnes différentes, ce qui est sensiblement différent de (13!)^4 * 37478624 ?

[Doraki]

Ah oui tiens.
J'avais pas vu que si on mélange des cartes d'un même joueur, ça change pas la donne.

Bon donc ce n'est plus équiprobable, mais heureusement, c'est rapide de calculer le nombre de donnes correspondantes à chaque répartition de couleurs, ainsi que d'en choisir une de manière équitable.
Ca fait une deuxième étape un peu plus compliqué que ce que j'pensais, mais toujours bien plus facile que la première étape.

[Galax]

Peut on raisonner joueur apres joueur.
Pour revenir à mon exemple, le joueur 1 a forcément une main du type :
5440, 5431, 5422, 5413, 5404, 6430, 6421, 6412 ou 6403
On doit pouvoir, obtenir assez facilement les probas de ces 9 distributions, et donc lui en affecter une equitablement ?
Ensuite faire de meme pour le joueur 2, sachant que le joueur 1 a la distribution qu'on lui a affectée ?

[Ben314]

Bon, effectivement, il m'a fallu une plombe pour taper le programme puis pour constater que, quasi systématiquement, il donnait des donnes "exeptionelles" (3 ou 4 chicanes dans le jeu et/ou des mains avec 8 cartes ou plus de la même couleur !!!) ce qui confirme ce qui en fait était assez évident : les différentes répart par couleurs ne sont pas équiprobables...

Bon, lors du calcul, pour toutes les répartitions "acceptables" vu les contraintes, on peut calculer le nombres de mains correspondant à cette répart et ce n'est pas trés long.
Par contre, coté "programation" (en tout cas dans mon bon vieux pascal), c'est la merde du fait qu'il faudrait stocker des entiers pouvant aller j'usqu'à 52!/(14!)^4 qui est de l'ordre de 2^96 ce qui demande un stockage sur 12 octets bien supérieur au pauvre "comp" du copro de calcul sur 8 octets...

Pour Galax : sur un "cas particulier" pas trop complexe, il est effectivement jouable de regarder les différentes configs possibles pour le joueur 1, mais dans le cas général (donnée de 4x4 intervalles correspondant aux valeur min/max du nombre de carte d'une couleur donnée pour un joueur donné, c'est passablement la merde.
En plus, je pense que, même si les réparts possibles du joueur 1 sont clairement dans une liste donnée, je pense que la proba de chaque répart risque de dépendre des contraintes que l'on a pour les autres joueurs...

[Galax]

Merci d'avoir regardé.

J'ai tenté une autre approche mais qui semble ne pas fonctionner :

J'ai donc mes 4x4 intervalles, tous cohérents entre eux.
Je les affine au maximum, par exemple pour un joueur donné, on doit avoir Nbmin(T) >= 13-Nbmax(K)-Nbmax(C)-Nbmax(P)
Je tire une carte au hasard, je regarde sa couleur, par exemple P.
Je tire un joueur au hasard, si son Nbmax(P) n'est pas atteint et qu'il a encore de la place, je lui affecte la carte, sinon je tire un autre joueur au hasard.
Lorsqu'une carte a été affectée, je la prend en compte en remettant à jours mes 16 intervalles.
Je passe à la carte suivante

On trouve ainsi très rapidement une main compatible avec les contraintes, mais je ne sais pas bien pourquoi les probas ne sont pas respectées.

[Ben314]

J'ai l'impression que, si au départ, les répartitions "acceptables" pour les Trefles sont :
Nord:0-13 , Est:0-13 , Sud:0-13 , Ouest:0-1
(donc seul contrainte : Ouest est chicane ou singleton Tréfle)
Alors, avec ta méthode, il sera trés trés trés trés rarement chicane à Tréfle alors que, à mon avis il ne devrait être "que" trés rarement chicane à Tréfle (j'espère que tu me comprend...)

[Galax]

J'ai l'impression que, si au départ, les répartitions "acceptables" pour les Trefles sont :
Nord:0-13 , Est:0-13 , Sud:0-13 , Ouest:0-1
(donc seul contrainte : Ouest est chicane ou singleton Tréfle)
Alors, avec ta méthode, il sera trés trés trés trés rarement chicane à Tréfle alors que, à mon avis il ne devrait être "que" trés rarement chicane à Tréfle (j'espère que tu me comprend...)

Effectivement, tu as tout à fait raison
Si on tire un trefle, ne peut on pas déduire de l'ensemble des contraintes, une probabilité d'affecter ce trefle à tel ou tel joueur plutot qu'à un autre ?

[Ben314]

Tient, regarde si ça te parrait aléatoire :
http://www.megaupload.com/?d=A36ZTZ1Y
(c'est du DOS...)

[Galax]

Ca a l'air tout à fait correct.
Sur l'exemple que j'ai donné ( 5-6 à P, 4-4 à C pour J1 et 4-13 à K pour J2 ), mon ancien programme (celui qui tire aléatoire jusqu'à ce qu'il trouve une main satisfaisant les contraintes), je trouve, apres 50.000 tirages, les repart suivantes pour J1 :
5440 : 7%
5431 : 39%
5422 : 32%
6430 : 4%
6421 : 15%
et avec ton prog, en comptant à la main 100 tirages, on obtient
10%, 38% 32% 2% et 18%, ce qui est tres correct.

Tu passes donc en revue toutes les repart possibles ?
Sais tu combien de temps il mettrait pour sortir 50.000 mains, et le temps mis dépend il des contraintes ou bien est ce toujours à peu pres le meme ?

J'ai juste remarqué un pb d'affichage (pas important du tout mais parfois ca peut cacher un pb plus grave), si tu demandes qu'un joueur ait 13 cartes d'une couleur, seules 12 cartes sur les 13 sont triées par ordre.

Merci

[Ben314]

En ce qui concerne l'algo, c'est trés bourrin :
Il y a 16 variables K11,K12,...K44 correspondant au nombre de carte de chaque couleurs possédées par chaque joueur et une "méga boucle"
Pour K11 de m11 à M11 faire
Pour K12 de m12 à min(M12;13-K11) faire
Pour K13 de max(m13;13-M14-K11-K12) à min(M13;13-m14-K12-K13) faire
Pour K21 de m21 à min(M21,13-K11) faire
...
Dans le cœur de la boucle on calcule les valeurs des K4? et des K?4, on vérifie que K44 est entre les bornes prérequises puis, si c'est le cas, un compteur CPT (mis à zéro au départ) est augmenté de (13!)^4 / (K11!.K12! ... K44!) qui correspond aux nombres de donnes possibles telles que les répartitions de couleurs soient K11,K12,... K44.
A la fin de la boucle, le compteur CPT contient donc le nombre de donnes possibles correspondant aux contraintes.
Ensuite, une valeur aléatoire RND est tirée entre 0 et CPT puis on recommence exactement la même "méga boucle" en diminuant la valeur de RND de (13!)^4 / (K11!.K12! ... K44!) dans le cœur de la boucle jusqu'à ce qu'il devienne négatif. On arrête alors la boucle en considérant que c'est cette répartition de couleur qui a été tirée au hasard.
Enfin, on mélange les 13 trèfles et on les donne aux différents joueurs en fonction de la répartition, puis idem pour les 3 autres couleurs. Enfin, on trie les 4 jeux (et c'est là qu'il doit y avoir un Bug, mais ça ne doit pas influer sur le reste).

Concernant le temps qu'il met pour tirer une donne au hasard, ben ça dépend fortement des contraintes : si tu ne met aucune contraintes (0-13 partout), il lui faut presque une minute pour dénombrer le nombre total de donnes (à savoir 52! / (13!)^4 puis, en moyenne, la moitié de ce temps pour tirer une donne au hasard (en fait, ça dépend de la valeur tirée de RND).
Plus tu met des contraintes "fortes", plus le nombre de donnes "acceptable" est faible et plus le programme va vite, à la fois pour calculer le nombre de possibilités mais aussi pour les tirages aléatoires : donc le temps mis pour tirer 50.000 mains, ça va BEAUCOUP dépendre des contraintes (par exemple, si pas de contraintes du tout, ça risque de faire 50.000*30 secondes=30 jours, mais avec des contraintes telles celles dont tu parle, je pense que c'est plus raisonnable)

[Galax]

Merci pour ces infos.

Tout est tres clair, mais du coup je ne pense pas que le gain en temps soit significatif, sauf pour des contraintes tres extremes.

Si l'on veut plusieurs tirages sur les memes contraintes il doit etre possible de ne pas tout recommencer à chaque fois, mais ca nécessiterait comme tu l'as deja dit, un stockage important, sauf si CPT n'est pas trop grand.

Ca m'interesserait de jeter un coup d'oeil à ton source si ca ne te derange pas (je programme d'habitude en C mais je pense que les instruction Pascal sont assez similaires pour etre comprises).

Je vais peut etre faire un panaché, en utilisant cette methode lorsqu'il y a beaucoup de contraintes 'contraignantes', et utiliser l'ancienne dans le cas contraire, où un tirage completement aléatoire a de bonnes chances de verifier d'emblée les contraintes initiales, et est bien plus rapide.

Si le bridge t'interesse tu peux toujours telecharger la version demo de mon logiciel sur http://www.masterbridgeanalyser.com, onglet Achat, en bas a gauche de la page.

[Ben314]

Le source est là :
http://www.megaupload.com/?d=40RYL0AL
Mais c'est un peu tapé "à la vite fait".
C'est du pascal, mais si tu connait le C, c'est quasi pareil (c'est plutôt plus simple et moins "ouvert") de toute façon, il n'y a que ce que je t'ais décrit au dessus (et j'ai pas pensé à enlever le bug à la fin où il y a un "for j:=2 to 12" là ou il devrait y avoir 13...)

Pour ce qui est du Bridge, on joue de temps en temps avec quelques collègues, mais on arrive rarement à être plus de 6 ou 7 (exeptionellement 8 ou on peut commencer à faire "tourner" les jeux).
Au niveau programme, ça fait assez longtemps que j'utilise WBridge qui, vu mon faible niveau est plus que largement sufisant...