Paradoxe des boîtes de Bertrand

Description

On prend trois boites identiques Ces boites sont opaques et disposées dans un ordre inconnu, vous ne savez évidemment pas leur contenu en les voyant.

Chacune des trois boites renferme deux pièces d'or ou d'argent.
-L'une des boites contient deux pièces d'or,
-Une autre contient deux pièces d'argent,
-La troisième contient une pièce d'or et une pièce d'argent.

Vous choisissez une boite et on vous présente au hasard, une des deux pièces qui se trouvent à l'intérieur.

Si c'est une pièce d'argent, la partie est nul, si c'est une pièce d'or, vous devez deviner la matière de la 2em pièce.

Avez-vous intérêt à miser plutôt sur l'or ou l'argent pour la seconde pièce ? Ou autant sur l'un et l'autre de ces métaux ?

Problème simple des trois portes.

Description

Lors d'un jeu télévisé, le présentateur montrait trois portes fermées au candidat et affirmait que derrière l'une d'entre-elles se cachait un cadeau (une voiture) et qu'il suffisait d'indiquer la bonne porte pour gagner.

1. - En supposant que l'emplacement du cadeau a été choisi au hasard et qu'il y a équiprobabilité, le candidat a une chance sur trois de désigner la bonne porte.
Pour l'instant on n'ouvre pas cette porte.

2. - Ensuite le présentateur ouvre l'une des deux portes autre que celle qui a été choisie et autre que celle qui cache la voiture.

3. - Le candidat a le choix entre maintenir son premier choix ou le modifier. Que lui conseillez-vous de faire ?

Pour le premier problème, à vue de nez, on peut jouer autant l'or que l'argent, pour le choix de la seconde pièce. C'est un problème de probabilités conditionnelles et cela se calcule, mais, simplement avec le raisonnement, on peut dire que:
1)la partie est nulle si on tire de l'argent; donc la partie ne compte pas; on ne considère que les parties où la première pièce tirée est de l'or; donc on ne considère que les parties où les boîtes 1 et 3 sont tirées; donc c'est comme si la boîte 2 (contenant argent + argent que je note A+A) n'existait pas.
2)On considère donc le jeu avec la boîte 1 (O+O) et la boîte 3 (O+A); sachant que O a été tiré, il reste dans ces boîtes : O dans 1 et O+A dans 3 si le tirage a eu lieu dans 1 et O+O dans 1 et A dans 3 si le tirage au eu lieu dans 3. La seconde pièce à trouver est O si on est dans la boîte 1 et A si on est dans la boîte 3; or les boîtes 1 et 3 sont équiprobables.

Donc on peut jouer autant O que A.

Je contrôlerai par un calcul de probas.

J'ai vu un test avec plusieurs carrés remplis de point dont un seul était le fait du hasard, je ne l'ai pas trouvé bien qu'ils soient tous très différents, comme la plupart des gents d'ailleurs (on imagine pas ce que peut faire le hasard, si un jour les numéros du loto sorte dans l'ordre les gents crieront à la tricherie)

Le paradoxe des boîtes de Bertrand s'assimile à ce genre de problème:
http://fr.wikipedia.org/wiki/Paradoxe_des_trois_pi%C3%A8ces_de_monnaie
dans lequel on utilise les probabilités conditionnelles.

Pour le problème des portes, j'ai fait une erreur, ne pensant pas à dédoubler les deux cas où le joueur choisit la mauvaise porte, ce qui fait qu'il y a apparition d'une probabilité de 2/3 et non de 1/2.

Mais pour les boîtes avec les pièces, je ne suis pas du tout convaincue; je regarderai ça demain soir en descendant de train.

[quote="Elisabeth"]

Buonaparte a écrit:

Attention à l'énoncé: à partir du moment où on demande quelle pari il faut miser pour le second tirage sachant qu'on a tiré l'or au premier tirage il ne s'agit pas d'un calcul de probabilités simples, mais de probabilités conditionnées au fait qu'on n'est pas dans le cas A au premier tirage. Par ailleurs, dans la première boîte il n'y a pas une série de deux évènements O-O puisque les pièces sont indiscernables, seule leur matière est marquée.

En fait, les deux choix sont liés, tu pense que les compteurs sont remis à zéro et qu'il reste dans la boite, soit une O ou une A, en oubliant que tu as deux fois plus de chance de tomber sur une OO plutôt qu'une OA.
C'est un choix "Boite-pièce"
Quant tu devrai choisir la pièce, dans les 2/3 des cas, tu seras dans une OO !
Je crois que certain on même fait le test en réel.

J'ai rajouté un dessin plus haut pour expliquer qu'il est inutile de séparer les deux OO et OO, à condition de prendre note qu'ils ont un poids deux fois plus gros que les tirages du type OA ( ce que je n'ai pas fait tout à l'heure, d'où mon erreur).
Voici maintenant mon dessin contenant un vrai calcul de probabilités:



Tu avais raison de dire que je me trompais en ne voyant pas que j'avais deux fois plus de chances de tomber sur OO que sur OA. Précisément l'erreur venait de ce que le OA provenant de la boîte 3 avait deux fois moins de chances d'arriver que le OO provenant de la boite 1 (dans le dessin ci-dessus les colonnes bleues ont une probabilité moitié des colonnes rouges. Je disais que ce qui provenait des deux boîtes était équiprobable, or, non: de la boîte 3 avait été extirpé la moitié des évènements possibles seulement.
Il vaut mieux faire un vrai calcul que d'essayer de raisonner de manière empirique. Il y a plein de traitrises comme cela dans les exercices de probabilités.
Pour avoir un topo sur la notion de probabilité conditionnelle ou conditionnée, voir:
http://fr.wikipedia.org/wiki/Probabilit%C3%A9_conditionnelle

Peut-être quand changeant le problème, les choses seraient plus claires, comme un crabe qui doit pincer un pied sur la plage où il y aurai 3 personnes ; une sans chaussure, une avec deux et une troisième qui n'en a qu'une. Pour le crabe, il y a 3 pieds sans chaussure et 3 avec, comme pour les boites, OO a autant de chance d'être touché que OA sauf que les A sont rejetés par le nul.
Mais le but du jeu était de démontrer que l'esprit humain a beaucoup de mal à détecter le hasard, d'ailleurs il est toujours à se plaindre ou dire ; c'est pas de chance ou qu'elle chance.
Napoléon disait que le hasard n'existait pas.

Si on demande à plusieurs personne de donner au hasard ! un chiffre compris entre 0 et 10, le résultat n'aura rien du hasard.

Personnellement, la première fois que j'ai joué au échec, j'ai battu un champion, en jouant au hasard, bien entendu, je venais d'apprendre les règles et je faisais seulement attention de ne pas faire de coup idiot, mon adversaire voulait me faire tomber dans des pièges de débutant et ne comprenais plus une façon de jouer pas très logique, je suis pourtant un joueur moyen. De même, certains joueurs ne voit pas qu'ils ont gagner, c'est psychologique.

Je joue au jeu vidéo et je suis surpris des progrès de l'IA, les commandes et la façon de jouer devient "instinctive"

Il existe un test vocale ou écrit pour calculer le temps qu'une machine peut tenir en se faisant passer un humain (certaine personne se font carrément berner par une machine qui donne des réponses intelligentes humaines



http://www.grappa.univ-lille3.fr/~torre/Recherche/Encadrement/Delzons2004/

http://www-poleia.lip6.fr/~zucker/Papers/%20CAP%2799.pdf





IX.Introduction L’intelligence artificielle est incluse dans un cadre d’application très vaste. Quand ces mots sont prononcés, les images qui viennent à l’esprit sont liées au futur sans rapport au monde actuel. Or, dans les années 50, des machines pouvant gagner contre des joueurs humains à des jeux où le match nul seul peut être espéré, ont été créées. Ce sont des jeux comme le dilemme des prisonniers ou encore le pile ou face.
Ainsi pour ce type de jeu, une machine est capable de battre systématiquement un joueur humain. L’explication avancée et acceptée est que l’être humain n’est pas capable véritablement de produire de l’aléatoire et finit par répéter ces choix. Il est alors facile de prévoir les coups du joueur humain pour une machine car celle-ci a une mémoire infaillible.

La théorie des jeux
L’étude de ces jeux implique de raisonner en termes de rationalité, de modélisation et d’anticipation des comportements. En effet, pour vaincre un adversaire à un tel jeu, il est nécessaire de se donner les moyens d’anticiper ses choix. Pour cela, il faut être capable de construire un modèle de son comportement en fonction de la rationalité qu’on lui prête.
Contrairement aux jeux à information complète et parfaite, les stratégies les meilleures contre un adversaire particulier ne sont pas nécessairement celles qui supposent que cet adversaire soit parfaitement rationnel ni parfaitement adapté à d'autres adversaires.
De tous ces différents jeux, le jeu le plus simple est le « Pile ou Face » (ou encore le « pair ou Impair »). Ce jeu si simple a suscité l’intérêt de Claude Shannon qui a inventé une machine efficace contre les joueurs humains [Shannon, 1953]. « Minasi », un autre algorithme, fut également créé et il est, lui aussi, efficace contre les humains. Mais, lorsque les deux algorithmes jouent l’un contre l’autre, Shannon est plus performant.
La machine de « Shannon » fonctionne suivant huit situations. Si une des situations est sélectionnée, « Shannon » joue selon cette situation sinon « Shannon » joue au hasard. Une seule des huit situations peut être activée c'est-à-dire que c’est une des huit ou aucune.
La machine de « Minasi » enregistre tous les coups joués et regarde s’il y a une répétition de la plus grande séquence possible. Si la répétition existe, « Minasi » va jouer ce qui a été le plus joué jusqu’à présent. « Minasi » joue au hasard dans deux situations : au début de la partie (les deux premières fois) et s’il ne peut pas distinguer deux situations identiques.
La Théorie des jeux permet de déterminer la stratégie optimale théorique, lorsque celle-ci existe. Mais dans les jeux à information complète et imparfaite la solution optimale est différente de celle de la Théorie des jeux. En effet une solution optimale se présente sous la forme d’une répartition probabiliste des coups à jouer en fonction des situations de jeux. Mais une telle stratégie garantie la partie nulle.
Dans le cas du jeu « Pile ou Face », la théorie des jeux nous donnerait comme théorie optimale de jouer au hasard. Mais, il est connu que le joueur humain n’est pas capable de produire de l’aléatoire, c’est pourquoi on peut faire ressortir un comportement répétitif au cours du temps. C’est d’ailleurs sur ce principe que sont basés « Shannon » et « Minasi ». Le Q-Learning va capturer également ce paramètre.

../..

../..

XI.II. Mind Reading Machines, ce qui existe déjà avec le jeu « Pile ou Face »
Shannon (1953)
Son fonctionnement
Shannon considère que deviner ce que joue l’adversaire se résume à huit situations. Ces huit situations sont :
j’ai gagné, puis j’ai rejoué la même chose et j’ai encore gagné
j’ai gagné, puis j’ai rejoué la même chose et j’ai alors perdu
j’ai gagné, puis j’ai changé mon jeu et j’ai encore gagné
j’ai gagné, puis j’ai changé mon jeu et j’ai alors perdu
j’ai perdu, puis j’ai rejoué la même chose et j’ai alors gagné
j’ai perdu, puis j’ai rejoué la même chose et j’ai encore perdu
j’ai perdu, puis j’ai changé mon jeu et j’ai alors gagné
j’ai perdu, puis j’ai changé mon jeu et j’ai encore perdu

Pour chacune de ces 8 situations, « Shannon » mémorise si le joueur a, au coup suivant, rejoué comme à son dernier coup ou si le joueur a changé de choix. Il mémorise aussi, si ce choix est le même que celui fait lors de la précédente rencontre de la situation. Le jeu de « Shannon » consiste à parier que le joueur qui s’est montré constant vis-à-vis d’une situation le restera à la prochaine rencontre de cette situation.
Par exemple, dans le jeu « Pile ou Face » si le joueur humain a joué Pile, qu’il gagne, qu’il rejoue Pile et qu’il regagne alors la première règle sera incrémenter de un. Cela donne pour la situation VVV. La prochaine fois que « Shannon » rencontrera cette situation, il verra si l’humain a un comportement constant ou non et jouera en conséquence. Par exemple si le joueur humain gagne, qu’il joue Face et qu’il regagne alors Shannon jouera Face car il retrouve le comportement VVV.
Si le joueur a changé d’attitude confrontée à une situation donnée, « Shannon » choisit au hasard son coup, de même qu’en début de série lorsque les informations disponibles sont insuffisantes. « Shannon » joue en fonction du contenu des 8 mémoires si le contenu de la mémoire est supérieur à deux. S’il est inférieur à deux, « Shannon » joue au hasard. Si une prédiction s’avère non fondée, le contenu de la mémoire correspondante est effacé même si cette prédiction a été juste de nombreuses fois avant. « Shannon » a un comportement adaptatif dans le sens où il s’adapte au joueur humain et utilise l’aléatoire de nombreuse fois. Le contenu d’un élément de mémoire contient la conséquence du coup, l’attitude au coup suivant et la répétition du coup.

Minasi
Fonctionnement
珷Minasi牷 analyse les patterns compos閟 par les coups successifs des 2 joueurs. Dans cet algorithme, un pattern est une s閝uence de paires de coup (un par joueur). Dans une s閞ie, l抏nsemble des paires de coups est enregistr?en continues.
Exemple? P f P p F f P f P p F p F f F f F p P p
Majuscule => joueur Minasi? Minuscule => joueur humain
P => pile? F => face
Lorsque le syst鑝e doit effectuer son choix pour le coup suivant, il recherche, dans l抏nregistrement, la plus longue s閞ie de coups r閜閠閟 au moins une fois, qui correspond ?la situation actuelle. Mais il part des derniers coups.


SAGACE (Solution Algorithmique Génétique pour l’Anticipation de Comportement Evolutifs)
Pour définir le mode de fonctionnement de « S.A.G.A.C.E. », je me suis référencée à l’article de J.P. Delahaye dans le journal « Pour la science », à celui de Meyer & Zucker et aussi de la thèse de Meyer car les droits sur SAGACE sont privés.
C’est une méthode plus complexe que « Shannon » et « Minasi ». Il fonctionne en deux modules :
Le premier module est la compréhension de l’adversaire c’est-à-dire l’élaboration de règles de comportement.
Ex : si les coups précédents sont (pile, face), (face, pile), (pile, pile) alors jouer pile (humain, SAGACE).
Beaucoup de règles sont créées et comparées au jeu de l’adversaire humain. Le modèle attribue aux règles, qui décrivent correctement le comportement de l’adversaire, un coefficient de validité plus fort qu’à celles qui le décrivent mal. La gestion des règles et des coefficients à chaque nouveau coup joué définit un « profil comportemental » de l’adversaire humain. Il permet de faire une prédiction du comportement humain au prochain coup. Dans la dernière version le nombre de coups passés susceptibles d’intervenir dans une règle est 16. Le dernier coup a plus d’importance que les plus anciens qui sont oubliés à la longue.
Le second module est le choix du coup :
Si l’une des règles s’appliquent, d’après le Module 1, alors SAGACE joue ce que prédit cette règle sinon il joue au hasard.
Lorsqu’une règle est appliquée avec succès, le programme en augmente le coefficient de validité, ce qui rend plus probable son application future. Lorsque qu’une règle est appliquée avec échec, le programme en diminue le coefficient de validité, ce qui rend moins probable son application future. Lorsque plusieurs règles sont utilisables simultanément, on prend celle dont le coefficient de validité est le plus grand mais selon un principe probabiliste qui a pour effet de rendre non déterministe le comportement de « SAGACE » (face à une même série de coups, on a pas la même réaction à chaque fois). Il utilise le tirage roulette afin de déterminer la règle qu’il va appliquer.
Un jeu de règles initiales est présent dans le système en début de partie (il a été mis au point soigneusement à la suite de longues séries de tests). En plus, à chaque étape du jeu, de nouvelles règles sont créées par les algorithmes génétiques. C’est-à-dire que l’on modifie légèrement une règle qui possède un bon coefficient de validité (mutation), ou on mélange 2 bonnes règles ensembles. Un programme simplifie plusieurs règles ayant une zone commune pour n’en garder qu’une. Des nouvelles règles sont aussi rajoutées par application de la « méthode du regret », c’est-à-dire après un coup perdu, « SAGACE » ajoute une règle indiquant ce qu’il aurait du faire pour gagner. Par conséquent cela déclenche une quantité importante de calcul à chaque coup et nécessite des parties longues (500 coups) afin que SAGACE puisse converger vers un modèle satisfaisant.
TitAfterTit
Le « TitAfterTit » est une allusion à la stratégie « TitForTat » utilisée dans le jeu du « dilemme du prisonnier ». Il joue (après le premier coup) toujours comme l’adversaire au coup précédent quelque soit le résultat. La prédiction du coup de l’adversaire est qu’il reproduit toujours son dernier coup sans tenir compte de ses conséquences : si (*, M) alors Coups_Suivants(B,M). La stratégie est implicite, non adaptative et pas aléatoire. Les résultats des coups ne sont pas tenus en compte. La mémoire des coups vaut 1 (seulement le dernier coup joué en mémoire). La longueur des patterns est donc de 1. La taille de la mémoire vaut également 1 (le dernier coup de l’adversaire). Le contenu d’un élément de la mémoire vaut un coup (pile ou face).

Récapitulatif
Tableau 1 : récapitulatif.
Mathématique 30-70 Shannon SAGACE Périodique Automate REUSSITES
Mathématique 50 50 50 50 50 50
30-70 50 45 42 42 50 45.8
Shannon 50 55 48 50 57 52
SAGACE 50 58 52 76 61 59.4
Périodique 50 58 50 24 49 46.2

Source : [Delahaye Jean-Paul, « L’intelligence humaine à nouveau dominée ? » Pour la Science n° 263, Septembre 1999.]
Ce tableau correspond aux résultats de cinq algorithmes pour le jeu « Pile ou face ». Dans le tableau c’est le pourcentage des réussite de six stratégies de jeu confrontées deux a deux.
Le classement est : SAGACE, Shannon, Mathématique, Périodique et 30-70. Ce classement peut peut-être s’expliquer par le fait que « SAGACE » et « Shannon » savent exploiter le comportement répétitif des joueurs. « Mathématique », lui, assure le match nul car dans sa théorie c’est cinquante pour cent Pile et cinquante pour cent Face mais si un comportement se répète il n’est pas capable de le détecter.
Quand on compare « Shannon » et « Minasi », on trouve une différence qui est la mémoire des coups. « Minasi » retient tous les coups joués, pourtant celui-ci a des résultats moins bons que « Shannon » face à un joueur humain. L’oubli est peut être nécessaire pour permettre une adaptabilité plus grande. Après tout l’homme oublie ces coups et pourtant il peut lui arriver de faire match nul avec ces intelligences.


Le protocole expérimental est donc :
Alpha = 0.3, gamma = 0.0
Les joueurs humains contre « Shannon » et contre « Prosper »
Les parties sont de 100 coups
On laisse le score des joueurs
Le message au début est « Bonne chance »
Le nombre de joueurs humains est de 36
Nous voulons que les joueurs humains jouent contre les deux intelligences afin de pouvoir comparer leurs performances et ainsi pouvoir comparer « Shannon » et « Prosper ».
Nous avons choisi de faire des parties de 100 coups car les joueurs humains doivent jouer contre les deux intelligences et les joueurs humains se seraient lassés de jouer deux fois 200 coups. La lassitude des joueurs en fin de partie peut fausser les résultats ou, au contraire, faire ressortir un comportement répétitif inconscient.
Nous avons laissé le score afin que l’humain puisse modifier sa stratégie et qu’il essaie, ainsi, de vraiment gagner contre les deux intelligences.
Le message au début de la partie est neutre, ainsi il n’y a pas d’influence dans les jeux des différents humains. On remarque que les joueurs humains adoptent différentes stratégies comme essayer de jouer au hasard, essayer des répétitions jusqu’à ce qu’ils perdent et à ce moment là ils changent. Certains ont une idée du fonctionnement des algorithmes et essaient de les déstabiliser. Tous ces comportements peuvent être influencés au niveau du message du début de partie.
Nous avons eu 36 joueurs humains. Nous les avons contactés par mail (voir annexe 1).
Les résultats
Tableau 13 : Récapitulatif des données.
Joueurs Prédictions correctes
(sur les coups non aléatoires) Coups aléatoires Prédictions correctes
(sur tous les coups) Temps moyen Parties gagnées Parties nulles Parties perdues
Humain 44.15 % - 44.15 % 2.2874 s. 15.07 %
(11/73) 5.48 %
(4/73) 79.45 %
(58/73)
Prosper 55.74 % 1.97 % 55.63 % 0.0329 s. 72.97 %
(27/37) 8.11 %
(3/37) 18.92 %
(7/37)
Shannon 64.41 % 62.49 % 55.40 % 0.0262 s. 86.11 %
(31/36) 2.78 %
(1/36) 11.11 %
(4/36)

Source : http://www.grappa.univ-lille3.fr/~torre/Recherche/MRM/resultats.php
Tableau 14 : les scores moyens.
Humain Shannon Humain Prosper
Moyenne 44,63889 55,86111 44,7429 56,6286
Maximum 53 71 56 80
Minimum 29 47 25 44

On remarque qu’on retrouve les mêmes résultats en moyenne et en prédictions correctes sur tous les coups. Les performances de « Shannon » et de « Prosper » sont équivalentes. Les cinq pour cent au dessus de cinquante veulent-ils dire que dans quatre-vingt-quinze pour cent des cas l’humain ferait de l’aléatoire ?
Le temps moyen de « Shannon » et « Prosper » est très petit. Cela veut dire que sur 100 coups les calculs ne sont pas longs. Cela est intéressant pour pouvoir effectuer des parties de plus de 100 coups. « Shannon » joue soixante pour cent des coups au hasard. « Prosper » joue au hasard en début de partie (les deux pour cent) puis il joue suivant l’algorithme. Or l’algorithme lui dit de jouer au hasard par la roulette. C’est-à-dire que même s’il y a une qualité pour l’action « même » Q(s, même) valant 0.9 et qu’il y a cette même qualité mais pour l’action « différent » Q(s, différent) valant 0.3, la roulette peut faire choisir l’action « différent ». « Prosper » joue donc au hasard.


XIV.Conclusion
Plusieurs points sont mis en évidence par l’expérimentation.
Tout d’abord, l’ordre de rencontre de « Prosper » et de « Shannon » avec le joueur humain. Lorsque le joueur humain rencontre d’abord l’un des algorithmes puis l’autre son niveau de performance peut être différent. En effet, le joueur humain peut avoir mal compris la consigne et c’est lors de la deuxième série qu’il est le plus performant. Il peut également ressentir une fatigue lors de la deuxième série et développer un comportement répétitif sans s’en rendre compte. Cela peut être intéressant pour essayer de comprendre le comportement humain et développer un algorithme simulant ce comportement. Le joueur humain peut aussi être plus combatif et changer de stratégie afin de gagner contre les algorithmes. Pour observer ce comportement, le score doit être accessible au joueur.
Ensuite, la taille des parties par rapport au Q-Learning. L’expérience ne comporte que des séries de 100 coups. « Prosper » n’a pas été testé avec des parties supérieures à ces 100 coups. Donc on ne connaît rien du comportement du Q-Learning sur des parties de 500 coups ou plus.
La valeur de alpha par rapport à la taille des parties est notre troisième point. Plus les séries sont importantes et plus le alpha devait être petit afin de pouvoir observer un comportement judicieux face au joueur humain. Il est possible d’envisager un alpha grand en début de partie, afin de faire ressortir une ou quelques actions, puis de le diminuer au fur et à mesure de la partie. Alpha serait modulable en fonction des actions du joueur humain. De plus si le joueur humain change subitement de stratégie, alpha redevient important afin de pouvoir isoler ce nouveau comportement.
Le dernier point serait de tester différentes stratégies (comme la stratégie de la roulette, la stratégie gloutonne, ou encore une stratégie qui sélectionne grâce a des probabilité proportionnelle ou non) afin de voir laquelle est la meilleure. On pourrait également associer un alpha grand à la stratégie de la roulette afin d’explorer toute les possibilités, puis lorsque alpha diminue, on pourrait l’associer à une stratégie gloutonne (c'est-à-dire une stratégie qui prend la meilleure qualité de l’état à venir).
Le Q-Learning est un algorithme qui gagne contre les joueurs humains. Il est équivalent, avec les données que nous avons, à Shannon. Doit on dire que le fait de mémoriser est inutile ? La mémoire joue-t-elle un rôle important ? Et l’oubli est-il nécessaire ?