Morpion Solitaire - Premiers programmes informatiques jouant au "morpion"

Morpion Solitaire - "Morpion" ?
? (français) / Trois Sens / Rabelais / Jeu / Programmes / Citations / Musique / San Antonio / Lieux / Solitaire / FDJ
? (English) / 3 Meanings / Rabelais / Game / Programs / Quotations / Music / San Antonio / Places / Solitaire / FDJ
These pages are written in French. However the images or videos don't need to be translated, and you may find some English quotations within the French text.

Les premiers programmes informatiques jouant au "morpion"

Le jeu de morpion à deux joueurs est courant en France depuis le début XXème siècle, avec un premier témoignage datant de 1924.

Le plus ancien programme informatique que j'ai pu trouver date de 1961. Voici le témoignage que m'a communiqué Paul Braffort en septembre 2010 :

Après mes cinq années au CEA, je suis entré à Euratom en 1959 pour mener une recherche multidisciplinaire au sein d'un groupe que nous avions baptisé "GRISA" (Groupe de Recherches sur l'Information Scientifique Automatique), devenu en 1961 le "CETIS" (Centre Européen de Traitement de l'Information Scientifique Automatique). Nous y abordions la plupart des thèmes de ce qui était en train de devenir, avec Marvin Minsky, l'"Intelligence Artificielle". Cela incluait évidemment la simulation des jeux, initiée par Shannon, Samuel et quelques autres. Nous avons alors travaillé sur les échecs, avec Claude Berge, David Hirschberg et Max Euwe (ancien champion du monde). Mais nous nous attaquâmes aussi au Morpion (ou Go-Bang) pour lequel nous produisîmes un programme relativement efficace. Ce travail avec André Lussan fut présenté en octobre 1961 au deuxième colloque de l'AFCALTI (qui deviendra l'AFCET). Il a été publié dans les actes du Colloque, p.221. Il est accessible aussi sur mon site www.paulbraffort.net, voir la page 1 puis les suivantes.
En 1968, les Presses Universitaires de France publièrent un bilan de ces travaux et une réflexion sur leur portée : "L'Intelligence Artificielle", ouvrage épuisé mais également accessible sur le site. Le Chapitre III, intitulé "Les jeux", dans le paragraphe "Etude d'un exemple", donne une description assez détaillée de notre travail. Je n'ai pas connu le Morpion Solitaire, malheureusement....

On peut lire dans ses travaux que les ordinateurs utilisés par le programme de Paul Braffort et André Lussan étaient des IBM-1620 et IBM-7090. Ces ordinateurs avaient été commandé en 1960 par Euratom pour les bureaux d'Ispra, en Italie (voir http://www-03.ibm.com/ibm/history/exhibits/italy/italy_ch2.html). Il est très possible que d'autres programmes aient existé avant le leur, notamment au Japon où les jeux de gomoku et renju, très proches du morpion, mais respectivement limités à des grilles 19x19 et 15x15, sont très anciens et populaires.

IBM-1620 à gauche, et IBM-7090 à droite.
(source image IBM 1620 http://theinvisibleagent.wordpress.com/2011/05/24/the-ibm-1620-1959/ et IBM-7090 http://computer-history.info)

En 1968 paraît un Hors-Série de Science & Vie consacré à l'informatique. Jacques Pitrat y rédige un article intitulé "L'Intelligence Artificielle" dans lequel il parle d'un programme jouant au tic-tac-toe, ainsi que d'un autre programme jouant au Morpion. Voilà son témoignage, également reçu en septembre 2010 :

Il faut vraiment faire appel à mes souvenirs, car je n'ai plus d'exemplaire de cet article de 1968 ! Je pense que j'étais l'auteur du programme, car à cette date j'avais réalisé un programme général de jeux qui jouait au jeu dont on lui donnait les règles. Parmi les jeux que j'ai essayé figurait justement le morpion, j'avais donc des parties jouées par mon programme. Je pense que j'ai utilisé une de ces parties; d'ailleurs je ne vois pas quel autre programme j'aurais pu utiliser, il n'en existait pas beaucoup en dehors du mien à cette époque ! Je me rappelle l'existence d'un programme plus ancien de morpion fait par Braffort et Lussan, mais je n'ai certainement pas utilisé leurs résultats. J'utilisais l'ordinateur CDC 3600 de l'Institut Blaise Pascal du CNRS, situé rue du Maroc dans le dix-neuvième, avant sa disparition suite aux événements de mai 68. La photo du Multivac a été ajoutée par Science & Vie, je n'ai jamais utilisé cet ordinateur.
Je ne connaissais pas le Morpion Solitaire et j'ai été très intéressé par votre site. J'y ai découvert que Tristan Cazenave, que je connais bien, avait établi momentanément des records pour une variante de ce jeu. Depuis 25 ans, je ne travaille plus sur les jeux, bien que je suive toujours les résultats nouveaux dans ce domaine, en particulier grâce au ICGA Journal.

Joueur contre machine : un début de partie jouée contre le programme tournant sur un CDC 3600
(à gauche, extrait de Science & Vie Hors-Série n°82 "L'Informatique", 1968, page 141, cliquer pour voir la page entière)
(à droite, source image CDC 3600: http://computer-history.info)

Quant au jeu du Morpion Solitaire, un programme Fortran IV écrit en 1970-72 pour un UNIVAC 1108 d'Orsay, depuis un terminal lecteur de cartes perforées de l'ENSET de Cachan, est mentionné par Christian Klipfel dans son site. Est-ce le plus ancien programme jouant au morpion solitaire ? En tout cas, avant la grille de 172 coups de Chris Rosin obtenue en 2010, les ordinateurs ont été incapables d'atteindre de gros scores et de battre le record de Bruneau obtenu en 1976 à la main : voir les tentatives à partir de 1995.

UNIVAC 1108 (source image http://en.wikipedia.org/wiki/UNIVAC)