La démarche dynamique
L'objectif de cette démarche est d'examiner, au-delà de la situation actuelle, ce qui peut se passer dans le futur. L'idéal est de trouver, parmi les chemins possibles, celui qui mène à une victoire, imparable par l'adversaire.
Nous avons vu que pour l'instant l'ordinateur ne peut pas atteindre cet idéal dès le début, et doit se contenter de regarder dans un avenir limité.
Nous allons tenter de bien comprendre la démarche en suivant tout d'abord le raisonnement d'un programme un peu limité (pour ne pas dire demeuré). Pour se faire, nous allons représenter les choix possibles par un "arbre", et ne m'en veuillez pas si cet arbre a la tête en bas et le tronc en haut, c'est comme cela que les informaticiens (qui connaissent sans doute mal la nature) se les représentent. Ils sont d'ailleurs si incultes qu'ils appellent racine le sommet (la base du tronc) et noeud chaque départ de branche. Dans le cas représenté ci-dessous par le schéma n°1, il n'y a d'ailleurs qu'un noeud, confondu avec la racine.
schéma n° 1
Examinons cet arbre. L'ordinateur est dans une position P0. Il a n possibilités de jeu. La première possibilité le conduit à la position P1, la seconde à la position P2, .... et la nième à la position Pn.
Il "imagine" qu'il joue le premier pion, pour se retrouver dans la position P1. Il place alors dans sa mémoire tous les pions conformément à cette position (mais, bien sûr, il ne montre rien de cela sur l'écran) et il applique à cette position l'évaluation statique que nous avons présentée dans le précédent article. Il trouve A1. Effectuant la même démarche pour la deuxième possibilité, il trouve une valeur A2, ainsi de suite jusqu'à la valeur An de la Nième possibilité. Il compare alors ces valeurs A1, A2,..An, regarde laquelle est la plus élevée (c'est à dire la plus favorable pour lui), et choisit donc de la jouer.
Nous avons fait là une démarche dynamique de premier niveau, c'est à dire que nous avons étudié un organigramme s'arrêtant au premier demi-coup. J'ai qualifié notre programme d'un peu limité, car il est évident qu'un joueur, même mauvais, poussera plus loin la réflexion et se demandera quelles sont les réponses possibles à chaque mouvement.
Nous allons donc aller un peu plus loin dans la réflexion.
Schéma n° 2
Nous voici devant un organigramme de deuxième niveau (schéma n° 2), ou chaque possibilité P est suivie de diverses possibilités Q de réponse.
Les points P et Q, d'où partent ou peuvent partir des branches de l'organigramme sont les noeuds dont nous avons déjà parlé (ils en ont d'ailleurs la tête).
L'ordinateur va évaluer chacune des positions obtenues en Q11,..Q1m,Q21,..Q2r,...,Qn1,..Qns. Vous voyez que cela fait déjà beaucoup d'évaluations statiques au niveau 2.
Il convient bien sûr d'aller plus loin, et d'envisager la réponse de l'ordinateur à son adversaire, puis de l'adversaire à l'ordinateur, etc..., et on augmente ainsi la taille de l'organigramme de 2 niveaux (celui de l'ordinateur et celui de l'adversaire) par coup.
L'organigramme prend rapidement des proportions gigantesques. Ainsi, si une moyenne de 10 possibilités par niveaux peut-être retenue, le total de positions à évaluer est de :
niveau 1 : 10
niveau 2 : 100
niveau 3 : 1000
niveau 4 : 10000
niveau 5 : 100000
niveau 6 : 1 million
niveau 7 : 10 millions
niveau 8 : 100 millions etc...
Vous voyez qu'à ce rythme pourtant modéré (10 possibilités par demi-coup), on atteint le million de possibilités en 6 niveaux, c'est à dire en 3 coups, et le milliard en 9 niveaux (4 coups 1/2).
Il faudra visiblement agir avec méthode (l'ordinateur a de la mémoire, mais il vaut mieux éviter de lui faire retenir et comparer des milliards de chiffres) et aussi envisager de faire de l'élagage dans cet arbre.