Au début des années 1980, Robert Axelrod a eu une idée géniale. Dans le cadre d’un dilemme du prisonnier répété 200 fois, il a proposé à celles et ceux qui le voulaient de soumettre l’algorithme qui leur semblait le plus capable de maximiser les gains du joueur.

Le principe est le suivant : à chaque itération, deux joueurs (ici Rouge et Bleue) ont le choix entre coopérer ou faire défaut. Sachant que :

  • S’ils coopèrent tous les deux, ils gagnent $R = 3$ chacun,
  • Si l’un des deux coopère mais l’autre fait défaut, celui qui coopère gagne $S = 0$ tandis que celui qui a fait défaut gagne $T = 5$,
  • Si les deux font défaut, ils gagnent tous les deux $P = 1$.

Un dessin vaut mieux qu’un long discours :

Si vous considérez ce problème, vous verrez facilement que, sur un match de 200 rounds, le pire résultat possible pour un algorithme c’est 0. C’est ce qui arriverait à un algorithme qui coopère systématiquement s’il tombait face à un algorithme qui fait systématiquement défaut : il gagnerait 200 fois $S = 0$. Symétriquement, le meilleur résultat possible, c’est 1 000. C’est celui, dans la même hypothèse que précédemment, de l’algorithme qui fait systématiquement défaut face à celui qui coopère tout le temps : il gagne 200 fois $T = 5$.

Plus raisonnablement, on peut considérer que les résultats devraient se situer entre 200 et 600. La borne basse correspond aux gains de deux algorithmes qui font systématiquement défaut : ils gagneraient 200 fois $P = 1$, soit 200 chacun. La borne haute c’est le résultat de la rencontre de deux algorithmes qui coopèrent tout le temps : ça leur ferait 200 fois $R = 3$, soit 600 chacun.

À l’époque de la simulation d’Axerod, l’algorithme le plus performant était aussi un des plus simples : c’était le « donnant-donnant » (Tit-For-Tat, TFT) d’Anatol Rapoport. Son principe est des plus basiques : au premier round, il coopère systématiquement puis, il se contente de reproduire le dernier coup de son adversaire. Si l’adversaire a coopéré au coup précédent il coopère, sinon il le punit en faisant défaut à son tour. Confronté aux autres logarithmes, TFT arrivait largement en tête avec un score moyen de 504.

Nous vous proposons de reproduire l’expérience d’Axelrod en programmant votre propres algorithmes. Votre mission, si vous l’acceptez, consiste à trouver le programme qui, en réutilisant le cadre proposé en 1980, aura l’espérance de gain la plus élevée quand il est confronté aux autres.

Si vous souhaitez participer, le règlement du tournois est ici. Nous recevrons vos propositions jusqu’au le vendredi 23 juin 2017 à minuit (heure de Paris).