Règles du jeu

Le joueur incarne un coureur se déplaçant le long d'un parcours. Il gagne du temps, compté en minutes, en répartissant ses efforts sur chaque tronçon de ce parcours. Dès son départ, il connaît le relief de ces tronçons, relief qui est soit plat (), soit en montée (), soit en descente (). Sur chaque tronçon, il décide (quand le hasard le permet) de son allure, qui peut être soit rapide soit lente. Une allure rapide est représentée par le placement d'une boule rouge () sur le tronçon concerné. A contrario, placer une boule verte () sur un tronçon représente une allure lente. Les réserves d'énergie du coureur sont constituées de boules rouges et vertes toutes initialement dans une urne transparente. Le coureur pioche à l'aveugle dans cette urne ce qui donne autant de chance à chacune des boules d'être piochée. Le souffle d'un coureur est en général constitué de cinq boules qu'il a pioché dans l'urne. A chaque tronçon visité par le coureur, celui-ci choisi une boule de son souffle à placer sur ce tronçon pour y indiquer son allure. En particulier, si toutes les boules de son souffle sont de la même couleur, il n'a qu'une allure possible. Si l'urne n'est pas vide, il recomplète son souffle à cinq boules en piochant dans l'urne avant de choisir son allure sur le tronçon suivant. Une allure rapide sur un tronçon en montée rapporte deux minutes, sur un tronçon plat, une seule minute et aucune minute dans tous les autres cas.

Interface minimale du jeu

En haut, la ligne de boules rouges et vertes représente la composition de l'urne, sauf les boules cerclées de blanc aux extrémités qui sont celles du souffle. Au milieu, le parcours formé de pas noirs horizontaux et diagonaux se lit de gauche à droite. Les minutes gagnées apparaissent sous forme de nombres blancs au dessus des tronçons parcourus. En bas, le score contient le gain en minutes. La décision d'une allure rapide s'exprime en appuyant sur la touche "Flèche droite", une allure lente sur la touche "Flèche gauche". Les pioches dans l'urne se font automatiquement. En fin de partie, le résultat est [t]ransmis en appuyant sur la touche "t". Des affichages supplémentaires sont paramétrables en appuyant sur la touche "s". Des actions supplémentaires sont présentées en appuyant sur la touche "h". Des détails sur l'interface sont fournis après la description du protocole autour de ce jeu.

Avertissements / Données récoltées

En échange de leur éventuel divertissement, les utilisateurs anonymes acceptent de rendre disponible les données suivantes de leurs parties: login, décisions, instants de ces décisions et paramètres du jeu. La base de données collectant ces données est actuellement disponible sur le site. Nous incitons les utilisateurs à utiliser des logins suffisamment anonymes. Les mots de passes sont cryptés dans la base, mais nous vous incitons à ne pas utiliser de mot de passe sérieux, même un mot de passe très simple est accepté. En cas de succès, cette base pourrait former un corpus académique d'erreurs humaines d'optimisation que nous souhaitons (et peut-être d'autres) étudier.

Game rules

The player is a rider moving along a route. He gains time, counted in minutes, by spreading his effort on regular sections of this route. At start, he knows the terrain for each section, that is either flat (), or rising (), or falling (). On each section, when chance agrees, he chooses his speed, either fast or slow. A fast speed corresponds to the placement of a red ball () on the current section. A contrario, placing a green ball () on the current section means a slow speed. Energy savings of a rider are described by a set of red or green balls, all initially in a transparent urn. The rider blindly draws in this urn giving as many chances to each ball to be drawn. The breath of a rider is in general made up of five balls drawn from the urn. At each section visited by the rider, he chooses one ball in his breath and places it on the section defining his speed there. In particular, if all balls in his breath have the same color, he may only select one possible speed. If the urn is non-empty, he refills his breath up to five balls, drawing in the urn, before choosing his speed on next section. At fast speed on a rising section, the rider gains two minutes. At fast speed on a flat section, the rider gains only one minute. Otherwise, the rider gains no time.

Minimal user interface

At the top, the line of red and green balls forms the urn, except for the white-bordered balls that compose the breath. Just below, the route is split in sections drawn as horizontal or diagonal steps read from left to right. The gained minutes appears as white numbers on sections. At the bottom, the score contains the sum of currently gained minutes. Strike "Right Arrow" key to choose a fast speed on current section where a rider in drawn. Strike "Left Arrow" key to choose a slow speed. Draws in the urn are automatic. At the end of the game, the result is [t]ransmitted to the server hitting key "t". Additional informations may be selected hitting key "s". Help on additional actions is obtained by hitting key "h". Details on this interface will be later described in the advanced (French) or academic (English) presentation.

Warning / Collected data

In exchange of their possible entertainement, the anonymous users accept to share in our database the following data: their login, their decisions, the time of these decisions, the game's parameters. The database is currently available on the website. We encourage users to define logins that are sufficient discreet. Passwords are encrypted when stored in the database, but we encourage you not to use serious passwords and mention that we accept even the simplest passwords. In case of success, this database may be used as an academic corpus of human optimisation errors that we, and maybe others, may study.

Protocole expérimental

Nous explicitons ici nos motivations expérimentales pour créer ce site-web dans un cadre académique.

Tous des cobayes !

Commençons par feindre le contre-pied: en ces temps où renaît le phénix de l'intelligence artificielle, notre ambition est ici d'observer la stupidité (ou plus sérieusement l'erreur) humaine. Pour cela, nous avons besoin de cobayes. Comme l'évoque Robert Wurtz dans ses mémoires, le CNRS a une longue tradition d'élevage de souris pour les besoins de ses expériences (X? en 2016). Sur un ton léger, nous dirons que pour les humains, à notre connaissance, il renâcle un peu. Le titre de cette page web devrait être: "Venez à moi petites souris !" car nous vous proposons le rôle d'une de ces souris. Au risque de vous offenser, cher lecteur, vous nous semblez être une source prometteuse d'observation. Si vous le prenez mal, dites vous que les auteurs de ce site ont débuté comme il se doit par des auto-analyses et que ce n'est pas pas faute de matière qu'ils se tournent vers vous. Au lieu du morceau de fromage à la sortie du labyrinthe, nous vous incitons à vous amuser sur le jeu d'optimisation que nous venons de décrire. Vous pouvez rester anonyme quand nous récupérons vos reflexions et en proposons des analyses automatisées. De tels "jugements" peuvent aussi bien être pertinents que déplacés. Un de nos objectifs est de vous expliciter les méthodes que nous employons.

Un jeu simple à comprendre mais propice à l'erreur pour l'homme et simple à analyser pour la machine

Nous sommes informaticiens de formation et donc a priori peu légitimes à mener une telle expérience. Notre atout est selon nous d'avoir conçu un jeu d'estimation avec les qualités suivantes. Il est d'inspiration naturelle et donc simple à comprendre pour les cobayes. Il est suffisamment difficile pour que des cobayes, au moins nous, commettent des erreurs. Il reste suffisamment simple pour être dans de nombreux sens totalement résolu algorithmiquement sur un ordinateur (dont le votre). Un informaticien ou un mathématicien ne devrait pas être impressionné par les résolutions d'équations de Bellman-Ford probabilistes qui s'appuient sur la programmation dynamique pour limiter l'espace et le temps de calcul à des dimensions polynomiales. Notre ambition est d'exploiter ce confort d'analyse du jeu pour étudier comment les décisions des cobayes s'éloignent des choix qualifiés d'optimaux qui sont ici accessibles.

Spécification des données récoltées

Lors d'une partie, le cobaye est identifié par un nom d'emprunt, son login (aussi appelé nickname). Ce login est protégé par un mot de passe saisi à sa première utilisation et qui ne peut ensuite plus être modifié. A la fin de la partie, le cobaye peut choisir de transmettre sa partie à notre base de données et donc les informations suivantes :
  • L'identité du cobaye (son login)
  • Le parcours (sous la forme d'une liste de 0,1,2)
  • La taille du souffle maximal (un entier en général égal à 5)
  • La suite des couleurs des boules piochées dans l'urne (une liste de 0,1)
  • La suite des décisions prises par le joueur (une liste de 0,1)
  • L'instant du début de la partie, puis de chaque décision prise par le joueur (une liste de dates)
A partir de ces informations, on peut en produire d'autres comme le score en comparant la suite des décisions et le parcours. Nous récupérons les dates de début de partie pour observer l'évolution du comportement d'un cobaye dans le temps. Les délais entre les décisions nous servirons d'indicateur potentiel de la réflexion du joueur.

Pour l'anonymat des cobayes

Les cobayes participent à l'expérience sous un nom d'emprunt qu'ils se sont choisi, leur login. Nous vous incitons à choisir un login le plus discret possible car vos parties restent accessibles à tous dans notre base de données. En étant exagérement optimiste pour forcer le trait, ce jeu pourrait par exemple rencontrer un succès inattendu dans les services de ressources humaines de grandes compagnies, et devenir un test de recrutement, voire de prospection de talents. Prospection s'appuyant sur l'étude de notre base de données après son succès mondial. Nous ne croyons bien sûr pas à tout cela, mais nous trouvons beaucoup de bon sens dans le serment de l'analyste de données dû à Derman et Wilmott, et reproduit par O'neil dans sa conclusion de "Weapons of math destruction" que nous tentons de traduire ici:
  1. Je me souviendrai que je ne fais pas le monde et qu'il ne satisfait pas mes équations.
  2. Même si je compte utiliser audacieusement des modèles pour estimer des valeurs, je ne serai pas excessivement impressioné par les mathématiques.
  3. Je ne sacrifierai jamais la réalité à l'élégance sans expliquer pourquoi.
  4. Je ne donnerai pas aux gens qui utilisent mes modèles un faux sentiment de confort quant à leur précision. Au contraire, j'expliciterai ses hypothèses et ses omissions.
  5. J'ai conscience que mon travail peut avoir des effets gigantesques sur la société et l'économie, fréquemment au-delà de mon entendement.
Il est amusant de relire le premier point juste après le dernier. Les enjeux ici ne sont bien sûr pas les mêmes que pour l'autorisation d'un prêt immobilier ou d'une assurance santé. Toute proportion gardée, il est donc important pour vous de pouvoir par vous même garantir votre anonymat. Si plus tard, vous souhaitez fanfaronner sur vos performances, vous pourrez révéler votre mot de passe à la terre entière ou bien jouer des parties avec des contraintes arbitraires. Nous avons conscience qu'un cobaye peut facilement multiplier les logins et partager son login avec d'autres cobayes. Nous voulons simplement garantir qu'un cobaye puisse jouer avec une identité anonyme sans usurpation possible (à moins d'un effort qui n'en vaut pas la peine).

Le mariage de la compétence avec la chance

Le lecteur attentif aura remarqué que les règles ne définissent pas clairement un but du jeu au delà du slogan « le plus vite sera le mieux ». Si les pioches dans l'urne pour la récupération du souffle étaient connues dès le début de la partie, cela suffirait: gagner 13 minutes sera toujours mieux que 12. L'aléatoire de ces pioches prend donc le contrôle d'une partie des gains du joueur, qui ne s'en remet donc pas uniquement à sa compétence. La stratégie d'un joueur, aussi bonne soit elle, ne lui donne donc qu'une distribution de probabilité sur son score. Par exemple, la stratégie nommée A d'un joueur conduit à la distribution également nommée A qui donne trois chances sur dix d'un gain de 12 minutes, cinq chances sur dix à un gain de 13 minutes et deux chances sur dix à un gain de 14 minutes. Elle se note aussi d(A) := {12:3/10,13:5/10,14:2/10} ou bien par le diagramme suivant où l'aire des colonnes est proportionnelle à la probabilité de chaque gain de temps.

But(s) du jeu

Voici trois distributions de gains obtenues à partir de trois stratégies différentes:
  • d(B) := {11:9/10,14:1/10}
  • d(C) := {11:4/10;13:6/10}
  • d(D) := {12:5/10,13:5/10}
Laquelle est la meilleure parmi ces stratégies B, C et D ? Si vous ne savez pas, une fois n'est pas coutume, félicitations, vous avez la bonne réponse. Pour vous en convaincre, nous allons finir de poser le problème avec trois buts différents et chaque distribution sera la meilleure pour un des buts mais pas les autres.
  • Premier but : vous devez atteindre un gain de temps de 13 minutes pour battre un coureur qui vient de gagner 12 minutes et trente secondes.
  • Second but : vous devez maximiser votre gain de temps cumulé sur un grand nombre, par exemple infini, de parcours.
  • Troisième but : vous devez obtenir le meilleur gain de temps parmi un grand nombre, par exemple infini, d'autres coureurs identiques.

Un but naturel mais insaisissable

Le premier but est la version édulcorée d'un quatrième qui vous est peut-être venue en premier à l'esprit.
  • Quatrième but : vous devez maximiser votre probabilité de gagner le plus de temps parmi un nombre raisonnable, disons dix, de coureurs identiques.
Ce quatrième but contient une difficulté qui nous a conduit à l'écarter dans cette première approche. Connaissant les choix des autres coureurs, il est possible pour vous d'optimiser ses chances d'obtenir un gain maximal. Cependant, comme les coureurs sont dans les même conditions, ces autres coureurs prennent aussi leur décision en observant votre stratégie. Donc votre stratégie est définie à la fois avant et après celle des autres coureurs. Le paradoxe de ces observations mutuelles peut-être parfois résolu, mais à ce stade nous laissons cette question en suspens.

Optimisation du premier but : passer la barre en saut en hauteur

Pour le premier but, on cherche a maximiser la probabilité d'un gain d'au moins X minutes, donc en fait la somme S des aires des colonnes X,X+1,X+2,... Ici X=13 donc
  • S(d(B)) = 1/10 (pour 14 uniquement)
  • S(d(C)) = 6/10 (pour 13 uniquement)
  • S(d(D)) = 5/10 (pour 13 uniquement)
donc la meilleure stratégie est ici C. [TODO un contexte ou ce but est naturel (remboursement prêt immobilier)]

Optimisation du second but : le gain moyen

Pour la seconde façon, c'est le gain moyen que vous souhaitez maximiser, aussi nommé l'espérance E(d(X)) de la distribution d(X). On a
  • E(d(B)) = (9/10)*11+(1/10)*14= 11.3,
  • E(d(C))= (4/10)*11+(6/10)*13= 12.2,
  • E(d(D)) = (5/10)*12+(5/10)*13= 12.5,
donc pour ce but la meilleure stratégie est D. Ce gain est aussi celui que nous privilégierons dans notre première version de l'analyse du jeu. C'est une optimisation fréquente en économie, si vous voulez fabriquer un grand nombre d'objets identiques, le temps moyen de fabrication peut être votre objectif.

Troisième but : Optimisation pour le record de l'optimiste

Pour la troisième façon, c'est finalement un cas limite de la quatrième façon que nous nous refusions à envisager en toute généralité. Comme il y a une infinité de coureurs, il y en a une infinité qui obtiendra les meilleurs pioches possibles pour le parcours. Il peut exister plusieurs séquences de meilleurs pioches. La stratégie d'un coureur peut être de supposer qu'une séquence donnée de meilleurs pioches se réalisera pour lui, et de jouer en l'anticipant de façon optimale pour cette séquence. Pour certains de ces coureurs, une petite fraction de cette infinité qui reste une infinité, leur prédiction se réalisera et ils atteindront donc le gain de temps maximal sur ce parcours. Finalement, des coureurs atteindront le gain maximal, et donc la meilleure stratégie est en priorité de maximiser le gain atteignable, puis de maximiser cette probabilité. Nous supposons ici que les seules stratégies possibles pour les coureurs sont décrites par les trois distributions, sinon il est possible que le gain maximal ne soit atteignable par aucune de ces trois distributions qui dans ce contexte deviennent alors équivalentes car perdantes à coup sûr. Pour d(B) c'est 14, pour d(C) et d(D) ce n'est que 13 donc la meilleure stratégie est ici C. En cas d'égalité du maximum atteignable, on peut trancher entre deux distributions selon la probabilité que ce maximum soit atteint. Ainsi selon ce but la stratégie C est jugée meilleure que la stratégie D car 6 fois sur 10 elle atteint le maximum 13, alors que la stratégie D n'atteint que 5 fois sur 10 ce même maximum.

Une notion robuste de comparaison de distribution

La discussion précédent est censée avoir instillé le doute sur la comparaison de distributions de probabilité sur les grains. Il existe toutefois une comparaison partielle, certaines distributions étant incomparables, raisonnable si seul le gain final nous intéresse. La fonction de répartition F(A) d'une distribution comme d(A) est celle qui donne pour tout valeur X la probabilité que le gain soit inférieur ou égal à X. Pour les gains à valeur entières, F(A)(X) se calcule en sommant les chances de gagner X,X-1,X-2, … Par exemple pour d(A) = {12:3/10,13:5/10,14:2/10}, on a :
  • Pour X strictement inférieur à 12, F(A)(X) = 0 car le gain minimal est 12 avec la stratégie A,
  • Pour X au moins 12 et strictement moins que 12, F(A)(X) = 3/10,
  • Pour X au moins 13 et strictement moins que 13, F(A)(X) = 3/10+5/10=8/10,
  • Pour X au moins 14, F(A)(X) = 3/10+5/10+2/10 = 10/10 = 1, car le gain maximal est de 14
  • .
On peut représenter cette fonction de répartition par le graphe de fonction suivant:
La stratégie U de distribution d(U) domine fortement la stratégie V de distribution d(V) si pour tout gain X, les chances d'obtenir ce grain avec la stratégie U sont au plus celles avec la stratégie V et donc, en terme de fonction de répartition F(U)(X) est au moins F(V)(X). Autrement dit plus bas est le graphe de la fonction de répartition qui croit de 0 à 1, meilleure est la stratégie. Les distributions d(B), d(C) et d(D) des stratégies B,C et D ne sont justement pas comparables deux à deux. Cela peut se voir sur la présentation graphique des trois fonctions de répartition. F(B) est verte donc la meilleure pour des gains entre 13 et 14, F(C) est bleue et la meilleure pour des gains entre 12 et 13, F(D) est rouge (et disparaît sous la bleue F(C)) et la meilleure pour des gains entre 11 et 12.

L'optimisation retenue est celle du gain moyen

Nous choisissons pour l'instant de compléter le problème en optimisant l'espérance de la distribution. Nous gardons à l'esprit que c'est un choix discutable qui est au coeur des jugements qui seront émis.

Exemple de but du jeu portant sur plus que les gains finaux

Nous avons fait le choix de faire porter l'optimisation uniquement sur les gains finaux. Nous avons vu que c'est un choix insuffisant pour définir le but. Il faut avoir aussi que ce n'est pas une condition nécessaire pour définir un but.
Par exemple, un but pourrait être d'optimiser la somme des gains de temps finaux et à mi-parcours. Dans ce cas, les gains sont modifiés car sur la première partie du parcours, les gains comptent double (4 minutes en montée et 2 minutes sur du plat). Cela pourrait être explicitement donné dans le modèle, puisque cela s'intègre naturellement mais l'objectif est de montrer comment on peut élargir le jugement à autre chose que le gain final en observant le déroulé de toute la partie.
Un exemple un peu plus réflexif de but du jeu serait de maximiser le nombre de kilomètres où le gain moyen depuis le début du parcours est supérieur ou égal au gain moyen final. Une stratégie serait alors de faire délibérement une mauvaise fin de parcours pour que le début de partie soit meilleur. Dans ce contexte, il est a priori plus délicat d'attribuer un gain à chaque kilomètre.

Mise en équation du jeu

[TODO Etat de la partie (explosion combinatoire polynomiale et non exponentielle), Bellman Ford, Paramétrage par la fonction de comparaison des distributions]

Résolution efficace par la programmation dynamique

[TODO Ordre inverse de résolution des sous-problèmes]

Simulation de joueurs parfaits

[TODO Vous êtes le coureur 0, vous pouvez être rejoint par neuf autres joueurs parfaits] [TODO On peut observer l'influence de la chance sur les autres joueurs. + On peut avoir une distribution explicite]

Le problème de la séparation de la chance et de la compétence.

[TODO Des parties différentes en fonction des tirages. Les erreurs conduisent à des choix différents. Est ce qu'une erreur pourrait être rentable ? ...]

Premier jugement pour le divorce de la chance et de la compétence

[TODO Modèle simple basé sur la variation d'espérance durant une décision pour la compétence et durant une pioche pour la chance. Limite de cette version utilisée comme première approximation.]

Pourquoi ce jeu n'est pas un jeu de plateau

[TODO On peut jouer à ce jeu avec un matériel de type jeu de plateau. Cependant le score (de compétence) n'est pas calculable sans l'analyse fine. Ce n'est pas le déroulement du jeu qui pose problème mais l'évaluation des gains]

Une première théorie empirique de l'erreur

[TODO L'écart entre les deux espérances de gain est le bon indicateur de la difficultée du choix. Etude sur les erreurs d'un des auteurs (définition de la probabilité d'erreur, best fit...]

Génération de parcours basés sur cette première théorie

[TODO Mise en oeuvre par exploration à base de flips, générations de parcours pour différentes difficultés]

Evaluation empirique de cette première génération

[TODO Les parcours théoriquement les plus durs ne le sont pas tant que cela]

Une seconde théorie de l'erreur

[TODO Comparaisons des gains cumulé sur les deux trajectoires optimales après un choix. Distribution spatiale de deux formes de gains. Affichage possible de cette comparaison dans l'interface. (TODO: lors d'un replay, afficher ces répartitions)]

Une symétrie cachée

[TODO Aversion à la perte/ Plaisir du gain. Opportunité de le tester ici. Est ce qu'il y a un biais dans la décision du joueur ? (surestime ou sousestime t'il les gains en montée, les pertes en descente). Pourquoi peut on l'observer alors que les pertes en descentes sont nulles par définition ? (on met le doigt sur le retard de paiement des pertes en descente) Parce que ce jeu est en fait symétrique: une reformulation est de maximiser la somme des boules rouges en montée et des boules vertes en descente. Symétrie de décision: on peut faire jouer le même jeu deux fois à un joueur en le présentant différemment. Est ce que le comportement sera le même ?]

De multiples présentations équivalentes de ce jeu

[TODO La matrice 2x3 des gains à 6 coefficients et peut être paramétré par deux coefficients qui ne sont pas sur la même ligne. Cela conduits à une description par une combinaison (pas forcéement convexe) de 3 ou 6 façons de présenter les mise en paiement des gains. Est ce que certaines présentations sont meilleures que d'autres pour ajuster son apprentissage ?]

Interface détaillée du jeu

WIP