« Les réformistes prétendent que les progrès de la théorie conduiront à la disparition des Échecs, et qu’il faut, pour leur rendre vie, en remanier les règles. En réalité, qu’exprime cette affirmation ? Le mépris de l’intuition, de l’imagination et de tous les autres éléments qui font des Échecs un art. »
Alexander Alekhine (1892-1946).

Pour ce billet je ne pouvais pas trouver de citation plus à propos, sauf à remplacer dans le texte « les progrès de la théorie » par « les ordinateurs » (car il est aujourd’hui admis que l’ordinateur, qui n’existait pas à l’époque d’Alekhine, est devenu le principal instrument des progrès de la théorie).

En poussant un peu le bouchon, la question pourrait se poser ainsi : comment continuer de trouver du plaisir dans la pratique d’un jeu dont on sait qu’il sera tôt ou tard résolu ?
Par « résolu » comprenez qu’un programme informatique en aura exploré toutes les possibilités, et in fine révélé la ou les suites parfaites, celles où les deux adversaires jouraient invariablement les meilleurs coups. Nous saurons alors qui de Noir ou Blanc est à priori gagnant, à moins évidemment que l’issue ne soit nulle (« Tout ça pour ça ! dit le badaud, quelle déception ! » 😀 ).
Notez que plusieurs jeux ont déjà été résolus : Connect Four (plus connu en français sous le nom de Puissance 4 ; le joueur qui commence a une ligne gagnante contre toute défense dès l’instant qu’il joue son premier coup dans la colonne du milieu, c’est une affaire de parité) ; Quarto (si Noir et Blanc jouent parfaitement, la partie sera forcément nulle) ou encore, plus récemment, les Dames anglaises, dont l’espace de recherche est à ce jour le plus vaste à avoir jamais été résolu1 (partie nulle)…

Eh bien, d’une certaine façon (mais d’une certaine façon seulement, et cela fait sans doute toute la différence), c’est ce qui menace d’arriver un jour aux Échecs, comme aux autres jeux de réflexion qui entrent dans le moule des jeux déterminés à information complète et parfaite et qui résistent encore à l’analyse informatique (Othello, les Dames, le Go…).

Faut-il s’en inquiéter ? Pas vraiment.
Nous avons même plusieurs raisons de nous rassurer :

1. Le commun des mortels ne se sent pas concerné.
Tout ce qui intéresse le joueur occasionnel, c’est de se divertir et non de se prendre la tête avec ces histoires de suites aussi parfaites qu’imbitables.
Lorsque Jackie fait sa grille de Sudoku assise sur le trône, elle se fout de savoir que la solution se trouve en dernière page, elle fait marcher ses deux neurones ; d’une ça la détend, de deux ça l’aide à démouler.

2. D’autres cataclysmes ont le temps de nous tomber sur la tête (à commencer par le 21 décembre 2012).
En effet, selon les spécialistes, il faudra de longues années avant qu’un jeu comme les Échecs soit résolu, il est même peu probable que cela arrive de notre vivant (voire celui de nos enfants ; bon là je m’avance un peu). Et plus l’espace de recherche d’un jeu est important (i.e. sa complexité exprimée en nombre de positions possibles), plus cela prendra de temps.
Prenez le Go : il existe 361 possibilités pour poser la première pierre, 360 pour la deuxième, etc. Le nombre total de positions possibles est ainsi de l’ordre de 10170 ! Monstrueux2. À titre de comparaison, il est d’environ 1050 pour les Échecs et de « seulement » 1028 pour Othello (un jeu de tapettes quoi).

3. L’homme et l’ordinateur ne jouent pas dans la même catégorie.
On pourrait imaginer que s’ils disposaient de l’arbre de jeu complet, les joueurs de compétition ne se prépareraient pas de la même manière, ils ne chercheraient plus à introduire des nouveautés stratégiques mais davantage à mémoriser les suites parfaites (ce qu’au demeurant ils font déjà, dans les limites de la théorie actuelle). Ce serait en quelque sorte la fin du jeu tel que nous le connaissons. Ça fout les boules. Sauf que c’est tout bonnement impossible. Car cela supposerait que pour chaque coup déviant (i.e. chaque coup imparfait) le joueur connaisse aussi la réfutation qui s’applique jusqu’au bout de l’arbre, et ce pour tous les coups ! La vache.
Inutile de vous dire que c’est totalement hors de portée, cela nécessiterait une capacité de mémorisation surnaturelle (à tout le moins dans un environnement sans OGM :-D), une force qui est et restera l’apanage des ordinateurs.
La résolution du jeu d’Échecs nous renseignerait donc tout au plus sur l’issue théorique d’une partie, mais la connaissance d’une ligne parfaite serait comme un grain de sable sur la plage… Bref, cela aurait un effet démystifiant et légèrement réducteur3, mais cela n’ôterait pas au jeu son intérêt à l’échelle de nos p’tits cerveaux reptiliens ; cela focaliserait l’étude autour de certaines variantes (et encore, d’aucuns pourraient a contrario être tentés de s’en éloigner le plus possible pour éviter une forme de standardisation du jeu), mais personne ne saurait en tirer un avantage définitif, à moins de se faire greffer un microprocesseur sur le lobe frontal. En fin de compte, cela ne changerait pas radicalement la donne.

Le vrai changement, celui que les « réformistes » craignaient, il est venu lorsque les ordinateurs ont commencé à battre les meilleurs joueurs humains.
À l’époque d’Alekhine, on était loin de se douter que les ordinateurs permettraient un jour d’étudier les Échecs, qu’ils seraient en quelque sorte les nouveaux dépositaires de la théorie, et encore moins qu’ils en viendraient à bout. Mais certains dénonçaient déjà le processus de théorisation du jeu qui selon eux conduirait inévitablement à cette forme de normalisation des parties, notamment dans le choix des ouvertures (une fois qu’il est acquis que certaines ouvertures sont meilleures que d’autres), privant le jeu d’une part de créativité et empêchant le talent pur de s’exprimer librement. Et c’est précisément ce processus que les ordinateurs ont accéléré au point que, aujourd’hui, il devient de plus en plus difficile, pour ne pas dire suicidaire, de jouer en dehors des ornières creusées par la théorie.

La défaite la plus retentissante concernant la passation de pouvoir entre l’homme et la machine a été le match revanche entre Kasparov et Deep Blue, le superordinateur d’IBM, en mai 97 à New York.
Elle a suscité chez Kasparov une rare incrédulité. D’abord parce qu’il avait jusque-là toujours été intimement convaincu que les ordinateurs jouaient comme des bites étaient « stupides » (ce qui se défend, vu qu’un des principaux algorithmes des machines consiste à évaluer tous les coups, même les plus pourris, mais notre ami Kasparov avait manifestement négligé l’extradordinaire puissance de calcul de la bête, capable d’analyser jusqu’à 200 millions de coups à la seconde ! À ce compte on peut se permettre d’analyser aussi les mauvais coups :-D), ensuite parce qu’il ne pouvait pas encaisser de se faire dérouiller par une merde en ferraille remplie de condensateurs et de circuits imprimés, fût-elle créée par l’esprit humain.
D’ailleurs, lors de la fatidique deuxième partie, Kasparov a accusé IBM d’avoir triché en faisant appel aux conseils d’un grand maître (au hasard, Karpov). Un des coups de Deep Blue semblait en effet inconcevable pour une machine dont la faiblesse devait être le penchant matérialiste et la difficulté à jouer dans des positions fermées. Aussi, quand Deep Blue a refusé l’avantage de pions que lui offrait Kasparov, lui préférant un coup positionnel, Kasparov a cru voir la main du diable, et le fait que Deep Blue ait longtemps « réfléchi » à ce coup achevait de l’en persuader : on était en train de lui faire à l’envers ! 😀
Le plus étonnant dans l’histoire, c’est que Kasparov a abandonné alors qu’il pouvait encore faire nulle (en jouant une séquence qui menait à un échec perpétuel). Plus tard, il commentera : « The truth is that I was very tired and couldn’t believe the way the machine had just played. I trusted its calculations. I assumed that if the machine allowed a move such as Qe3 at the end, it had calculated everything that could follow and found wins, so I didn’t even bother checking it. Costly error, as I soon found out. »
Cette défaite a littéralement torpillé Kasparov. Jusqu’à la fin du match (qui se déroulait au meilleur de six parties), il ne sera plus que l’ombre de lui-même, incapable de se faire à l’idée que Deep Blue ait pu le battre à la régulière. Comment se pouvait-il que Deep Blue joue avec une telle profondeur d’analyse, et que dans le même temps il n’ait pas été en mesure d’anticiper un simple échec perpétuel ? Pourquoi avait-il mis si longtemps avant de jouer 37.Be4 ? Pourquoi refusait-on au staff de Kasparov d’accéder aux fichiers logs de la machine ? Autant de questions qui alimentaient la parano du Russe.
Dans la dernière partie, il jouera une ouverture réputée perdante, comme s’il avait voulu battre la machine sur un terrain qui lui est complètement étranger : la psychologie. Erreur fatale.

Hop, extrait du documentaire de Vikram Jayanti : Game Over : Kasparov and the Machine.

Et la partie en question, sinon c’est pas drôle :

Bon, je suis un peu à la dérive. L’idée, au départ, c’était de dire que les ordinateurs dominent largement les meilleurs joueurs mondiaux4, que c’est sur leurs analyses que s’appuient désormais toutes les stratégies, et qu’en dehors de ces stratégies point de salut. Ce qui a tendance à rendre le jeu prévisible et chiant. Les ouvertures n’étant bien souvent qu’une succession de coups récités par cœur jusqu’à ce qu’un des deux joueurs décide de sortir de la sacro-sainte bibliothèque d’ouvertures5, au mieux parce qu’il a préparé une combinaison maison au bénéfice de laquelle il pense pouvoir piéger son adversaire, au pire parce qu’il ne se souvient plus de la suite théorique 😀

Quand le jeu devient à ce point formaté, on est en droit de se demander quelle part de plaisir et de créativité il nous reste.
Voilà, en susbstance, ce que dénonçaient les réformistes. Et, n’en déplaise à ce cher Alekhine, ils n’avaient pas complètement tort.

J’avais précédemment expliqué (ici) qu’une façon de sortir des sentiers battus consistait à pratiquer le jeu rapide. Mais ce n’est pas la seule option.
Dans les années 90, le GM Bobby Fischer a imaginé une façon beaucoup plus radicale de « redistribuer les cartes » : il a inventé (ou remis au goût du jour, c’est selon) les Échecs aléatoires (en anglais Fischer Random Chess, ou encore Chess 960 où 960 représente le nombre total de positions de départ différentes liées au système de jeu qu’il propose). Concrètement, il s’agit d’une variante des Échecs dans laquelle la position de départ des pièces de la première rangée est tirée au sort ! (Avec quand même deux ou trois règles conditionnelles comme le fait que le Roi doit obligatoirement être entre les Tours, les Fous sur des cases de couleurs opposées…) Ceci afin de changer la physionomie des parties (les nouvelles positions de départ impliquant de revoir les plans de jeu habituels), et de remmettre au centre des préoccupations la maîtrise des concepts fondamentaux du jeu.
Inutile de préciser qu’il serait tout à fait vain de vouloir mémoriser les ouvertures théoriques à partir de 960 positions de départ différentes !
Pour prendre un exemple que je connais mieux : si demain la position de départ du jeu d’Othello changeait, cela mettrait à mal l’ensemble des théories existantes sur les débuts de partie, en revanche les principes fondamentaux que sont l’occupation du centre de la position, la mobilité, la frontière, la notion de parité etc., tous ces principes continueraient de s’appliquer, et la créativité des joueurs retrouverait une première jeunesse, celle d’il y a quarante ans, lorsqu’il y avait encore tout à faire, tant de choses à découvrir, tant de pistes à défricher…

Le hic, c’est qu’on ne peut pas appliquer directement le système de Fischer à Othello, car le nombre de départs différents serait de… deux ! Soit la position classique, où les pions noirs et blancs sont disposés en chiasme, soit la position historique du Reversi, où les pions sont parallèles.
De fait, des joueurs ont imaginé que la partie pourrait démarrer après que quelques coups aient été préalablement joués de façon artificielle, en faisant en sorte que la configuration des pions ainsi formée assure une égalité quasi parfaite entre les joueurs.
Borja Moreno et Matthias Berg ont utilisé des programmes d’Othello (Edax et Ntest) pour créer une liste d’ouvertures aléatoires « à 8 coups » considérées comme étant équilibrées (i.e. dont l’évaluation est entre +1 et -1).
Borja a implenté cette liste sur son serveur de jeu en ligne qui offre donc la possibilité de s’essayer au jeu sur ouverture aléatoire (random opening).
Matthias quant à lui a développé une application java (XOT) qui permet de générer des ouvertures aléatoires à la demande, ce qui est particulièrement pratique pour affronter un ami ou organiser un tournoi ITRW.
Voici quelques exemples de positions ainsi créées (la partie commence réellement au neuvième coup, Noir conserve donc le trait) :

Naturellement ce système n’est pas parfait mais il permet de renouveler astucieusement l’intérêt des parties en obligeant notamment les joueurs à réfléchir dès le premier coup (ce qui n’est jamais le cas dans une partie classique entre joueurs expérimentés) et en proposant des modèles de partie aussi inhabituels qu’amusants.
Fischer disait à propos des Échecs 960 qu’il ne s’agissait pas de « tuer les Échecs », mais bien au contraire de leur redonner l’apparence du bac à sable dans lequel le talent et la créativité des joueurs peuvent s’exprimer à plein, laissant aux vestiaires les lignes apprises par cœur et autres formes de parties préarrangées.
Et Levon Aronian d’ajouter : « Chess 960 is healthy and good for your chess. If you get into it and not just move the pieces to achieve known positions it really improves your chess vision. »

1 Il aura fallu plus de 18 ans et jusqu’à 200 ordinateurs travaillant simultanément pour que Jonathan Schaeffer et son équipe viennent à bout des Dames anglaises (plateau 8×8) : http://webdocs.cs.ualberta.ca/~chinook/
2 Un espace de recherche tellement vaste que la force de calcul brute n’y suffit pas (il y a quelques années, les meilleurs programmes de Go jouaient encore comme des brêles), certains spécialistes se sont ainsi penchés sur de nouvelles heuristiques basées sur ce qu’on appelle des simulations Monte-Carlo, sortes de techniques probabilistes qui permettent d’élaguer très largement l’arbre de jeu à analyser. Cet article paru dans Pour La Science (n°354, avril 2007) en parle beaucoup mieux que moi et se lit comme du petit lait. Et pour ceux qui aiment se prendre le bulbe, voir aussi les travaux de Rémi Coulom sur le sujet : http://remi.coulom.free.fr/ (en anglais).
3 Le truc un peu chiant ou paradoxal ou les deux, c’est de se dire qu’on connaît la meilleure façon de jouer, la stratégie dominante, celle qui est au-dessus de toutes les autres, mais que pour continuer de s’amuser il faille nécessairement en jouer une moins bonne…
4 C’est au moins vrai pour Othello (j’ai en mémoire la cinglante défaite de Takeshi Murakami face à Logistello), les Dames (et ce en dépit de la récente victoire d’Alexander Schwarzman face à Maximus) ou les Échecs… en revanche c’est loin d’être le cas pour le Go, même si les progrès accomplis en termes de programmation ces dernières années sont impressionnants.

5 Les ouvertures sont au jeu ce que les voies d’insertion sont à l’autoroute, il y en a des longues, des sinueuses, d’autres qui se terminent vite, mais dans tous les cas le but est le même : s’insérer le plus sûrement possible. À défaut le voyage risque de tourner court.

6 commentaires sur “La fin progammée des jeux de réflexion”
  1. The Braiiiin dit :

    « Pas de commentaire. »

    Tu m’étonnes.
    Et pourtant j’ai essayé…

  2. Frank Poupart dit :

    J’espère que t’as quand même noté mes efforts de vulgarisation (cf. le § sur Jackie) ! 😀

  3. Dominique dit :

    Merci pour cet excellent article !
    Alors on se la fait quand cette ouverture aléatoire sur eothello ?

  4. Frank Poupart dit :

    Ça fait une paie que j’ai pas joué sur eothello mais promis je vais m’y remettre juste pour te tataner mon Dom :-)
    La biz aux filles !

  5. TLA dit :

    Excellent article, tu as vraiment l’étoffe d’un journaliste !

    Je n’ai pas grand chose à redire, je suis d’accord avec tout ou presque… 2 remarques quand même :

    1/ les algorithmes classiques, utilisés depuis 40 ans, élaguent environ 99 % des arbres d’exploration, voire davantage. Minimax tout seul explore tout. Mais en y ajoutant alpha-beta, on élague déjà beaucoup. Et on gagne encore en efficacité grâce au « coup meurtrier », qui consiste à essayer en priorité un coup qui tue dans d’autres branches, afin d’avoir plus de chances de provoquer un élagage alpha-beta.

    2/ à ma connaissance, l’algorithme de Monte Carlo est effectivement probabiliste mais tout bête : il consiste, à partir d’une position, à essayer, pour chaque coup possible, des millions de lignes prises au hasard, et à retenir le coup qui génère le plus de lignes s’avérant gagnantes. C’est très efficace pour le Go. Mais j’imagine qu’on peut coupler cet algorithme au minimax alpha-beta, pour essayer seulement les coups les plus prometteurs…

  6. Frank Poupart dit :

    Merci Thierry pour ces remarques très justes (j’ai un peu forcé le trait il est vrai). C’est sympa de te savoir dans le coin :-)
    Concernant ta dernière phrase : « Mais j’imagine qu’on peut coupler cet algorithme au minimax alpha-beta, pour essayer seulement les coups les plus prometteurs… » En effet, c’est ce que fait notamment Rémi Coulom avec son programme Crazy Stone (lequel a battu l’an dernier un joueur 5p avec 4 pierres de handicap !).

  7.  
Je commente, je flatte, je tacle...