MountyHall - La Terre des Trõlls

	Ze Figurines
MountyHall

Référencé sur

Nous sommes le Mundidey du Scarabée du 22° cycle après Ragnarok

Bienvenue Invité

Tous les Forums

Hors Jeux - Les autres Jeux

Modérateurs de ce forum : Aghabeu, Dabihul, Grankausto, Loinvu, Madère, Mamoune, Modérateur 6, Modérateur1, Modérateur2, Modérateur3, Modérateur4, Modérateur5, Mr x, Rouletabille, Schtroumpf, TilK, VYS, Xaruth

Préfixez toujours vos titres de message du nom du jeux. Par exemple :"[Bombix]" ou "[Taupedelire]" S'il s'agit d'une présentation d'un site, n'oubliez pas d'en donner l'URL.

Attention : les liens d'affiliation et autre parrainage sont formellement interdits.

PB mathématique 2 : jeu de belote
[Pages : 1, 2]

#. Message de AngelFace le 25-05-2008 à 18:45	2149 - AngelFace (Skrim 60) - Compañeros Mosca Trõlls -
Pays: France (2A - Corse-du-Sud) Inscrit le : 26-11-2002 Messages: 4231 (Djinn Tonique)	Citer

Vu le succès du premier post, en terme de résultat du moins, je vous soumet un projet qui me trotte dans la tête depuis longtemps.

Je suis un joueur de cartes invétéré, entre autres de belote contrée. Pour rappel, la contrée est un jeu on l'on doit annoncer le contrat et l'atout, de 10 en 10. Divers système d'annonces existent, qui ont leurs avantages et leurs inconvénients. En général, on tente de s'annoncer un maximum de choses, avec un maximum de précision. Pas simple avec peu d'enchères à disposition, au contraire du bridge par exemple.

Sans rentrer dans les détails du jeu, il est intéressant d'établir des probabilités de répartition, afin de déterminer le contrat optimal en fonction de son jeu (connu) et du jeu du partenaire (partiellement connu en fonction des annonces).

Ensuite, il est également intéressant, en fonction du contrat, je jouer de telle ou telle manière pour optimiser ses chances de victoires.

On peut utiliser le vocabulaire du bridge, largement plus évolué au niveau de la théorie.

On parlera d'hypothèse de nécessité dans certains cas. Par exemple, le 10 de pique DOIT être placé en ouest si je veux réussir mon contrat. Dans le cas contraire, je ne pourrais de toute facon pas gagner.

Ou hypothèse de crainte : J'ai gagné si les piques sont répartis 2 - 2. Comment puis-je gagner si les piques sont répartis 3 - 1. Le gain est-il encore possible avec un partage 4 - 0 et a quel prix ?

Je vais donner un exemple concret avec une main complète (P = Piques, C = Coeur, K = Carreau, T = Trèfle, ARDV = As, Roi, Dame, Valet, x = carte quelconque, - = rien) :
P : Vxxx
C : -
K : Axxx
T : -
En face, le partenaire 3 piques.

Il y a capot pique dans plusieurs cas :
- le partenaire a le 10K second, 3eme ou 4eme = 4 plis dans la couleur
- le partenaire a la coupe a K, et les adversaires ont les K 2 - 2 = 1 pli de tête + 1 coupe + 2 plis de longueur.
- le partenaire a la coupe a K, et les adversaires ont les K 3 - 1 = 1 pli de tête + 2 coupes + 1 pli de longueur.
- le partenaire a un K = 1 pli de tête + 2 coupes + 1 pli de longueur, quelle que soit la répartition adversaire.
- le partenaire a 2 K (sans le 10) et les adversaires on les K 1 - 1 = 4 plis

Egalement 2 autres cas, impossibles à jouer :
- le partenaire a 2 K sans le 10, et le 10 de K est placé dans une fourchette AR. Il faudrait être capable de jouer petit K de la main du partenaire vers le roi. Impensable de tenter une impasse directe, sans indication de jeu possible.
- le partenaire a la coupe a K, et un des adversaire a 10xxx. Il faudrait couper 3 fois en laissant trainer le dernier atout (et donc risquer une surcoupe). La encore, jamais un joueur ne touchera une couleur annexe sans jouer atout avec 7 atouts dans la ligne.

En dénombrant les nombres de cas favorables, on se rends compte qu'avec cette main, le capot est à 96%

C'est UN cas donné, et il est assez difficile de faire ce genre de dénombrement, pour plusieurs raisons :
- Pas de généralisation possible, il faut tout calculer.
- Il y a un risque d'erreur important, tant sur le dénombrement en lui meme, que sur les cas faisables (cf les 2 derniers cas).

On ne cherche pas ici une réponse exacte et précise. Une marge d'erreur (chiffre sans virgule par exemple) est largement acceptable. Du coup, je pense que la meilleure solution consisterait à faire un petit programme de donne virtuelle. On impose certains choix, certaines mains, et le programme calcule un nombre importants de cas différents, en donnant les résultats de répartition.

De plus, on parle d'un cas réel. Or, qd je dis que le capot est a 96%, ca veut dire que le nombre de répartions défavorable atteint 4% en théorie. C'est à dire avec un jeu correctement mélangé. Or, à la belote, ce n'est jamais le cas. On bat très epu les cartes, voire pas du tout, avant de distribuer. Du coup, avoir un partage très excentré 4 - 4 est assez fréquent, dans la mesure ou ca peut tout simplement être un pli de la donne précédente.

J'en arrive - enfin - à mes questions :

1/ Qui serait capable de faire un tel programme ?
2/ Comment prendre en considération un jeu non mélangé ?

#. Message de Malachite le 26-05-2008 à 11:18	20848 - ( )
Pays: France Inscrit le : 15-08-2004 Messages: 860 (Shaï Epileptique)	Citer

T'étonnes pas si il n'y a pas de réponse à ce thread : ton problème est plus que difficile. J'ai demandé rapidement autour de moi, et il semble assez probable qu'il n'y a pas de solution connue.

Malachite

#. Message de AngelFace le 26-05-2008 à 14:08	2149 - AngelFace (Skrim 60) - Compañeros Mosca Trõlls -
Pays: France (2A - Corse-du-Sud) Inscrit le : 26-11-2002 Messages: 4231 (Djinn Tonique)	Citer

Pour l'exemple que je donne, 2 pages de calculs, et quelques heures pour traquer les erreurs. C'est pour ca que je cherche plutôt à faire un programme.

Hélas, il faut trouver quelqu'un qui réunisse 3 conditions :
- Connaitre la programmation
- Avoir un certain niveau en maths
- Connaitre un minimum la belote

Bref... 2 ans que je cherche dans mon entourage

#. Message de Malachite le 26-05-2008 à 15:22	20848 - ( )
Pays: France Inscrit le : 15-08-2004 Messages: 860 (Shaï Epileptique)	Citer

Ce que je voulais dire, c'est qu'il est fort probable que personne sur terre ne puisse te donner un algorithme qui donne un résultat intéressant. Les mathématiques de ce genre de problèmes sont très compliqués. Et il est fort probable (aux vues des connaissances que j'ai pu réunir) que personne ne sache les faire.

#. Message de cirederf le 26-05-2008 à 16:28	109308 - Dvergar (Darkling 47) - Les Pilleurs des Ombres -
Pays: France (17 - Charente-Maritime) Inscrit le : 27-06-2005 Messages: 6862 (Hydre Fumante)	Citer

AngelFace > je connais la programmation, j'ai pas un mauvais niveau en math (je voulais être prof de maths, j'ai fini dans l'informatique), j'adore la belote (par conte je n'ai jamais joué à la contré mais j'ai déjà joué au bridge).

Et bien ton problème a tellement de paramètre que soit on donne des valeurs au carte comme au poker pour faciliter le calcul et suivant la valeur des mains ça donne une probabilité de réussite.
Soit il faut faire une IA qui a toutes les mains possible et joue tous les coups (on avait fait un puissance 4 et un jeu d'échec en programmation avec étude des calculs dix coups à l'avance) Mais toi là ça devient super complexe et je ne sais pas en combien de temps le calcul sera fait pour une main donnés et toutes les mains possibles chez ton partenaire et adversaire.
Quand au fait que les cartes sont très peu distribué voir jamais et bien ce paramètre est quasiment impossible à définir ou alors en privilégiant les proba d'avoir plutôt 3 ou 4 cartes dans la même mains vu la façon dont on distribue (une sorte de majoration arbitraire sur ces cas là).

#. Message de AngelFace le 26-05-2008 à 20:12	2149 - AngelFace (Skrim 60) - Compañeros Mosca Trõlls -
Pays: France (2A - Corse-du-Sud) Inscrit le : 26-11-2002 Messages: 4231 (Djinn Tonique)	Citer

Si tu sais jouer au bridge, et si tu connais les règles de la belote, il n'y a aucun souci de compréhension. Tu vas pouvoir comprendre par exemple la notion d'appel Lavinthal, ou d'ouverture de barrage, d'hypothèse de necessité ou de crainte, de partage de couleur, etc...

A noter que j'ai récupéré un source de programme intéressant (mais que je suis incapable d'utiliser). Il s'agit d'un programme résolvant les grand chelem au bridge, pour des mains données. Donc, qui donne le jeu de la carte obligatoire pour réussir un contrat. Ayant eu un petit échange de mail avec le créateur du soft (qui distribue son source libre), il s'avère que généraliser à tous les cas devient un casse-tête impossible à résoudre.? Du moins, il n'a pas réussi.

Cependant, j'ai tellement d'interrogation que certaines devraient être facilement programmables.

Par exemple, quel est le % de chances d'avoir une certaine forme de jeu ? Quel est le partage résiduel d'une couleur donnée ? Quel % de cas défavorable y a-t-il d'embarquer une carte a point sur un 2ème coup dans une couleur donnée (partage résiduel + probabilité de répartition).

Ce sont de "simples" problèmes de dénombrement, que j'aimerais bien généraliser. Mais de suite, on sombre dans une complexité phénoménale.

Pour ma part, j'avais quelques notions de maths et d'info, mais pour n'avoir plus pratiqué depuis 10 ans, je ne sais plus rien faire.

Le mieux est d'en parler sur MSN, ou sur IRC. Mon adresse est sur mon profil.

#. Message de Malachite le 26-05-2008 à 21:12	20848 - ( )
Pays: France Inscrit le : 15-08-2004 Messages: 860 (Shaï Epileptique)	Citer

> Par exemple, quel est le % de chances d'avoir une certaine forme de jeu ?
Ca, pour des "formes" raisonnables, c'est a priori plutôt facile. Ca rentre dans le cadre des distribution hypergéométriques. En fouillant un peu wikipedia, tu devrais pouvoir comprendre comment ça marche

.

Je m'y connais pas trop dans ce genre de question, donc je peux pas franchement t'aider plus qu'en donnant quelques directions.

Malachite

#. Message de charlo le 29-05-2008 à 18:33	70862 - charlo (Tomawak 53) - Solar Fire [Damnés] -
Pays: France (44 - Loire-Altlantique) Inscrit le : 20-12-2005 Messages: 5205 (Hydre Fumante)	Citer

on appelle ca la coinche par chez nous

a part ca bon courage pour ton probleme

#. Message de frozhalf le 29-05-2008 à 19:31	71057 - frozhalf (Tomawak 30) - Les Trolls Génétiquement Modifiés -
Pays: France Inscrit le : 28-11-2005 Messages: 652 (Shaï Epileptique)	Citer

à mon avis le gros problème c'est que tu connais pas le jeu du partenaire ce qui fait un nombre de cas de figures très grand...

un autre gros problème c'est la manière de jouer. en effet une fois la répartition effectuée tu as un nombre de cas de figure niveau jeu hyper important, suivant la couleur où tu pars, ta manière de jouer (faire des impasses, tenter le 10 pensant à l'impasse, etc...)

bref du coup j'ai bien peur que la probabilité que t'obtiennes soit pas terrible ou alors non significative si tu prend tous les cas de figure car on joue quand meme préférentiellement certaines cartes que d'autres d'abord.

par contre pour des cas très particuliers (comme celui que tu cites) il est possible à mon avis de calculer des probas (mais comment ? bonne question)

#. Message de AngelFace le 30-05-2008 à 15:32	2149 - AngelFace (Skrim 60) - Compañeros Mosca Trõlls -
Pays: France (2A - Corse-du-Sud) Inscrit le : 26-11-2002 Messages: 4231 (Djinn Tonique)	Citer

On a des indications sur le jeu du partenaire, en fonction du système d'annonce. Par exemple : 80 Pique = Valet ou 9 manquant, un as à coté. Le partenaire donne : + 10 pts = V ou 9. 20 pts = 3 atouts. 30 pts = V 3eme ou 9 3eme. 40 pts = V 3eme ou 9 3eme accompagné d'un as. Dans cet exemple, on a des informations qui sont données (30 pts, il a le V 3eme car j'ai le 9) et des informations inférentielles (puisqu'il ne m'a donné que 30 pts, il n'a pas d'as !).

A travers cet exemple, on comprends ce que je recherche : Sur 32 cartes, j'en connais 8 (les miennes); Sur les 8 cartes de mon partenaire j'en connais 1 a 100%, et 2 dans un choix de 3 ou 4 cartes. De plus, sur les 5 cartes restantes, je sais qu'il n'a pas d'as. En fonction du jeu de la carte, je saurais refaire les mains au fur et a mesure de l'arrivée des informations.

La façon de jouer découle directement de ces informations. Ai-je intérêt à une impasse au 10, ou a jouer mon as suivit d'un retour dans la couleur en espérant la coupe de mon partenaire (le terme précis s'appelle l'expasse).

Ces probabilités de répartitions sont très bien définies au bridge, mais avec un jeu plus simple : 52 cartes au lieu de 32, mais le jeu du partenaire connu à 100%, car le mort est étalé à la vue de tous. Pour refaire les 2 mains inconnues (les adversaires, ou un adversaire et son partenaire dans le cas du flanc) on utilise les informations qui nous parviennent (on fournit ou pas a une couleur, on donne un compte des cartes, on fait des appels, on obéit ou pas a un appel, etc...). C'est la théorie des résidus. J esais utiliser ces informations, mais je ne sais pas les calculer dans un autre cas (au bridge, il y a des 10aines de livres qui traitent du sujet).

#. Message de frozhalf le 31-05-2008 à 00:43	71057 - frozhalf (Tomawak 30) - Les Trolls Génétiquement Modifiés -
Pays: France Inscrit le : 28-11-2005 Messages: 652 (Shaï Epileptique)	Citer

alors là je suis carrément pas d'accord sur le début... tu peux gagner un grand nombre de 80 sans avoir ni le valet ni le 9 à l'atout. Pareil j'ai l'habitude de remonter systématiquement 20 lorsque j'ai le valet (puisque je ramène plus que 20 pts) 10 pts ça peut correspondre au 9 ou à l'As troisième, 2 As à côté ou encore 1 As avec 2 petits atouts... bref et encore je te parle meme pas où tu remontes pas de la meme manière suivant que ton enchère est un peu forcée par l'adversaire ou pas, et suivant la valeur de l'enchère (genre tu remontes pas aussi facilement 1 as sur un 130 que sur un 80)

bref les habitudes de jeu de chacun étant plutôt différentes il devient très difficile ne serait ce que de formaliser les méthodes de jeu et d'enchères de chacun des joueurs, avant même de parler de probabilités. Ceci d'autant plus qu'à la coinche il y a un phénomène de mémoire des plis précédents puisque l'on ne mélange pas entre les parties...

bref tous ces éléments compliquent considérablement ton algorithme...

#. Message de AngelFace le 1-06-2008 à 18:22	2149 - AngelFace (Skrim 60) - Compañeros Mosca Trõlls -
Pays: France (2A - Corse-du-Sud) Inscrit le : 26-11-2002 Messages: 4231 (Djinn Tonique)	Citer

Ce n'esrt pas le problème le système d'annonce, et pas le sujet. Si on prends le système que je propose, on peut avoir des informations précises sur le jeu du partenaire. Avec le tien, on ne peut pas faire le distingo, donc, on a simplement des données différentes.

Le principe est de poser des bases concrètes et réalistes, afin de déterminer des probabilités de répartitions. Pas de créer / modifier un système d'annonce.

#. Message de Dadour le 3-06-2008 à 15:35	32476 - Dadour (Skrim 60)
Pays: Non Précisé Inscrit le : 4-08-2004 Messages: 4196 (Djinn Tonique)	Citer

Le probleme la dedans c'est pas les math, c'est de definir ta sequence de jeu comme un automate. Quoi jouer, quand couper pisser faire une impasse, quoi annoncer.

Pour calculer les proba, meme avec des donnes non melanges, suffit de faire une simulation numerique et de faire jouer un bot en boucle sur des milliers de parties.

Du coup le non melange se fait aussi facilement que dans une partie reelle.

Aucun interet les maths des que ca depasse une certaine complexite, un ordi ca sert beaucoup plus.

#. Message de AngelFace le 3-06-2008 à 18:29	2149 - AngelFace (Skrim 60) - Compañeros Mosca Trõlls -
Pays: France (2A - Corse-du-Sud) Inscrit le : 26-11-2002 Messages: 4231 (Djinn Tonique)	Citer

Voila Dadour, c'est exactement ça en ce qui concerne le jeu de la carte. Mais les probas de répartition sont intéressantes aussi, pour déterminer l'intérêt de tel ou tel système d'annonce, sans jeu de la carte.

#. Message de Dadour le 5-06-2008 à 23:28	32476 - Dadour (Skrim 60)
Pays: Non Précisé Inscrit le : 4-08-2004 Messages: 4196 (Djinn Tonique)	Citer

Si jamais tu as des bases de programmation ou que tu veux t'y mettre je peux te faire un squelette de programme en te laissant juste 2 ou 3 fonctions a remplir. Enfin si je trouve le temps un week end.

Mais je te laisserait la partie jeu de la carte et annonces parce que j'ai pas envie d'y passer des plombes non plus.

Les probas, c'est pareil que le reste, faut faire des milliers de donnes pour les avoir. Mais elles vont peut etre un poil dependre du jeu. Enfin entre 2 systemes de jeu, les probas doivent etre proches.

Tu me dis si ca t'interresse.

#. Message de AngelFace le 5-06-2008 à 23:31	2149 - AngelFace (Skrim 60) - Compañeros Mosca Trõlls -
Pays: France (2A - Corse-du-Sud) Inscrit le : 26-11-2002 Messages: 4231 (Djinn Tonique)	Citer

J'ai un squelette de bases en programmation, mais depuis le temps que j'en ai pas fait, ca risque de pas être simple ^^

Cela dit oui ca m'interesse

Il faudrait en parler sur MSN, ce serait plus pratique. Mon adresse est sur mon profil.

#. Message de Fafi le 2-07-2008 à 14:22 [Ami de MountyHall]	709 - Plotch (Kastar 60) - Les morveux de mamie vieille -
Pays: France Inscrit le : 7-06-2002 Messages: 3016 (Djinn Tonique)	Citer

Ceci dit, il y a en fait 2 parties dans ton boulot, et moi je separerai strictement les 2.

1) partie : J'ai un jeu strictement donne autour de la table (la donne est complete et connue completement, un peu comme si tu jouais jeu decouvert) : Effectuer un calcul de probabilite de reussite de ton capot.
Ca a l'avantage d'eliminer d'entree de jeu la complexite des annonces et importances des cartes. En effet, je peux t'assurer que parfois un roi ou une dame peuvent casser le jeu d'un capot aussi surement qu'un 10.
2) Une fois la programmation de l'automate de jeu des parties, simuler l'interfacage de donnes non completement definies... Et ce d'autant que tu aura deja une tres bonne idee de comment fonctionne ton automate de calcul

Vala, sinon ton probleme en haut ne depend pas tout a fait que de cela, mais aussi de :
- Quel joueur entame la partie, trop souvent oublie ce parametre. La plupart des joueurs n'y pensent que dans des situations critiques telles que le capot, mais meme dans une partie normale ou tu dois serrer les contrats au max de tes capacites, c'est tres important.
Sur ton exemple, un adversaire commence et joue K. Le preneur vient ensuite. l'adversaire suivant, pas de chance coupe avec le seul atout qui reste en jeu, et ton collegue ben l'en a un de K. Certes, c'est pas de chance. Si vous aviez pu commencer, l'atout serait tombe, pourtant, ben l'ouverture primordiale a fait chute le capot.

PS : pour ceux qui, comme moi, seraient heurtes par de l'interfaCage, sur une station Unix, impossible de mettre la cedille ni les accents...

#. Message de Harmonie le 2-07-2008 à 16:03	34868 - ( )
Pays: France Inscrit le : 20-04-2004 Messages: 436 (Golem Costaud)	Citer

Fafi tu exagères: il suffit de configurer ton claver en anglais international, c'est exactement ce que j'ai fait et çà pérmét dé pàrlér lé tröll. Ou alors un plugin de correction orthographique pour Firefox

Pour le soucis en cours de discussion, le plus simple reste encore à mon avis, et je rejoins Dadour, de faire jouer des parties à un automate. Le soucis restant étant qu'il faut une IA pour obtenir des résultats intéressants (personne ne joue ses cartes au hasard).

C'est le genre de problème pour lequel PROLOG est fait; il est également possible de se tourner vers des machines d'inférence genre DROOLS. En gros: tu entres toutes tes suppositions, axiomes et heuristiques dans la machine et tu la laisses débrouiller le reste. Les résultats seront à la hauteur de la qualité de tes règles, à voir si ça permet de résoudre certaines de tes questions les plus simples ?

My two cents,

H.

#. Message de AngelFace le 3-07-2008 à 15:46	2149 - AngelFace (Skrim 60) - Compañeros Mosca Trõlls -
Pays: France (2A - Corse-du-Sud) Inscrit le : 26-11-2002 Messages: 4231 (Djinn Tonique)	Citer

Fafi et Harmonie, merci pour vos idées. Cependant, je suis totalement incapable de programmer un automate. Pour la proposition d'Harmonie, c'est pire : je ne comprends pas les termes employés

Pour le départ, j'y pense à chaque fois. En fait, mon système d'annonce change légèrement en fonction de la position du donneur.

Il y a 3 idées générales :
- Comparer et optimiser les systèmes d'annonce.
- Trouver le meilleur % de réussite d'une ligne de jeu (jeu de la carte).
- Evaluer le % de réussite d'un contrat a priori (donc quelque soient la distribution des 3 autres jeux, en fonction d'un jeu donné).

Bref, vos idées ont l'air intéressante, mais sans un minimum d'aide, je ne peux pas tester. Si vous voulez aller plus loin dans vos explications, mon MSN est sur mon profil (pas facile d'une station unix je suppose ^^)

#. Message de Dadour le 11-07-2008 à 00:11	32476 - Dadour (Skrim 60)
Pays: Non Précisé Inscrit le : 4-08-2004 Messages: 4196 (Djinn Tonique)	Citer

Pas eu le temps moi, et pas trop l'envie non plus en sortant de journees passes dans du code pourri au boulot. J'avais fait un mini truc mais pas fini encore. La flemme a du mal a me quitter en ce moment. C'est con je joue plusieurs fois par semaine ca me dirais bien de connaitre le systeme ideal, mais trop la flemme quand meme

.

Si tu veux te lancer moi je te conseille plutot c++ et si t'a windows (non tout le monde n'a pas unix sur son pc perso...) cygwin pour compiler. Plein de tuto sur le net, plus commun que prolog et moins une usine a gaz. En plus ca permet de faire plein de choses, pas que des algo etranges.

[Pages : 1, 2]

Pour poster une réponse sur ce Forum, vous devez d'abord vous connecter

Si vous n'êtes pas encore enregistré, vous devez d'abord vous inscrire.

Changer de Forum

[ Contact : ] - [ Heure Serveur : 21:47:26 le 05/05/2024 ] - [ Page générée en 0.007 sec. ]