Denis FELDMANN
La série de "dictionnaires" de la Nihon Ki-in contient par exemple deux volumes sur le Fuseki, un sur le Y ose, etc... Il y figure aussi un intéressant "dictionnaire de Ko ", où sont entre autres classées des positions de vie et mort classiques (carré du charpentier, "L long" de Davies, etc...) se terminant en Ko ; j'en ai extrait le problème ci-contre (Utilisé pour la couverture du N° 65), et la question est bien sûr de déterminer le meilleur Ko (et d'analyser la structure éventuelle des menaces intrinsèques, etc...).
Problème 1 : (couverture de GO-RFG N°65) : Blanc joue : statut du groupe noir ?
La solution proposée par le dictionnaire est montrée dia.l ; on remarquera en particulier des variantes inférieures telles que le dia.2, qui conduit à un Ko moins intéressant pour Blanc. Tout cela est trouvé en une minute environ par les quelques joueurs cinquième Dan (André Moussa, Farid Ben Malek, Frédéric Donzet) auxquels j'ai soumis ce problème.
Diagramme 1 :Noir doit trouver la première menace de Ko pour reprendre en 2
Diagramme 2 : Inférieur, car c'est Blanc qui doit trouver la première menace)
Il n'y a qu'un petit ennui : en fait, ce groupe est mort sans condition (dia.3, 4 et 5). Je n'y ai pas cru non plus quand le programme de Tsumego de Thomas Wolf m'a fourni (en vingt secondes) cette analyse, mais j'ai bien dû me rendre à l'évidence ; et ceci semble bien être le premier résultat obtenu par un ordinateur qui aurait échappé à des humains forts (j'attends avec impatience la réaction des pros cet été à Maastricht), ce qui dans notre domaine est sans doute un scoop, quand on connaît les performances généralement déplorables des programmes.
Diagramme 3
Diagramme 4
Diagramme 5 : En fait Noir meurt sans condition !!!
J'ai donc décidé d'en profiter pour faire le point des résultats actuels en informatique "goïque" (quelqu'un aurait-il un adjectif mieux formé ?) ; la synthèse qui suit est en partie basée sur un article de N. Wedd dans le British Go Journal (Janvier 92), mais je prends l'entière responsabilité des opinions (peu flatteuses) émises...
Ces programmes sont bien évidemment les seuls commercialisés ; on trouve dans cette catégorie :
a) Des programmes complètement débutants (et souvent "buggés") tels que les programmes proposés dans des lots de jeux (en shareware) ; il convient de mettre en garde le lecteur contre ce genre d'objet, dangereux en particulier pour une éventuelle initiation ; de nombreuses tentatives françaises (la mienne, par exemple) n'ont jamais dépassé ce niveau...
b) Des programmes médiocres (environ 15ème kyu*), l'intérêt principal de ces programmes est en général l'environnement fourni, et on peut en particulier recommander sans réserves "Many Faces of Go" (vendu en français sous le nom de "Go Master", ou encore (par la fédération) dans une version "gratuite" de démonstration sur 9x9) pour la qualité de ses graphiques et de ses options d'enseignement.
c) Des programmes compétitifs, obtenant de bons résultats dans des championnats d'ordinateurs (et en particulier dans le tournoi organisé à Taiwan par Ing) : on remarquera principalement les programmes de Mark Boon (la série des Goliath), et, quoiqu'un peu plus faibles, les programmes de Kraszek (Star of Poland) et de Reiss (Oxford Softwork, champion d'Europe 92). Ces programmes sont évalués (par leurs auteurs) au voisinage de l0ème kyu (Boon estime même à 8ème kyu le sien) ; je me montrerai plus pessimiste, surtout si on envisage de jouer longtemps avec un de ces programmes (il n'ont bien entendu aucune fonction d'apprentissage, et rejouent donc toujours les mêmes erreurs).
Les programmes de cette catégorie ne sont le plus souvent pas disponibles, bien qu'il soit parfois possible de disposer d'une copie de travail prêtée par l'auteur (et le plus souvent inutilisable sans un mode d'emploi détaillé, et évidemment non fourni). La plupart du temps, il s'agit de projets se concentrant sur une difficulté précise (apprentissage, reconnaissance de forme, utilisation de systèmes experts, etc.) et négligeant ou ignorant les autres aspects du jeu. Le plus prometteur de ces projets est sans doute celui d'Allan Scarff (la série des Microgo) ; hélas, il s'agit là surtout des promesses de Scarff, lequel envisageait par exemple en 86 d'avoir un programme 1er dan dans un délai de trois mois à un an. J'aurais tort d'ironiser, m'étant moi-même livré à des prophéties (un peu moins) optimistes analogues ; le seul aspect intéressant de cette histoire est l'extrême originalité des idées de Scarff (en particulier l'utilisation d'automates cellulaires) ; quand on sait à quel point aucune idée raisonnable ne donne grand chose de bon dans ce domaine, on finit par penser que seul quelque chose de complètement différent atteindra un jour un niveau intéressant (rappelons à ce sujet qu'un prix déjà confortable attend le premier programme qui battra (avant l'an 2000) le joueur proposé par M. Ing (un insei taiwanais) à 9 pierres de handicap**). Nemesis (de Bruce Wilcox) est un autre de ces projets prometteurs (basé sur les idées pédagogiques de son auteur, appelées "Instant Go", et dont les lecteurs les plus fidèles de la Revue se rappelleront sans doute les extraits publiés dans les numéros 2 à 6 !) ; tout le reste, pour autant que je le sache, a surtout fait l'objet de publications (thèse de Ryder en 72 (!), projet d'Hervé Dicky dans les années 85, les tentatives actuelles de Pompidor, etc.), et a surtout le mérite d'explorer des idées prometteuses (hélas le plus souvent pour aboutir à la conclusion qu'elles sont en fait peu efficaces, ou qu'il faudrait un temps énorme de programmation et de mise au point pour aboutir à un programme complet).
Le lecteur intéressé (et qui, s'il est novice, doit commencer à se demander depuis un bon moment pourquoi tout cela est si difficile***) lira avec profit le chapitre du livre de Pascal Reysset consacré à ces questions (le texte, fort bien documenté, a bénéficié des conseils de Bernard Vittori, cofondateur du groupe d'étude français "Go et Informatique"), ou mieux encore, s'il parvient à se la procurer, l'étude parue dans l'Almanach of Go d'Ishi Press.
Dans cette dernière catégorie, on trouve pêle-mêle :
a) Des programmes d'aide à l'archivage et à l'édition de positions (tels par exemple que celui (Smart Goboard) où sont stockées les parties commentées lors des stages fédéraux et publiées par intermittence dans ces pages), qui dans leurs options les plus riches peuvent aussi servir de base de données (le programme de François Péchoux vous retrouvera par exemple toutes les parties de pro contenant une grande avalanche, si vous savez lui poser la question), de vérification automatique (Goscribe compte les prisonniers, vérifie la légalité des coups, etc.), et éventuellement de Goban "magique", sur lequel une partie jouée (même en Blitz) est automatiquement enregistrée, où il est possible d'étudier des variantes sans craindre de ne pouvoir retrouver la position initiale, etc. Je profite de cette parenthèse pour signaler l'intéressant projet de travail de Simon-Louis Lavallou, consistant à utiliser un programme du même genre pour mémoriser des problèmes de référence (Joseki, Tesuji, Tsumego, etc.) et vérifier d'un clic de souris qu'il en a retenu la solution.
b) Des programmes de calcul tactique, qui étant donné un objectif (et parfois des informations complémentaires fournies par le joueur) déterminent si cet objectif est réalisable (capture d'une chaîne par Shicho ou Gêta, coupure de deux chaînes, calcul d'une séquence de Yose connaissant la valeurs des coups, etc). Là, la puissance de calcul de l'ordinateur peut évidemment être rentabilisée, et de plus en plus, on peut même espérer bénéficier de théories "inhumaines", mais exploitables par une machine : c'est ce qui semble s'être produit tout récemment avec la découverte d'une théorie mathématique du petit Yose (Berlekamp, Mathematical Go Endgames, Ishi Press), dont les résultats ont apparemment fort surpris les professionnels.
c) Et enfin le programme de Tsume-go de Thomas Wolf (non, je n'avais pas perdu de vue le début de l'article !)
Ce programme mérite d'être classé à part pour de nombreuses raisons : tout d'abord, il est spectaculairement performant, résolvant souvent des problèmes de niveau 5ème dan en des temps de l'ordre de la minute (l'exemple du dia.6 est résolu (dia.7, 8 et 9 page suivante) en 30 secondes), et ce avec une finesse d'analyse (classifications des Ko, calcul des menaces intrinsèques, diagnostic des Seki, etc.) d'autant plus surprenante que son auteur n'est que 7ème kyu ; ensuite, il fait appel à des méthodes d'"apprentissage" (très rudimentaires) qui lui permettent d'améliorer ses performances sur des problèmes d'un type proche de ceux qu'il a déjà rencontrés ; enfin il dispose d'un mode de génération de problèmes (il en construit de nouveaux en retirant ou déplaçant aléatoirement des pierres, et en sélectionnant les positions dont la solution est unique, et lui a demandé un travail important), qui fabrique quotidiennement plusieurs dizaines de problèmes, dont certains sont de difficulté professionnelle (c'est du moins l'opinion de Nagahara, qui, fort intéressé, lui en a proposé la publication au Japon en 1992). Pour être complet, et ne pas vous laisser sur une impression trop enthousiaste, il faut tout de même signaler (outre quelques bugs que nous**** sommes en train de corriger) que le programme ne peut traiter que les positions complètement fermées, et qu'il perd beaucoup de son efficacité s'il figure des libertés extérieures trop nombreuses. Pour conclure, un exemple parfait de «coup d'ordinateur» obtenu par le programme : dia.10, quel est le statut du groupe noir après le coup 1 ? (réponse dia. 11 page suivante)
Diagramme 6 : Noir joue et tue par Ko
Diagramme 10 : Statut de Noir ?
.
Diagramme 7
(Première partie...)
Diagramme 8 (Deuxième partie)
Diagramme 9 : (Troisième partie) N17 en 11, B18 en13 ; 20 : menace de Ko à trouver pour Blanc...
Diagramme 11 : Seki ! (aussi peu vraisemblable que cela puisse paraître !)
*Le problème de niveau est évidemment une bouteille à l'encre ; disons qu'il s'agit de performance moyenne lors de la première partie jouée contre la machine ; en effet l'humain apprend en général très vite à exploiter les faiblesses du programme, et le niveau apparent de celui-ci baisse donc à chaque partie.
** mais pour l'instant, aucun programme n'a réussi à gagner ne serait-ce qu'à 17 pierres !
*** on se contentera ici de faire remarquer que les méthodes de force brute qui ont si bien réussi aux échecs sont inutilisables pour le Go, à la fois parce que l'arborescence y est beaucoup plus dense (10700 positions pour le Go, contre «seulement» (!) 10120 pour les échecs), et aussi parce qu'il est difficile de juger une partie avant