Voilà un sujet de discussion bien stérile, on en a parlé pendant des heures avec un ami,chacun campant sur sa position: pour moi le hasard existe mais l’aleatoire non, pour lui c’est le contraire !

J’expose ici ma thèse sur le hasard, pour mieux me faire comprendre on va formaliser le problème on utilisant une structure de données très puissante : le graphe.

Prouver qu’une action est du au hasard est un non-sens car il y aura toujours un lien de cause à effet ammenant à cette action, aussi je vais m’attacher à prouver que deux actions provoqués en simultané peuvent etre du au hasard.

Introduction aux graphes

Un graphe est une structure de données complexe.

On peut la définir de plusieurs manière :

• C’est un ensemble de noeuds reliés entre eux par des arcs.

• C’est un ensemble d’objets avec des relations entres eux.

• C’est un ensemble de situations reliés par des transitions.

Un graphe peut avoir de nombreuses propriétés :

• Si le nombre d’arc est beaucoup plus grand que le nombre de noeud (de l’ordre de N² ou N est le nombre de noeud) on dit que le graphe est dense voir très dense.

• Si le nombre d’arc est de l’ordre de N on dit au contraire que le graphe est creux voir très creux

• On peut ajouté une pondération aux arcs, dans ce cas on dit que le graphe est pondéré.

  Ex : Dans un graphe ou les noeuds sont des carrefours et les arcs des rues, on pourrait pondéré le graphe avec la longueur des rues, le temps qu’il faut pour la traverse…

• Le graphe peut etre orienté ou non, si il est non-orienté, un arc entre un noeud A et un noeud B implique un arc entre B et A.

Ex 1 : on reprend le graphe des carrefours et des rues, par exemple, il y a un arc entre un carrefour A et un carrefour B si on peut empruntant la rue dans ce sens(i.e . : il n’y a pas de sens interdit). Le graphe est alors orienté.

Ex 2 : toujours dans le même graphe, si on se place du point de vue d’un piéton qui n’a pas a se préoccuper des sens interdits, il peut emprunter toutes les rues dans n’importe quel sens : le graphe est alors non-orienté.

• Il y a un chemin entre un noeud A et B si il y a une suite d’arcs reliant A et B.

• Un graphe orienté est cyclique, si il existe deux noeuds A et B tel qu’il y ai un chemin entre A et B et entre B et A.

Il existe de nombreuses autres propriétés plus évolués qui ne nous intérèsse pas ici(un graphe peut être eulerien, hamiltonien, connexe, fortement connexe…)

Le graphe de causalité

Dans notre monde, on peut reconnaître des milliers et des milliers de graphe mais un me semble interressant lorsqu’on parle du hasard : On considère un graphe ou les noeuds sont des action et ou il y a un arc entre deux noeuds si il y a un lien de causalité entre ces deux noeuds.

Le graphe est orienté, non-pondéré et potentiellement très dense.

Un exemple simple :

La situation : On a un magasin equipé d’une alarme très sensible près d’une route à fort passage.

L’alarme peut se déclencher si :

• Des voleurs sont dans le magasin (il y a donc un arc de l’action « voleurs dans le magasin » vers l’action « déclenchement de l’alarme »).

• Un gros camion passe sur la route(il y a un arc de « passage de camion » vers « declenchement de l’alarme »).

a contrario :

• Le declenchement de l’alarme ne provoque pas la présence de voleurs dans le magasin ni le passage d’un camion(il n’y a donc pas d’arc de « alarme » vers « voleurs » ni de « alarme » vers « camion »).

Le hasard dans le graphe

Deux actions A et B sont du au hasard si il n’y a pas de lien de causalité entre A et B.

Autrement dit on se plaçant dans notre graphe : deux actions A et B qui sont provoqués en même temps sont du au hasard si il n’y a pas de chemin du noeud A au noeud B OU du noeud B au noeud A.

Dans notre premier graphe, le fait qu’il y ai des voleurs dans le magasin ainsi que le passage d’un gros camion est donc du au hasard

Critiques éventuelles

L’exemple présenté plus haut est volontairement pauvre, on peut imaginer qu’en élargissant le système on puisse trouver un lien de causalité entre ces actions.

Par exemple, imaginons que les voleurs ai besoin d’un gros camion pour venir sur place et emporter leur butin,le grape se transforme donc de cette manière :

Il y a un chemin entre « voleurs » et « camion », le passage d’un camion avec la présence de voleurs n’est donc plus du au hasard.

L’élargissement du système peut supprimer le hasard mais elle peut aussi le créer par exemple :

Dans ce cas la il me semble logique que le fait que je mange une pizza soit totalement independante du fait qu’il y ai des voleurs dans le magasin ^^.

On peut trouver des situations qui ne sont pas sujets à polémique, en voici une imaginé grâce a une anecdote vécu (merci Herihor ^^) : Il y a du vent aujourd’hui, nous nous réfugions donc dans la voiture et nous constatons que celle-ci est en panne, on remarque que les phares sont restés allumer, le conducrteur nous avoue alors qu’il est rentré hier soir fatigué et qu’il a probablement oublié d’eteindre ses phares tout en ajoutant qu’il ne savait pas qu’il y aurait du vent le lendemain (très important).

Le graphe :

Il ne peut pas y avoir de liens de causalité entre « vent » et « panne » puisque :

• l’origine de celle-ci est detecté

• le sujet ne savait pas qu’il y aurait du vent le lendemain, donc cela n’a pas pu le troublé au point d’oublier ses phares !

En bref : tu suxxx Herihor ^^

J’ai retrouve récemment un article du GLMF qui traitait de cette intelligence artificiel assez étonnante.

En effet Minasi bat quasi systématiquement les joueurs humains au jeu de Pierre-Papier-Ciseaux : une étude portant sur un nombre important de parties montre que Minasi ne perd pratiquement jamais sur une partie d’une centaine de coups. Je me suis empressé de coder un programme exploitant Minasi et les résultats sont la : je n’ai jamais gagné contre elle sur une vingtaine de partie en 10 points gagnant !

Le jeu Pierre-Papier-Ciseaux

Ce jeu (que j’abrégerai désormais PPC) est sans doute l’un des plus simple au monde, deux joueurs choisissent simultanément un coup parmi les trois permis : la pierre(le joueur montre alors son poing fermé), la feuille (la main a plat), et les ciseaux (l’index et le majeur formant une espèce de V). La pierre l’emporte sur les ciseaux, les ciseaux sur la feuille et cette dernière sur la pierre. Si les deux joueurs jouent le même coup, personne ne remporte de points. La partie s’arrête lorsqu’un joueur atteint un nombre de points fixé en début de partie.

D’apparence absolument pas ludique, le jeu devient intéressant si l’on pousse la réflexion un peu plus loin que « je joue au hasard et je prie pour avoir de la chance « , il existe même des championnats du monde de PPC ! Les « champions » essayent de deviner ce que va jouer l’adversaire et réagissent en conséquence, le temps de réflexion est limité et court ce qui oblige les joueurs a compter non seulement sur la stratégie mais aussi sur leur intuition. On remarque donc que le PPC est une forme simplifiée de Poker ou l’on ne garde que l’analyse du comportement du joueur (on peut retarder la divulgation de son coup pour voir les gestes esquissés par son adversaire), l’instinct, et la stratégie en occultant le stress lié a l’argent et le hasard des cartes.

Une partie de PPC analysé : la finale du championnat du monde 2003 entre Krueger et Rigaux

On va utiliser la notation anglaise pour supprimer toutes ambiguïté : R pour pierre(rock), P pour papier(paper) et S pour ciseaux (sissors).

Krueger	S	R	P	S	P	R	P
Rigaux	R	R	R	S	P	R	R

Au début de la partie, Rigaux joue un triplement pierre, imaginant que son adversaire pensera qu’il n’aura pas l’audace de jouer une troisième fois le même coup, Krueger ne se fait pas avoir et joue papier ce qui lui permet de remporter le point. Le quatrième coup est très intéressant, Krueger prends un risque en jouant ciseaux, Rigaux pouvant quadrupler pierre et ainsi gagner le point, mais Krueger pense qu’il n’en aura pas le courage, en effet il vient de perdre le point en jouant pierre… le choix des ciseaux est donc optimal : Krueger fait au pire match nul sur les 2 coups possibles de Rigaux.

Il y a deux possibilités pour analyser le coup de Rigaux, ces deux possibilités sont dépendantes du fait qu’il est perdu le point précédent et a donc un « désavantage psychologique » :

Il a pu joue le coup complètement au hasard (probable)

Il a fait la même réflexion que Krueger mais préfère ne pas risquer le quadruplement de pierre et donc s’assure le match nul.

Le reste de la partie est beaucoup plus difficile a analyser : pour le cinquième coup on pourrait imaginer que Krueger pense que Rigaux va retenter la technique du triplement avec ciseaux cette fois-ci et joue donc papier pour contrer… Je n’ai pas vraiment d’idée pour le reste et je vous laisse le soin de commenter la suite.

Le hasard et l’homme

Faites ce petit test chez vous : essayer de jouer aléatoirement à PPC et regarder le pourcentage de coup que vous avez joués(Bien entendu il ne faut pas tenter de tricher en faisant tout le temps R-P-S-R-P-S… ce n’est plus de l’aléatoire puisqu’une séquence est répétée !) .

Voici ce que j’obtiens :

Pierre	Papier	Ciseaux
28	35	37

On est quand même relativement loin de l’aléatoire théorique (33-33-34) !

L’Homme est en effet souvent incapable de comprendre la notion de hasard et a fortiori de le produire et c’est ce qu’exploite Minasi.

Minasi, ou comment détruire tout plaisir ludique

La stratégie optimale pour battre Minasi est de joue complètement au hasard mais on a vu précédemment que le hasard était incompatible avec l’homme : dommage, n’est ce pas ?

Le plaisir de jouer au jeu de PPC vient quand l’on réussit a cacher notre intention a l’adversaire ou quand, au contraire, on découvre celle de notre partenaire et on parvient a la contrer. Le problème c’est que la première source de plaisir est quasiment impossible a atteindre avec Minasi et la seconde complètement impossible ce qui détruit tout plaisir ludique, l’étonnement succède vite a la frustration et on vient a se demander si Minasi ne triche pas (c’est souvent le cas dans des jeux-vidéos comme les STR ou l’IA par exemple ne souffre pas du « brouillard de guerre »).

Minasi fonctionne pourtant d’une façon relativement simple :

• elle stocke en mémoire tout l’historique de la partie sous la forme d’une chaine de caractère du type « PrSpSrSsRp » ou les lettres en majuscules désignent les coups joués par Minasi et ceux en minuscule par le joueur humain.
• Elle va ensuite recherche la plus longue séquence de coup qui s’est déjà produit dans le passé.

  Ex : RsPpPsSrPp : Minasi cherche d’abord une séquence de longueur 1, c’est a dire est ce que ‘p’ a déjà été joué auparavant, elle en trouve une a l’indice 3 (on indice a partir de 0 en informatique). Puis elle cherche une séquence de longueur 2 c’est a dire ‘Pp’, elle en trouve une a l’indice 2. Il n’y a pas de séquence de longueur 3.

• On regarde le coup joué après la séquence repéré et on agit en conséquence.

  Ex : RsPpPsSrPp :le coup joué après la séquence est ’s’, Minasi va donc jouer R pour gagner.

• Si il y a plusieurs séquences, on compte le nombre d’occurrences des coups joués par l’Homme, on tiendra compte uniquement du plus grand.

  Ex : PpPpSrPpSpSsPp : Il y a deux séquences ‘Pp’ suivit de ‘p’ et une séquence ‘Pp’ suivit de ‘r’, Minasi choisira donc de contrer ‘p’ en jouant ‘S’

• Si il y a plusieurs coups avec le même nombre d’occurrence Minasi choisira au hasard entre ceux-ci.

Minasi est donc vulnérable en début de partie ou elle est prévisible, pour la battre au final il faut essayer de gagner un maximum de points au début : pour cela, un crayon et un bout de papier, notez l’historique des coups et réfléchissez comme elle, cela devient bien sur impossible au fur et a mesure de l’évolution de la partie…

le Code Source C++ d’un programme exploitant Minasi

En m’excusant d’avance de la saleté du code.

Show ▼

Sources :

Fabrice Rossi : « l’ordinateur peut-il lire dans votre esprit », GLMF n° 58 p.34

Article wikipedia sur le hasard