Perfectionnons le programme
Un programme qui saurait effectuer toutes les analyses qui ont été exposées, et qui surtout saurait les effectuer rapidement, serait sans doute un bon programme. Mais il souffrirait de quelques défauts :
- l'effet d'horizon
Si votre ordinateur est programmé pour arrêter son évaluation au niveau N, vous comprendrez très bien qu'il ne se préoccupe pas de ce qu'il se passe au niveau N+1 et au-delà. Or il peut s'y passer des choses très intéressantes. Nous allons voir un exemple.
An niveau N-3, les noirs ont les cases 7,11,14,20. Les blancs ont la case 8.
Schéma n° 7
L'ordinateur (noir) voit que, s'il joue les pions 11, 14 ou 20 au niveau N-2, son adversaire fera une dame au coup N-1, qu'il aura toujours au coup N. Or une dame vaut 3 pions, et même plus en fin de partie, lui a-t-on expliqué. Par contre, en jouant le pion 7 au coup N-2, l'ordinateur perd certes 2 pions, mais son adversaire ne fait pas de dame au coup N-1 (il prend). L'ordinateur choisira donc cette solution, pensant aboutir à une position plus favorable. Et, ainsi, il transformera une victoire (la dame aurait été perdue au niveau N+1 sur 11-16 et 20-25) en défaite (les pions 14 et 20 ne passeront jamais).
Comment éviter cet effet d'horizon ? Et bien il est impossible de le supprimer tout à fait, il y aura toujours un horizon. Mais on peut le reculer, en examinant plus loin les solutions sensibles. Il convient en particulier de regarder plus loin les chemins qui passent par des prises, par exemple en augmentant le niveau maximum d'une unité chaque fois qu'il y a une prise, ou, c'est équivalent, en n'incrémentant* pas le niveau actuel lors des prises (en maintenant cependant une limite raisonnable pour éviter que l'ordinateur n'examine le don de tous les pions du damier). Dans le cas que nous avons étudié ci-dessus, l'ordinateur aurait alors vu que, au niveau N+1, l'adversaire faisait de toute façon une dame après le sacrifice des 2 pions.
Cette méthode concernant le recul de l'horizon après les prises offre de plus l'avantage de nous mettre généralement à l'abri des contre-coups qui peuvent suivre des combinaisons.
On peut aussi regarder plus loin certaines positions, indépendamment de l'enchaînement de coups (avec ou sans prises) qui nous y a conduits. Ainsi, nous avons vu dans un chapitre précédent que les branches étroites devaient être explorées plus loin. De même, les positions où un joueur est prés de la ligne de dame sont à étudier plus à fond.
- la maîtrise du temps
En fait, beaucoup de programmes ne maîtrisent pas correctement leur temps de jeu (en particulier Dames 2020). Ils vous offrent de jouer à un certain degré de difficulté, mais vous ne savez pas s'ils vont vous répondre en 5 secondes ou en 3 minutes.
La recherche itérative, que j'aurais pu vous présenter dans le chapitre concernant l'alpha-bêta car elle en constitue un perfectionnement, permet une meilleure régularité dans les temps de réponse.
Contrairement aux techniques présentées jusqu'ici, la recherche itérative ne diminue pas le nombre de boucles examinées, mais les augmente. Quel est alors son intérêt, me direz-vous ?
Suivez-moi bien, et vous comprendrez. La recherche itérative se déroule de la façon suivante :
* On étudie l'arbre des solutions d'abord jusqu'à un niveau N (par exemple 2).
* Puis on ordonne les solutions trouvées.
* On réexamine depuis le début l'arbre jusqu'à un niveau M, supérieur à N (généralement N+1). Cet examen au niveau M sera généralement plus rapide que si on l'avait entrepris directement dès le début, puisqu'on le fait selon l'ordre des solutions du niveau N, et qu'une bonne solution au niveau N a une certaine probabilité de rester bonne au niveau M. Selon la théorie précédemment exposée de l'alpha-bêta, une recherche commençant par les bonnes solutions donne lieu à plus d'élagages, et donc se déroule plus rapidement.
* On ordonne les solutions.
* On recommence depuis le début jusqu'au niveau P, supérieur à M.
* .....et ainsi de suite.
Même si nous supposons que nous n'avons rien gagné dans les élagages alpha-bêta, l'augmentation du temps de calcul est relativement faible. En effet, si nous supposons que le nombre moyen de branche est de d, et que le nombre de niveaux à examiner est de p, une recherche itérative jusqu'au niveau 1, puis 2, ....puis p se traduit, sans alpha-bêta, par l'examen de d p+d p-1+.....d noeuds terminaux, soit (d p+1-d)/(d-1), au lieu de d p si on n'avait pas utilisé cette méthode. Le rapport entre les 2 nombres de solutions examinées est équivalent à d/(d-1) lorsque p est grand, et est d'autant plus proche de 1 que d est grand (ce qui signifie que la rentabilité est meilleure aux échecs - d moyen voisin de 35 - qu'aux dames - d moyen voisin de 10 -).
Mais me direz-vous, quel est le rapport avec la maîtrise du temps ?
Et bien, avec une telle méthode, l'ordinateur peut toujours proposer une solution jugée bonne jusqu'à un certain niveau d'examen. Ainsi, si son temps de réflexion est limité à 5 secondes, il examinera par exemple le jeu jusqu'au niveau 2 en 1/100éme de seconde, jusqu'au niveau 3 en 1/10ème de secondes, jusqu'au niveau 4 en une seconde, commencera l'examen du niveau 5 et l'arrêtera faute de temps. Il aura alors eu le temps d'examiner plus à fond la meilleure solution de niveau 4, la jouera si elle est toujours bonne, jouera la seconde si ce n'est plus le cas (en fait, il préférera alors souvent réexaminer le niveau 4 en éliminant la première solution, car la seconde solution, lorsqu'on a procédé à un élagage alpha-bêta, n'a pas été vue à fond, et n'est pas forcément le véritable deuxième meilleur choix ; cela lui prendra donc une seconde de plus).
Ceci permet à l'ordinateur de vous répondre dans le temps indiqué (par exemple 50 coups en 2 heures). Vous comprendrez donc qu'un programme muni de ce perfectionnement joue différemment selon l'ordinateur sur lequel vous l'installez. Ainsi, placé sur un vieux PC 8086, tel programme vous parait mauvais lorsqu'il réfléchit moins d'une minute. Placé sur un 486 DX4-100, 60 fois plus rapide, vous obtenez la même qualité de réponse en une seconde, et si vous le laissez réfléchir une minute par coup, comme sur l'ancien, le niveau est celui anciennement obtenu en une heure. Mieux encore, sur un Pentium III 1000, 40 fois plus rapide encore, vous obtenez en une minute le résultat obtenu en 40 heures sur le 8086 !
Si votre ami vous dit qu'il bat le programme T..., alors que celui-ci vous flanque une pâtée à chaque match, demandez-lui donc sur quel type d'ordinateur il s'entraîne !
- La recherche sur temps adverse
Quand vous jouez contre un adversaire, vous profitez généralement de son temps de réflexion pour réfléchir de votre côté. Certains programmes savent en faire autant, ce qui leur permet, si leur gestion du temps est bien faite (et en particulier s'ils sont munis du perfectionnement présenté ci-dessus) d'avoir le plus souvent examiné la réponse de l'adversaire et les contre-réponses possibles avant que l'adversaire n'ait joué. Ceci permet ensuite, dans le même temps, d'examiner plus loin l'arbre des solutions.
Essayons maintenant de faire un bilan de tout ce que nous avons appris du jeu des ordinateurs, et de voir la démarche globale qu'ils utilisent lorsqu'ils sont munis de tous les algorithmes présentés :
- l'ordinateur examine l'arbre des solutions jusqu'au niveau N,
- au départ de chaque branche, il regarde si la solution a déjà été examinée,
- il vérifie que la solution conduisant à cette branche n'est pas absurde (sacrifice inutile),
- il fait une évaluation statique de la position obtenue à chaque extrémité de la branche,
- il remonte cette solution aux niveaux supérieurs par la méthode du minimax,
- il examine s'il peut effectuer à chaque niveau un élagage alpha-bêta,
- ayant examiné tout l'arbre au niveau N, il ordonne les solutions obtenues,
- il recommence ce travail au niveau N+1,.....
- et ainsi de suite, jusqu'à ce que le temps qui lui a été imparti soit atteint,
- il joue la solution qu'il a retenue comme la meilleure dans sa recherche.
- il poursuit sa recherche pendant que l'adversaire réfléchit, de façon à être prêt quand son tour viendra, sans handicaper son temps de réflexion.
Voilà, cette série d'articles est terminée, il ne vous reste plus qu'à battre votre ordinateur maintenant que vous connaissez ses forces et ses faiblesses, et, pourquoi pas, à écrire un petit programme vous-même, qui vous serve d'adversaire les jours où le club est fermé.
Bibliographie :
A. K. Dewdney : Récréations informatiques, les ordinateurs qui jouent aux dames ; dans Pour la Science, Novembre 1984 - (N.B. : il s'agit ici de checkers et non pas de dames européennes).
J.L. Lauriere : Intelligence artificielle, résolutions de problèmes par l'homme et la machine ; Eyrolles 1987.
David Levy : Les jeux et l'ordinateur ; série de 20 articles dans L'Ordinateur Individuel, n°16 (avril 1980) à 35 (mars 1982).
David Levy : Chess and Computers, Bastford, London 1976.
Jonathan Schaeffer, Norman Treloar, Paul Lu and Robert Lake : Man versus machine for the World Checkers Championship ; dans A.I. Magazine, summer 1993.
Fédération Française d'Othello, BP 147, 75062 Paris CEDEX 02. Cette fédération possède une importante documentation sur le sujet, gracieusement mise à ma disposition pour l'écriture de cette série d'articles (merci en particulier à Bruno de La Boisserie).
* Incrémenter une variable signifie augmenter sa valeur d'un pas déterminé (le programme incrémente le niveau d'une unité lors de chaque demi-coup).