« Quel est le classement de Dieu ? » me demande Ken Regan, alors qu’il me conduit en bas des escaliers menant au sous-sol de sa maison de Buffalo, dans l’État de New York. Dehors, le froid point par cette matinée couverte de la fin du mois de mai 2013. Ici, la lumière du soleil pénètre par deux fenêtres proches du plafond, comme si cet emplacement sur Terre jouissait d’un lien direct avec le paradis. Sur une étagère à proximité, des vieilles boîtes de jeux sont empilées : Monopoly, Parcheesi, Life, parmi d’autres souvenirs d’enfance des deux adolescents de Regan. Juste à côté de l’étagère se trouve une table surmontée d’un ordinateur portable connecté au système Unix du Département d’informatique et d’ingénierie de l’Université de Buffalo, là où Regan exerce son métier de professeur associé à temps plein.

L’ordinateur portable gère quatre invocations de son logiciel anti-fraude dédié au jeu d’échecs, qui surveille actuellement les parties du championnat du monde de blitz. Ce logiciel utilise un moteur de jeu d’échecs code source appelé Stockfish, l’une des plus puissantes entités jouant aux échecs sur la planète. En continu et en temps réel, cet ordinateur portable compile des données de référence essentielles pour les algorithmes de Regan. Regan et moi prenons la direction de son bureau, où il prévoit de m’expliquer son travail en détail.

L’ordinateur portable n’a pas chômé. Regan décortique chaque étape du travail, puis presse quelques touches. Ce qu’il observe sur l’écran l’amène à reformuler sa question, mais cette fois-ci, sans attendre de réponse de ma part. « Quel score représente la partie parfaite ? » me demande-t-il. « Mon programme dit que c’est 3 600 points. Avec ces moteurs à 3 200, 3 300, on s’en approche… » Dans le code de Regan, le moteur de jeu d’échecs doit jouer le rôle d’une intelligence artificielle omnisciente qui classe et évalue de façon objective, mieux que n’importe quel humain, n’importe quel coup réglementaire dans une position donnée. En d’autres termes, le moteur doit faire jeu égal avec Dieu.

Le Jeu des Rois

Un Internet omniprésent combiné à des systèmes de communication sans fil de la taille d’un bouton de chemise et des programmes pouvant facilement balayer un champion du monde renforcent plus que jamais la tentation d’avoir recours à une assistance high-tech pour jauger les parties d’échecs. Selon Regan, on a enregistré depuis 2006 une inquiétante augmentation des cas de fraudes à travers le monde. Aujourd’hui la fréquence frôle approximativement un cas par mois, impliquant généralement des adolescents. Les réglementations anti-fraude en cours de la Fédération internationale des échecs (FIDE) sont trop anciennes pour comporter une section sur l’assistance informatique non-autorisée. Ainsi, Regan se charge lui-même de surveiller la plupart des événements majeurs en temps réel, y compris publics, et quand l’organisateur d’un tournoi devient suspicieux pour une raison ou une autre et souhaite intervenir, Regan est la première personne à appeler.

Regan est un fervent chrétien. Sa foi lui a insufflé une responsabilité morale et sociale pour combattre la fraude dans le monde des échecs, une responsabilité qui s’est muée en appel. En tant que maître international, et, comme il se décrit lui-même, professeur d’informatique de niveau 2 600 avec un passif en théorie complexe – il est titulaire de deux maîtrises de mathématiques, d’un bachelor à Princeton et d’un doctorat à Oxford –, il apparaît aussi comme l’une des rares personnes au monde ayant la capacité de lancer un tel appel. « Sur Terre, Ken Regan fait partie des deux ou trois personnes ayant le bagage suffisant, l’expertise des échecs et les talents informatiques nécessaires pour développer des algorithmes anti-fraude susceptibles de fonctionner », dit Mark Glickman, professeur de statistiques à l’Université de Boston et titulaire d’une chaire au sein du comité de notation de la Fédération américaine des échecs (USCF). Chaque fois que Regan lance une instance de son code anti-fraude, il ne fait pas que lancer une fonction du logiciel – il l’invoque. Le double sens d’ « invoquer » est à la source de la relation inspiratrice qui guide son travail anti-fraude.

Le forfait de Kramnik à la cinquième partie n’a pas seulement menacé la réunification, mais aussi le futur de ce sport.

Sa tâche a commencé le 29 septembre 2006, durant le match de championnat du monde entre Topalov et Kramnik. Vladimir Kramnik venait alors de déclarer forfait à la cinquième partie pour protester contre les accusations de l’équipe de Topalov qui affirmait qu’il consultait un programme d’échecs durant ses passages dans sa salle de bain personnelle. Il s’agissait alors du match de la réunification pour unir deux champions du monde, une situation qui durait depuis que Garry Kasparov et Nigel Short avaient quitté la FIDE en 1993. Topalov était qualifié pour la rencontre de 2006 en tant que tenant du titre de la FIDE. Kramnik, parce qu’il avait défait Garry Kasparov en 2000 pour prendre sa place au sein de cette auguste lignée. À la suite de ce schisme, les échecs ont enduré 13 ans de lourd déclin en termes de sponsoring, de stabilité et de réputation. Le forfait de Kramnik à la cinquième partie n’a pas seulement menacé la réunification, mais aussi le futur de ce sport.

Kramnik accepta de jouer la sixième partie, qui finit par une égalité. Après la sixième partie, le 4 octobre, l’équipe de Topalov publia une note controversée dans la presse pour tenter de prouver leurs allégations précédentes. Le manager de Topalov, Silvio Danailov, écrivit dans cette note :
« Nous aimerions attirer votre attention sur la coïncidence statistique entre les mouvements de GM Kramnik et les recommandations du logiciel d’échecs Fritz 9. » La note pointait la fréquence à laquelle les mouvements de Kramnik lors des première, deuxième, troisième, quatrième et sixième parties correspondaient à la première ligne de Fritz.

Une guerre en ligne éclata entre les experts qui prirent la preuve de Danailov au sérieux, contre ceux, comme Regan, qui insistèrent sur le fait qu’une méthode statistique valide pour détecter une assistance informatique n’existait pas encore. Pour la première fois, un scandale autour de la fraude éclatait dans le monde des échecs de haut niveau. Il restait plusieurs zones d’ombres : combien de temps fallait-il à Fritz pour calculer chaque coup ? Combien de mouvements imposés furent joués ? Le programme fonctionnait-il en single-line ou en multi-line (en mode multi-line les machines jouent plus lentement mais plus efficacement, car elles utilisent des heuristiques supplémentaires et proposent un éventail moindre de coups non gagnants) ? Qu’est-ce qui constituait un pourcentage concordant typique dans le jeu d’un super-grand maître ? Toutes sortes de questions qui faisaient obstacle au développement scientifique de l’accusation de Danailov. En quelques semaines, la grande menace existentielle pour les échecs passait d’une combinaison de mauvais choix politiques et d’un manque de soutien financier à quelque chose de potentiellement plus sinistre : l’ignorance scientifique. Dans l’esprit de Regan, cette menace semblait trop imminente pour être ignorée. « Je me soucie des échecs », me dit-il. « Je me suis senti appelé pour faire ce travail quand il semblait que le monde des échecs allait s’effondrer. »

The Chess Game
Sofonisba Anguissola, 1555

Regan, satisfait de la collecte de données de l’ordinateur, me guide hors de son sous-sol, jusqu’au bout de son allée où il m’indique une maison voisine au fond du quartier. Le frère du voisin de Regan se trouve être un ami du lycée avec lequel Regan a parcouru l’Angleterre avant d’étudier à Oxford, et avec lequel Regan a passé beaucoup de temps durant son année sabbatique à l’Université de Montréal. (Cet ami est professeur à McGill.) Regan adore pointer les connexions et les coïncidences qui traversent sa vie, et à mesure que sa foi infuse son sens moral dans son travail anti-fraude et que sa passion pour les échecs et les mathématiques infuse son sens technique, sa fascination pour les coïncidences infuse sa propre direction de façon étrange. « La théorie des réseaux sociaux est intéressante », me dit-il. « La fraude, c’est une question de fréquence d’apparition des coïncidences dans le monde des échecs. »

Dans la Honda Accord de Regan, nous parlons de la façon dont son travail sur les échecs a fait germer des idées sans lien avec les échecs : comment utiliser les ordinateurs pour préparer des cours massifs disponibles en ligne, comment penser l’économie du futur. Tyler Cowen, ami d’enfance de Regan et professeur à l’Université George Mason, est l’auteur de Average is Over, publié en 2013. Cowen consacre un chapitre avec des prédictions inspirées des recherches de Regan. Cowen rapporte dans quelle mesure les équipes mixtes (humain et ordinateur) jouent mieux que des ordinateurs seuls, et défend que l’économie future reposera sur des équipes humain-ordinateur de haut niveau dans chaque aspect de la société. Regan est fier d’occuper une telle place dans le livre de son ami.

Le hasard affecte chaque aspect de la vie de Regan. Son portefeuille déborde de morceaux de papier sur lesquels sont notés des noms, des numéros, des mémentos. Il ne possède pas de smartphone. Quand on entre dans son bureau, des cartons encore fermés pavent le sol. La moindre aspérité, la moindre étagère de son espace de travail déborde de papiers, de piles de livres, de carnets de notes. On relève un vieil écran d’ordinateur, une radio des années 1990, et des caisses de lait remplies de papillons éphémères. Quelques mois plus tôt, Regan a déménagé dans un nouveau bâtiment construit par l’Université et explique qu’il n’a pas eu le temps de déballer ses affaires. Un espace propre pouvant contenir deux plateaux à café héberge un écran et un clavier. Dans un autre petit espace rangé, malicieusement placé en face de nous, repose le seul objet de la pièce qui, à l’exception de l’équipement informatique, semble avoir reçu l’attention de Regan : un portrait encadré de sa femme. Un onglet du navigateur de son ordinateur est ouvert sur un site de baseball, un sport qu’il adore. Il était en train de regarder les playoffs de 2006 quand, tout en étant connecté sur playchess.com, un serveur de jeu d’échecs en ligne, il entendit parler du forfait de Kramnik.

Regan porte en lui, de manière inconsciente, cette responsabilité de faire pour les échecs professionnels ce que la chasse aux stéroïdes a été pour le baseball professionnel. Le rapport Mitchell fut commandé en 2006 pour enquêter sur les abus de produits dopants dans les ligues majeures, à peu près quand Regan a commencé son travail anti-fraude. Quand le baseball est entré dans son ère post-produits dopants, la FIDE venait juste de mettre en place un équivalent, la régulation pour les systèmes d’amélioration de performances. Ce n’est qu’à partir du milieu de l’année 2013 que l’ACP (Association of Chess Professionnals) et la FIDE ont organisé un comité mixte anti-fraude, dont Regan est un membre éminent. À l’issue du deuxième trimestre de 2014, le comité envisageait de ratifier un protocole pour soupeser les preuves et appliquer une sanction.

Regan fait quelques clics avec sa souris puis tourne son écran pour que je puisse voir les résultats de son test sur la ligue allemande d’échecs. Son visage affiche une moue de dégoût. « Encore une fois, il n’y a pas de preuves physiques, pas de preuves comportementales », me dit-il. « Je regarde seulement les chiffres. Je vais te dire, des gens sont en train de frauder. » Regan a 53 ans. Ses cheveux sont devenus blancs. Ceux qui restent ondulent au-dessus de son crâne en touffes sauvages qui lui donnent l’air d’un professeur. Quand Regan prend un air surpris, ses épais sourcils couleur jais se soulèvent comme de petits boomerangs, une réminiscence de sa jeunesse. Son enthousiasme pour le travail ne décroit jamais ; sa voix change simplement sa façon de transmettre son érudition, le faisant sonner comme un professeur.

Pour attraper un fraudeur présumé, Regan prend un ensemble de positions – idéalement 200 ou plus mais son analyse peut fonctionner avec 20 – jouées par un joueur et traite chacune d’entre elles comme un QCM. Le résultat de cette étude se convertit en classement Elo, résultat que Regan intitule « Classement de performances intrinsèques ». Il y a, bien entendu, trois différences principales entre un QCM standard et l’examen anti-fraude de Regan. Premièrement, dans un QCM, chaque question possède un nombre fixe de réponses, généralement quatre ou cinq ; dans l’examen de Regan le nombre de réponses par position correspond au nombre de coups autorisés. Deuxièmement, dans un examen standard, une réponse par question donne autant de points, alors que les autres réponses ne valent aucun point ; dans l’examen de Regan le nombre de points pour chaque coup est défini par l’ordinateur, en fonction du classement qu’il a établi. (Un crédit partiel dépend d’une relation non-linéaire complexe basée sur les évaluations du moteur. Ce crédit est aussi contraint au fait que pour une position, la somme de tous les coups est égale au crédit maximal.)

La troisième différence est la méthode de notation (voir schéma 1). Un QCM d’examen standard est noté en divisant le nombre de réponses justes par le nombre de questions. Pour 25 questions, si un étudiant répond correctement à 22 questions et faux à trois questions, alors le résultat équivaut à empiler 22 points à l’emplacement 1 et trois points à l’emplacement 0. Le nombre 0.85 représente l’emplacement moyen ou « ajusté » qui équivaut au résultat/score total de l’étudiant. Ceci aboutit à un pourcentage, qui devient une note arbitraire comme A, B-, C+, etc. [comme le veut le système de notation américain, NDE]. Ce qui importe n’est pas seulement le pourcentage mais comment la personne interprète ce pourcentage. Si un examen s’avère être particulièrement difficile et que beaucoup d’étudiants obtiennent un mauvais résultat, alors un résultat de 85 % pourrait devenir un A au lieu d’un B plus trivial. Ce que l’on appelle noter selon la courbe.

Le schéma numéro 2 illustre la relation conceptuelle entre les coups choisis par un joueur déterminant un ensemble de positions et comment le moteur peut distribuer les crédits partiels. Chaque point représente un coup. Les bons coups tendent vers le coin supérieur gauche du graphique, tandis que les mauvais tendent vers le coin inférieur droit. Étant donné que les bons joueurs et les grands maîtres jouent tous les deux de mauvais coups comparativement à un moteur, tous les graphiques représentant des humains tendent à adopter une forme en « L ». Cette méthode de conversion de l’évaluation d’une machine en crédit partiel objectif est l’aspect original du travail de Regan. Il l’appelle « Conversion des données en probabilités ». (Regan utilise le terme technique de « probabilité » au lieu de « crédit partiel », car après que les crédits partiels sont soumis à une contrainte – leur somme doit être égale au total des crédits –, ils doivent mathématiquement se convertir en probabilités.) « Je l’ai inventé », me dit-il. « En vérité, j’ai été stupéfait de constater que rien n’avait été écrit à ce sujet. J’étais persuadé que quelqu’un s’était déjà attaqué au problème. »

Les recherches de Regan en littérature ont nourri son penchant pour les coïncidences. En tant que fervent chrétien, on lui demande parfois s’il croit en la théorie de l’évolution, ce à quoi il acquiesce. « Les travaux sur le dessein intelligent concernent une part importante de mes recherches en littérature. Il n’y a pas de lien direct avec mon travail, mais certains ingrédients mathématiques sont les mêmes. » Le dessein intelligent guide le théoricien de la complexité William Dembski, et Regan fait remarquer que le mari de l’ancienne colocataire de sa femme est Robert Sloan, détenteur d’une chaire au département de science informatique de l’Université de l’Illinois, à Chicago, où Dembski a obtenu son doctorat.

Dans les algorithmes de Regan, c’est la différence relative entre la qualité des coups qui importe, et non pas la différence absolue. Admettons, par exemple, que les trois meilleurs coups d’un candidat soient notés par le moteur comme différant très légèrement, alors ces coups vaudront chacun approximativement 30 % de crédit (les 10 % restants se répartissant sur les autres coups possibles). Cette accentuation sur la différence relative plutôt que sur la valeur absolue explique pourquoi les fraudeurs qui utilisent des mouvements qui ne sont pas toujours les premiers choix du moteur se feront toujours attraper. Cela explique aussi pourquoi il n’est pas possible pour un crédit partiel d’être plus élevé face à des adversaires plus faibles.

Ajustement idéal

Après que les crédits partiels d’un joueur ont été placés sur une représentation pour un ensemble de positions, Regan crée une représentation graphique du résultat en dessinant une courbe à partir des données (voir schéma 3). (En jargon statistique, ce processus constitue la « Méthode des moindres carrés ».) Le résultat d’un QCM standard peut aussi être vu comme un ajustement idéal, mais dans ce cas-là le meilleur ajustement est calculé entre les points 0 et 1 d’un axe horizontal plutôt qu’entre de multiples points sur un graphique en deux dimensions (voir schéma 1). L’ajustement idéal donne une courbe (nommée « y » sur le schéma 3) et deux valeurs,
« s » et « c », qui caractérisent la courbure de celle-ci. Regan nomme « s » la sensibilité. Elle oriente la courbe vers la droite et la gauche et est indexée sur la capacité du joueur à effectuer des mouvements avec une petite différence de qualité. Regan nomme « c » la consistance, elle amincit ou épaissit la queue de la courbe. Un « c » élevé représente la capacité du joueur à éviter les erreurs grossières (« grossier » étant relatif à l’interprétation de la machine).

Regan a découvert que les valeurs différentes de « s » et de « c » se traduisent dans des catégories bien définies qui correspondent à des classements Elo, de la même manière qu’un 95 % et un 85 % à un examen se traduisent habituellement et respectivement par un A et un B. Dans les années 1970, quand Arpad Elo a conçu les systèmes de notation de l’USCG et de la FIDE, il a choisi arbitrairement que 2 000 correspondrait à expert, 2 200 à maître, etc. Cette distinction arbitraire signifie que les notations aux échecs sont basées sur une courbe, et que les valeurs spécifiques de
« s » et « c » peuvent être attribuées directement à un Elo spécifique. Cette notation particulière représente l’IPR, le Classement de performances intrinsèques.

L’IPR et le score-z sont deux résultats différents qui sont issus du même test, mais le score-z s’avère plus fiable. Si Regan évaluait un IPR avec seulement quelques coups, cela reviendrait à noter un examen avec très peu de questions. Ce qui se traduirait par une notation très peu crédible. Le score-z, cependant, est plus précis. « L’IPR n’a pas une précision scientifique », dit Regan. « Mais le score-z du test anti-fraude repose sur des réglages de l’étude de 8 500 coups issus de parties du championnat du monde. » Ces coups agissent comme les questions que le jury d’examinateurs utilise pour normaliser sa notation lors d’un examen standard. Par exemple, si le jury veut attraper un fraudeur au SAT [test américain d’admission à l’université, NDE], il peut le faire facilement en examinant un petit échantillon de réponses suspectes à des questions définies comme difficiles. Les fraudeurs répondront étrangement juste à ce genre de questions. Le même drapeau rouge se lève quand un joueur d’échecs fraudeur reçoit constamment plus de crédits partiels par coup par rapport à ce que son Elo prédirait.

Étant donné que la construction de preuves statistiques contre des fraudeurs avérés requiert un haut degré d’expertise technique, Regan pense qu’il est nécessaire d’établir une autorité centrale responsable de l’administration du protocole anti-fraude. Regan rêverait de superviser la conversion de ses 35 000 lignes de code C++ en un programme Windows ou une application portable. « Je vois d’autres personnes utiliser ma méthode mais pas forcément mon programme », dit-il. Regan pense aussi qu’une autorité centrale pourrait être à même de mettre fin à la confusion publique entre ce qui constitue une procédure scientifique et ce qui ne l’est pas. Il est trop facile pour les gens avec peu de méthodologie de répandre des rumeurs en ligne.

La preuve statistique ne craint pas la dissimulation. Peu importe la ruse d’un fraudeur (…), les véritables mouvements du fraudeur ne peuvent être cachés.

L’affaire de fraude la plus connue du public est celle du Bulgare Borislav Ivanov. Âgé de 26 ans à l’époque, il fut d’abord accusé d’avoir eu recours à un appui informatique en décembre 2012 lors de l’Open de Zadar en Croatie. S’étant hissé avec peine au niveau 2 200, il gagna six matches sur neuf dans la catégorie Open, incluant des victoires sur quatre grands maîtres. Il aurait également fraudé au moins lors de trois opens précédents. Il fut finalement disqualifié de l’Open de Bladoevgrad en octobre 2013 et de l’Open de Navalmoral de la Mata en décembre 2013, dans les deux cas après avoir refusé une inspection de ses chaussures, où il avait supposément caché un système de communication sans fil.

L’affaire Ivanov fut largement médiatisée dans les médias bulgares et sur le site d’informations chessbase.com, qui invita des blogueurs amateurs et des aficionados de YouTube à poster leur propre analyse, mais aucune ne fut suffisamment sérieuse pour persuader la Fédération bulgare d’intervenir. Cependant, l’analyse de Regan montra que les coups d’Ivanov valaient un score-z de 5.09. La possibilité qu’il ait trouvé ses coups par lui-même était d’une chance sur cinq millions. La preuve statistique de Regan couplée au refus d’Ivanov de se soumettre à la fouille déboucha sur une suspension d’Ivanov de quatre mois par la Fédération bulgare.

La preuve statistique ne craint pas la dissimulation. Peu importe la ruse d’un fraudeur pour communiquer avec ses collaborateurs, peu importe la petitesse des systèmes de communications, les véritables mouvements du fraudeur ne peuvent être cachés.

Malgré tout, des anomalies sans lien avec la fraude se produisent de temps en temps, conduisant à de faux résultats positifs. Dans chaque grand tournoi comprenant au moins une centaine de joueurs ne fraudant pas, les chances sont très élevées pour que l’un de ces honnêtes joueurs obtienne un score-z de 3.0 ou plus, valeurs ostensiblement suspectes. Tamal Biswas, l’un des deux étudiants diplômés de Regan et joueur de classe A, a utilisé une base de données de parties précédemment jouées pour simuler de grands tournois et vérifier ces chiffres.

À l’été 2014, le comité anti-fraude ACP-FIDE espère calculer les détails logistiques relatifs au nombre et combinaisons de preuves statistiques, physiques et comportementales tangibles si un supposé fraudeur n’est pas pris en flagrant délit. Regan propose le score-z de 5.0 (le seuil de la probabilité d’une découverte scientifique) ou alors plusieurs occurrences de score-z légèrement inférieurs devraient suffire pour constituer des preuves statistiques par elles-mêmes. Mais dans d’autres cas, il faudrait utiliser une preuve comportementale ou physique, comme un comportement suspect en salle de repos/détente ou dans la salle de tournoi.

Regan fut un jeune prodige des échecs durant les années 1960 et le début des années 1970, à Paramus, dans le New Jersey, à quelques kilomètres de New York. La région regorgeait de possibilités en matière d’échecs, et en 1973, à l’âge de 13 ans, Regan remporta le titre de maître. Il était alors le plus jeune Américain depuis Bobby Fischer à y parvenir. Une photographie de cette époque nous montre un Regan au visage de petit garçon rond et aux épais sourcils bruns qu’il arbore encore à ce jour.

Équivalence théorique

Mais avant que Regan ne termine le lycée, les mathématiques s’avérèrent trop séduisantes, et il décida de ne pas poursuivre sa carrière de joueur d’échecs. Ses deux derniers triomphes en compétition eurent lieu en 1976, quand il fut le seul joueur non-soviétique à gagner une médaille d’or aux Olympiades d’échecs pour étudiants, aujourd’hui disparues, puis en 1977 avec sa victoire ex-æquo au championnat américain junior. Après l’obtention de ses diplômes à Princeton et Oxford, ainsi que son post-doctorat à Cornell, Regan fut embauché par l’Université de Buffalo en 1989, où il n’a jamais cessé de travailler ensuite. Des années 1990 à 2006, Regan ne fit guère cas des échecs. Ses enfants étaient jeunes, et il s’immergeait alors dans l’étude du problème P = NP, le Graal des problèmes de sciences informatiques. Désormais, il « mène trois vies » comme il aime à le dire : ses travaux de recherche et d’enseignement, son travail anti-fraude, ainsi que la co-rédaction (avec Richard J. Lipton) du blog Gödel’s Lost Letter and P=NP. En décembre 2013, Springer publia un ouvrage que Regan co-rédigea avec Lipton à propos du blog, intitulé People, Problems, and Proofs.

Sur le blog sont publiés non seulement des articles techniques mais aussi des apartés offrant une certaine matière à réflexion concernant de drôles de coïncidences. Selon Regan, « Scott Aaronson [professeur au MIT, Institut de Technologie du Massachusetts, NDA] paria 100 000 dollars sur le fait que des calculateurs quantiques évolutifs pouvaient être mis au point. Les médias l’ont relevé. L’impulsion derrière son pari est à chercher dans mon message intitulé “Mouvement perpétuel du XXI^e siècle”. Mon message fut édité par Lipton. Lipton, Lance Fortnow et moi-même avons co-écrit quelques articles au début des années 1990, et Fortnow co-écrit son propre blog avec Bill Gasarch ; Bill Gasarch est un ami et également un confident, car il est également chrétien. » Regan est du genre à broder, et on peut se demander si ses relations personnelles ne lui coûtent pas plus d’énergie que ses études et son travail de recherche.

P = NP signifie temps polynomial contre temps polynomial non-déterministe. Un problème de type P requiert relativement peu de calculs, comme les solutions du jeu de morpion ou du jeu de dames en 64 cases. Les calculs des problèmes de type NP se cumulent extrêmement vite au contraire, trop vite pour trouver une solution basée sur les théories actuelles informatiques (un exemple pourrait être celui du problème du commercial itinérant, dans lequel le but est de calculer le chemin le plus court reliant un grand nombre de villes). Le travail de Regan comprend des méthodes de réduction du nombre de calculs nécessaires dans un problème de type NP, afin qu’il se comporte plus comme un type P.

Benjamin Franklin disputant une partie d’échecs
Edward Harrison May, 1867

Si Regan parvenait à prouver l’équivalence théorique de problèmes de types P et NP – la signification du P = NP dans son blog étant malheureusement improbable, non pas à cause de déficiences techniques de la part de Regan mais bien plutôt parce que le consensus général en la matière veut que la relation soit erronée –, les résultats pourraient alors bien changer le monde : les techniques de cryptographie deviendraient obsolètes, des traductions linguistiques parfaites, des algorithmes de reconnaissance faciale seraient possibles, et un bond incroyable serait effectué dans le domaine de l’intelligence artificielle. À juste titre, une telle découverte lui vaudrait la fameuse Prime Millennium d’un million de dollars.

La résolution des échecs n’est pas définie en tant que problème de type NP (bien que ce soit le cas de certaines variantes sur des échiquiers de plus de 64 cases), mais elle en partage deux caractéristiques : un, il est pratiquement impossible de prouver une solution – par exemple, de prouver une victoire ou un nul pour les blancs d’après la position initiale ; deux, nous pouvons rapidement vérifier une solution – qu’une position particulière soit échec et mat ou pas. La différence majeure entre les échecs et les problèmes de type NP réside dans le fait qu’une solution aux échecs est théoriquement possible, tandis que des solutions aux problèmes de type NP ne le sont actuellement pas. D’une certaine manière, les échecs peuvent toutefois être considérés comme plus difficiles que les problèmes de type NP, parce qu’avec ces derniers on peut théoriquement vérifier une solution dès le départ, si elle existe. Pour trouver une solution aux échecs, on ne peut que s’enfoncer dans une suite de calculs.

Dans son célèbre article « Programmer un ordinateur pour jouer aux échecs », le fondateur de la théorie de l’information Claude Shannon estimait le nombre de positions uniques aux échecs à 10⁴³. « Il est impossible de dévoiler l’ensemble des possibilités du jeu », dit Regan. « Elles sont si étendues que si chacune de ces unités était placée dans un appareil de stockage efficace de la taille d’une salle, cette salle disparaîtrait dans un trou noir. » Regan classe les échecs dans la catégorie des « problèmes profonds », « où l’on peut décrire l’ensemble complet des règles avec peu d’informations, mais où le décorticage de l’information peut prendre très longtemps ».

Les moteurs d’échecs continuent de s’améliorer d’environ 20 points Elo chaque année. Si l’estimation de Regan selon laquelle la partie parfaite se situe à 3 600 points est avérée, on y parviendra alors d’ici quelques décennies. Regan croit que les moteurs y parviennent déjà de manière occasionnelle, si on leur laisse suffisamment le temps de réfléchir. Un programme d’échecs muni d’un algorithme suffisamment bon et d’un processeur suffisamment rapide n’a pas besoin de stocker 10⁴³ positions pour jouer avec la même efficacité qu’un ordinateur le nécessitant. Pour comprendre comment une telle prouesse est possible, considérons comment il est possible à un être humain de parfaitement jouer au morpion sans avoir à emmagasiner toutes les solutions possibles du jeu. Il y a 256 168 variations possibles au jeu du morpion, mais un peu de jugeote permet de réduire le nombre à 230 positions d’importance stratégique.

En septembre 2013, l’université d’Harvard accueillit le colloque d’une journée sur les Statistiques dans le sport pour la Nouvelle-Angleterre, et Regan décida d’y faire un saut en revenant d’une autre conférence. Quelques semaines avant l’événement, il m’écrivait qu’il « ne cherchait pas forcément à aller faire des discours si ce n’est pour frayer avec les gens et leur tenir la jambe ». Nous nous étions retrouvés au bar du Grafton Street Pub, un restaurant plein à craquer près d’Harvard Square, pendant la pause du colloque. Le vacarme du samedi soir couvrait les discussions, et je trouvais Regan tendant l’oreille afin d’écouter Eric Van, un statisticien quinquagénaire qui fut consultant pour les Boston Red Sox entre 2005 et 2009. Van lui expliquait pourquoi les Sox avaient eu besoin de revoir leur composition d’équipe pour gagner les World Series, un but que Van permit à l’équipe d’atteindre en 2007, puis encore une fois un mois après cette petite discussion. Regan avait assisté à la conférence pour étendre son réseau, et le lien que Van entretenait avec le monde du baseball avait tout pour lui plaire.

Mais durant toute cette scène du bar, le langage corporel de Regan trahit toutefois une certaine anxiété. Il cligne parfois des yeux sans s’arrêter et mâche son chewing-gum avec énergie. (« Ce sont les échecs qui m’ont permis de me sentir à l’aise dans un monde d’adultes », m’expliqua-t-il plus tard. « J’étais ainsi capable de me jeter à l’eau dès ma première année à Oxford et de me sentir en confiance. » C’est également durant cette époque à Oxford que Regan rencontra sa femme.) Regan offrit de payer une tournée, d’une voix qui laissait paraître qu’il n’en avait pas forcément l’habitude mais qu’il considérait comme la chose à faire. Personne n’accepta. Il proposa alors de partager une pizza, et on se déplaça dans un coin plus tranquille.

Joueurs d’échecs égyptiens
Lawrence Alma-Tadema, 1865

Van lutte contre des troubles du déficit de l’attention, et contre la narcolepsie. Il officie désormais en tant que chercheur indépendant, étudiant ces maladies, ainsi que la théorie de la conscience. La conversation en vint aux relations entre science cognitive et jeu d’échecs, ce qui mena naturellement à une discussion relative à l’expérience hypothétique de la chambre chinoise, développée par le philosophe John Searle. Cette expérience propose d’asseoir une personne anglophone dans une pièce fermée à clé. Après qu’une question écrite en chinois soit glissée sous la porte, la personne doit suivre une série de règles décrivant la manière d’écrire une réponse en chinois. Cette personne glisse alors sa réponse sous la porte. Pour les gens en dehors de la pièce, il semblerait alors qu’un sinophone éduqué et authentique leur a répondu, de la même manière qu’un programme d’échecs peut dissimuler un mini super-grand maître. Searle développait l’idée que quand la personne anglophone (ou bien l’ordinateur) suit une série d’instructions afin de traduire une langue, peu importe avec quelle réussite, elle ne comprend pas la langue de la même manière qu’un locuteur natif. Le même scepticisme peut être appliqué à la question de la compréhension des échecs par un ordinateur.

Des 1 et des 0

Les échecs ont souvent été considérés comme une forme de langage, et quand j’argue que les programmes d’échecs d’aujourd’hui s’approchent de la perfection en suivant une série de règles inscrites dans un code source, de la même manière que le traducteur de la chambre chinoise suit un organigramme, Regan pèse bien sa réponse. L’implication comme quoi les meilleurs joueurs d’échecs de la planète, artificiels ou non, suivent des règles, se rapporte à un débat en cours dans la communauté des échecs : des joueurs humains utilisent-ils ou non des séries de règles afin d’évaluer les positions ? Ironiquement, il est généralement considéré que les programmes d’échecs jouent dans un style qui ignore les règles.

Regan parle anglais, espagnol, allemand, italien et français, et il rentre dans le débat en distinguant bien les règles du langage humain de celles d’un code informatique. Selon Regan, « quand il s’agit des paramètres ajustables du programme – toutes les constantes magiques qui définissent la valeur de la reine, de la tour, du cavalier, la valeur d’une certaine position, des cases, des attaques –, ces paramètres sont ajustés par le comportement, par régression linéaire. Les programmeurs n’ont pas forcément de théorie quant aux valeurs et règles employées qui fonctionneront bien avec ces paramètres. Ils ont une idée générale, mais les valeurs finales sont déterminées par [le programme] jouant un grand nombre de jeux rapides contre lui-même, et voyant quelles valeurs se comportent le mieux ». Quand j’insiste alors que les 1 et 0 compilés d’un programme restent statiques, similaires à une règle écrite dans un livre, il se penche en arrière et reformule : « Oui, c’est vrai. Mais les ordinateurs utilisent la régression. »

« Je veux utiliser l’ordinateur pour mieux comprendre l’esprit humain. »

— Ken Regan

La régression qu’évoque Regan signifie ce qui suit : quand des 1 et des 0 restent statiques dans le programme initial du moteur d’échecs, d’autres 1 et 0 essentiels à la fonction d’évaluation du moteur – essentiels en ce qu’ils lui permettent de
penser – se mettent à jour dans la mémoire vive (RAM). Le processus imite un entraînement et améliore la capacité de l’ordinateur à faire plus que calculer. La régression génère un feedback en temps réel qui permet au moteur de
penser chaque position sans la contrainte d’un contexte, de la même manière qu’un cerveau humain gère le déséquilibre. Mais les ordinateurs calculent beaucoup plus vite. Deep Blue, le premier ordinateur à avoir vaincu un champion du monde en match standard régulé, parvint à la victoire malgré de faibles fonctions d’évaluation, qu’il contrebalançait par une grande vitesse de calcul. Les meilleurs moteurs d’aujourd’hui ne laisseraient aucune chance à Deep Blue parce qu’ils évaluent mieux, parce qu’ironiquement, ils
pensent plus comme des êtres humains.

« [Alan] Turing voulait modeler la connaissance humaine avec un ordinateur. J’irai dans la direction opposée », déclare Regan. « Je veux utiliser l’ordinateur pour mieux comprendre l’esprit humain. » Regan utilise comme base un résultat en psychologie mené par les économistes lauréats du prix Nobel Daniel Kahneman et son collègue Amos Tversky : la perception humaine de la valeur est relative. Regan admet qu’ « on peut traverser toute une ville pour économiser quatre dollars sur un achat qui en coûte 20, mais on ne le ferait pas pour un achat qui en coûte 2 000 ». Ses statistiques montrent que les joueurs font de 60 à 90 % plus d’erreurs avec une pièce en plus ou en moins que quand les adversaires sont à égalité. Regan prétend qu’il s’agit d’un effet cognitif avéré, non pas le résultat d’un jeu de type haut risque/haut rendement, car il est observé chez des joueurs à la fois en situation d’avantage ou de désavantage.

Les échecs ont été appelés la drosophile (ou mouche des fruits, souvent utilisée dans la recherche génétique à cause de ses larges chromosomes, de ses nombreuses variétés, et de son rapide taux de reproduction) de l’intelligence artificielle. Ils sont une manne importante de recherche en sciences cognitives et en psychologie, car le système de notation Elo fournit une mesure objective des capacités humaines. Le travail de Regan reste dans cette tradition scientifique. Il a traité plus de 200 000 jeux de référence animés par des joueurs dont le classement Elo était compris entre 1 600 et 2 800 points, en utilisant le système Rybka 3 à 13 coups et en mode single-line. Le mode single-line est un peu moins précis que le mode multi-line, mais fonctionne à peu près 20 fois plus vite. Ces jeux de référence fournissent une riche banque de données à partir de laquelle on peut construire des applications basées sur le modèle des échecs.

Les trois joueurs d’échecs
Cornelis de Man, 1670

En 2012, la FIDE a vendu les droits de distribution et de marketing des échecs professionnels à AGON, une société dirigée par Andrew Paulson. Selon le New York Times, « [Paulson] veut faire des échecs le prochain sport de marché de masse ». Paulson veut associer la couverture médiatique des compétitions majeures sur Internet à ce qu’il appelle ChessCasting, une émission proposant non seulement des parties, commentaires, vidéos et évaluations de moteurs, mais aussi des données biométriques telles que le pouls du joueur, les mouvements des yeux, la pression artérielle, et le taux d’exsudation. Le travail de Regan y ajoute de nombreuses statistiques non-invasives. « L’impact immédiat le plus important que je pense laisser sur le monde des échecs professionnels, mis à part mon travail contre la fraude, réside dans la statistique que je vais lancer, appelée Challenge Created, et qui permettra de distinguer objectivement les joueurs qui posent de gros problèmes à leurs adversaires. » Les plus grands casse-têtes pratiques ne sont pas toujours causés par ce que l’on considère comme les meilleurs coups, et le système de Regan permet de quantifier cette distinction.

D’autres statistiques se distinguant du système de calcul IPR de Regan, il devient par exemple possible de constater la dégradation du jeu sous pression (dans le graphique 5, l’augmentation du nombre d’erreurs se fait près du 40^e tour de jeu, via contrôle par pendules d’échecs) ainsi que de normaliser les différents systèmes de classements dans le monde. Les joueurs amateurs se demandent constamment à quel niveau leur classement chess.com, par exemple, peut être comparé avec ceux de leur fédération nationale. Le système IPR fournit un moyen de standardiser cette manœuvre. En un sens, les IPR sont encore plus précis que les classements traditionnels car ils sont calculés sur la base de chaque coup joué, plutôt que sur chaque partie. Faire un mauvais tournoi pouvait plomber un classement traditionnel, mais si ce mauvais tournoi n’était la résultante que de trois mauvais coups isolés, alors une telle déveine n’aurait pas un effet préjudiciable prononcé sur l’IPR. Regan admet toutefois que les moteurs biaisent leurs évaluations, parfois de manière infime, face à des coups humains, et cet effet « dérègle très légèrement les IPR ». La raison exacte de cet état reste inexpliquée et obsède Regan pendant son temps libre.

Pour le joueur qui cherche à s’améliorer, les IPR peuvent être utilisés comme indicateurs d’entraînement à divers stades de la partie. Admettons qu’une personne veuille obtenir une mesure objective de la façon dont elle joue les milieux de partie en jeu espagnol par rapport à une partie jouée en défense scandinave, tout ce qu’elle aurait à faire serait d’isoler les coups et positions qui l’intéressent, de les envoyer au générateur IPR de Regan, et elle obtiendrait une mesure de ses compétences. Cette méthode a été utilisée par Regan pour évaluer des joueurs de renom. Pendant des années, le statisticien Jeff Sonas a évalué ces joueurs mais l’IPR de Regan reste plus objectif. Sonas utilise les résultats des parties historiques, ce qui ne fournit que des informations relatives à certaines périodes. Seuls des joueurs ayant vécu à la même époque peuvent s’affronter. Mais depuis que les méthodes de Regan comparent les coups à un standard commun (le moteur) plutôt qu’aux résultats des parties, il est possible de faire le lien entre des joueurs de différentes époques. Il en ressort qu’une inflation des classements n’existe pas.

« Les échecs sont la vie. »

— Bobby Fischer

Entre 1976 et 2009, il n’y a pas eu de modification notable dans l’IPR pour les joueurs des classements de la FIDE. Par exemple, le graphique 6 montre comment l’IPR de joueurs classés entre 2 585 et 2 615 points est restée constante avec le temps. De nos jours, des milliers de grands maîtres et des dizaines de joueurs classés au-delà de 2 700 constatent une augmentation légitime des compétences. On pourrait ainsi conclure que l’apex de Hikaru Nakamura au classement FIDE avec 2 789 points dépasse celui de Bobby Fischer et ses 2 785 points pour le titre de meilleur champion américain de tous les temps, et le classement de Magnus Carlsen avec 2 881 en fait le meilleur joueur humain tout court (voir graphique 6).

Pourquoi ne parvenons-nous pas à comprendre les fraudeurs ? Le journaliste du New Atlantis Jeremy Ruzansky écrit que « les produits dopants sont une forme de fraude, qui n’altère pas que les résultats et les statistiques personnelles, mais transforme la personnalité de l’athlète. Si notre seul but était de battre des records de lancer de balle au baseball, on pourrait construire des machines au lancer parfait. Il est bon de se demander pourquoi on ne le fait pas, pourquoi on ne remplacerait pas nos sportifs par des machines, quand bien même les machines obtiendraient de meilleures performances ».

La réponse de Ruzansky est que nous ne donnons de valeur aux statistiques qu’en tant que performance humaine de niveau supérieur. Nombre d’athlètes et de joueurs d’échecs, y compris Bobby Fischer, ont comparé le sport à la vie. « Les échecs sont la vie », déclara l’ancien champion américain. Pour la société, on associe le sport à la métaphore de la compétition, inhérente à la vie, et cette métaphore ne fonctionne que quand un être humain est impliqué, dans le cas des échecs, quand son esprit contemple la complexité des coups.

Et pourtant, les fraudeurs voient en leur action une forme de sport. Dans le Journal de la personnalité et de la psychologie sociale, des chercheurs ont découvert que les fraudeurs prenaient du plaisir quand ils s’en sortaient impunément, quand bien même d’autres personnes en connaîtraient le fin mot. Par exemple, Boris Ivanov continua à frauder bien après avoir été exposé, en attente de sa suspension. Des comportements comme celui d’Ivanov constituent une grande menace pour les tournois d’échecs, car les risques d’arracher ainsi une victoire ne sont pas élevés. Confronté à un calcul complexe, un joueur pourrait facilement utiliser un smartphone dans la salle de bain pour un coup unique, et frauder ainsi sur une seule position critique. L’ancien champion du monde Vishanathan Anand annonça qu’un simple détail, un simple oui/non quant à la pertinence d’un sacrifice par exemple, pourrait valoir 150 points de classement.

Aristocrates joueurs d’échecs
Thomas Eakins, 1897

Mais les fraudeurs qui choisissent leurs coups auraient tendance à le faire sur des coups critiques, et Regan dispose d’autres tours dans son sac. « Si l’on dispose ne serait-ce que de quelques coups, pour lesquels quatre possibilités s’offriraient au joueur, la probabilité de faire correspondre ces coups devient tout de suite plus importante. Ou alors, l’arbitre pourrait me demander d’analyser une partie et me dire combien de coups il suspecte. Je lui donnerai alors mon avis et essayerai de lui dire quels seraient les coups en question, comme lors d’une séance d’identification de la police. Nous devons toutefois savoir quels coups analyser, et plus important encore – il s’agit même de la partie la plus vitale –, il doit y avoir un critère d’identification de ces coups indépendant du fait qu’ils correspondent. »

Si aucune de ces techniques contre les coups sélectifs n’a été discutée par le comité anti-fraude de l’ACP-FIDE, Regan croit qu’elles fonctionneront. Mais il modère son optimisme. Il n’a pas hâte qu’on en arrive aux prochaines évolutions dans les méthodes de fraude, qui devront forcément se produire entre les fraudeurs et ceux qui les exposent, un phénomène qui a invariablement pourri d’autres sports. D’autres défis persistent. Un nouveau paramètre de profondeur calant le nombre de coups évalués par un joueur est en cours d’élaboration pour lier « s » et « c ». Le moteur standard Rybka 3 est en train d’être converti en Houdini. Et la préférence omniprésente quoique minimale de comportements anti-humain dans les résultats du moteur doit également être réglée.

En 2012, Regan a perdu un match de démonstration contre un robot construit en pièces de Lego, fonctionnant avec un moteur Houdini, équipé d’un bras déplaçant les pièces sur un véritable échiquier et disposant d’une caméra pouvant interpréter les positions. L’expérience lui fit forte impression. « La technologie va-t-elle être si omniprésente qu’on ne pourra plus la réguler ? », demande-t-il pendant que lui-même, sa femme et moi dînons dans un restaurant thaïlandais du quartier. Regan se penche sur son assiette, l’air déprimé d’avoir eu ne serait-ce qu’à poser la question. « Houdini a gagné en mettant seulement 6 secondes par tour », dit-il. Le match rappelle à Regan que sa vocation lui a rogné beaucoup de temps sur ses recherches et sa famille. « Il est obsédé », dit sa femme de l’autre côté de la table. Mais « il faut être obsédé pour être bon à quelque chose », ajoute-t-elle. Regan ignore le compliment, son attention divertie par une pensée émergente. Il saute alors dans sa chaise, souriant. « À propos », dit-il, « ce projet était piloté par quelqu’un dont la mère et ma mère ont un meilleur ami en commun dans le New Jersey… »

Traduit de l’anglais par Gwendal Padovan d’après l’article « How To Catch A Chess Cheater: Ken Regan Finds Moves Out Of Mind », paru dans Chess Life.

Couverture : The Chess Game, Charles Bargue.