headlogo

 La programmation des jeux

Jean-Marc Alliot — Thomas Schiex

1.1  Introduction

Les jeux, activité futile en apparence, ont toujours fasciné les informaticiens1. Ainsi, Babbage2 avait envisagé de programmer sa machine analytique pour jouer aux échecs, Claude Shannon3 décrivit en 1950 les rudiments d’un programme d’échecs, comme le fit également Alan Mathison Turing. Dès les débuts de l’IA, les premiers chercheurs se lancèrent dans la réalisation de programme de jeux4. Ainsi, un des tous premiers programmes de Simon, Newell, Shaw fut un programme de jeux d’échecs et Arthur Samuel écrivit dans les années 50 un programme de jeu de dames américaines.

Pourquoi cette fascination des informaticiens pour le domaine des jeux ? Tout d’abord parce qu’il semble intuitivement (et inconsciemment) que la pratique de jeux intellectuels soit le propre de l’homme. De plus, tout jeu apparaît un peu comme un champ clos de tournoi au Moyen Âge : chacun est astreint à respecter des règles strictes et précises, et ne peut l’emporter que grâce à sa valeur et à son habileté. La victoire et la défaite sont sanctionnées clairement et sans appel possible. Réaliser une machine qui joue aussi bien qu’un homme, voire mieux, << prouverait >> l’intelligence (ou la supériorité) des ordinateurs, et serait apparue comme une grande réussite pour l’IA, du moins à ses débuts.

Enfin, comme le dit Donald Michie :

<< La recherche sur le jeu d’échecs est le champ le plus important de la recherche cognitive5. Les échecs seront pour nous ce que la drosophile6 a été pour les généticiens : un moyen simple et pratique de développer de nouvelles techniques. >>

Sur le plan technique, le domaine des jeux est très << spécifiable >> au sens informatique du terme : les règles sont généralement simples, et surtout les interactions avec le monde extérieur parfaitement nulles : il s’agit d’un micro-monde totalement clos, et donc aisément accessible (en apparence) à un programme d’ordinateur. D’autre part, les informaticiens pensaient (plus perfidement) que sa puissance de calcul devrait donner, dans un univers aussi restreint, un avantage considérable à l’ordinateur.

Les choses ne se passèrent pas aussi facilement. Il fallut rapidement distinguer les jeux très simples (morpion) où une analyse exhaustive est possible, des jeux plus complexes comme les dames ou les échecs qui demandent des algorithmes spécifiques et des méthodes heuristiques de recherche, ou encore des jeux à information partielle comme le bridge ou le poker qui demandent en plus des raisonnements de type probabiliste.

Nous allons dans ce chapitre faire un tour d’horizon des techniques de programmation des jeux, et examinerons en détail trois exemples : Othello, les échecs et le bridge. Ces exemples nous permettront d’introduire quelques principes supplémentaires importants de la théorie moderne de la programmation des jeux.

Les joueurs (surtout d’échecs) ayant été des sujets d’études pour les psychologues, nous présenterons quelques-uns des résultats les plus intéressants, résultats qui sont d’autant plus significatifs qu’ils dégagent des facteurs communs à presque toutes les activités humaines.

1.2  Principe minimax (négamax)

Les programmes de jeux à deux joueurs et à information totale utilisent des techniques de représentation semblables à celles que nous avons vues dans le paragraphe précédent : espace d’états et arbres ou graphes. On utilise également des systèmes de production pour générer les états. En revanche, du fait de la présence de deux joueurs ayant des objectifs antagonistes (et non plus identiques), la recherche dans ces arbres7 ne peut se faire en recourant à des algorithmes du type A*.

La méthode générale utilisée pour ces jeux est la suivante : à partir d’une position (ou état) donnée, on génère l’ensemble des positions (ou états) que l’ordinateur peut atteindre en jouant un coup (niveau 1 de profondeur). À partir de chacune de ces positions du niveau 1, on génère l’ensemble des positions que l’adversaire peut à son tour atteindre (niveau 2). On peut alors recommencer l’opération aussi longtemps que le permet la puissance de calcul de l’ordinateur et générer les niveaux 3, 4, …, n. On construit ainsi un arbre de l’espace d’états du problème. Il est clair qu’il est impossible, dans la plupart des jeux, de générer l’ensemble de l’espace d’états du problème. Ainsi, aux échecs, le facteur de branchement8 est environ de 35 à chaque niveau de profondeur. Une partie d’échecs convenablement jouée devant contenir au moins une trentaine de demi-coups, le nombre d’états de l’espace d’états est alors de l’ordre de 3530=20991396429661901749543146230280399322509765625 : même l’ordinateur le plus puissant du monde ne pourrait le générer en un temps raisonnable (inférieur à l’âge de l’univers par exemple). On doit donc limiter l’exploration à une profondeur maximale de résolution. Lorsqu’on a atteint cette profondeur, l’ordinateur attribue à chacune des feuilles une valeur par l’intermédiaire d’une fonction d’évaluation. Cette valeur correspond à l’estimation de la position. Cette estimation peut se faire du point de vue d’un joueur fixe (convention minimax) ou du joueur qui a le trait à cette profondeur (convention négamax). Il doit alors, à partir du niveau 0 (la racine), jouer le coup de niveau 1 qui lui garantit le gain maximal contre toute défense de son adversaire, en supposant que celui-ci utilise également une stratégie optimale, c’est-à-dire qu’il joue lui-même à chaque coup le gain qui lui garantit le gain maximal contre toute défense. Ce mécanisme est appelé principe minimax9.

Nous allons détailler les deux phases principales de la résolution : la fonction d’évaluation des états terminaux et les algorithmes de recherche.

1.2.1  Fonctions d’évaluation

La fonction d’évaluation tente d’associer à une position une valeur estimant la qualité de la position pour un des deux joueurs. Les fonctions d’évaluation furent étudiées très tôt. Les premières proposées furent évidemment les plus simples. Aux dames par exemple, on peut effectuer la différence entre le nombre de ses pions et le nombre de pions de l’adversaire. Il est clair qu’une fonction heuristique élaborée permet de mieux jouer : si j’inclus dans ma fonction d’évaluation des notions d’attaque et de défense de pions, j’améliore mon niveau de jeu. En revanche, plus la fonction est élaborée et plus il faut de temps pour la calculer, ce qui limitera la profondeur d’exploration de l’arbre. Nous examinerons plus en détail les fonctions d’évaluation en étudiant la programmation des échecs et d’Othello.

1.2.2  Algorithme minimax

L’algorithme minimax10 est un algorithme de type exploration en profondeur d’abord comme nous les avons décrits au chapitre précédent. Il implante le principe minimax que nous avons évoqué. Le jeu comporte deux joueurs : O (l’ordinateur) et H (son adversaire). Une fonction d’évaluation h est chargée d’évaluer la qualité d’une position de jeu terminale (position de profondeur maximale ou sans descendance) du point de vue de O (par exemple). À chaque niveau où O a le trait, il peut choisir son coup et choisira donc celui de valeur maximale pour lui, on parle de nœud de type Max et du joueur Max. À chaque niveau où H a le trait, O va supposer que l’adversaire essaie de le mettre en mauvaise posture (minimiser ses gains) et choisira donc le coup de valeur minimale pour O (nœud de type Min, joueur Min). Ce n’est que sur les feuilles que l’on peut directement appliquer la fonction d’évaluation h. Sinon, on s’appuie sur une écriture récursive. L’algorithme, qui travaille en profondeur d’abord et jusqu’à la profondeur n, ne stocke jamais plus de n positions à la fois. En effet, il commence par générer une branche complète. Il évalue alors la feuille terminale et marque le sommet n−1 avec cette valeur. Il repart alors de la position de niveau n−1 et génère la feuille suivante (niveau n). Il utilise l’évaluation de cette feuille pour modifier le marquage du niveau n−1, et répète l’opération jusqu’à ce qu’il ait généré toutes les feuilles de niveau n issues de cette position de niveau n−1. Il utilise alors la valeur de ce niveau n−1 pour marquer le niveau n−2, remonte à la position du niveau n−2 et génère la position de niveau n−1 suivante, et continue le processus jusqu’à ce que toutes les feuilles et tous les niveaux aient été générés.

Une convention simplificatrice (du moins pour le programmeur) consiste à considérer qu’on évalue la qualité d’une position non pas du point de vue d’un joueur fixe donné (joueur racine) mais du point de vue du joueur qui a le trait sur cette position. La fonction heuristique doit évidemment être modifiée en conséquence. Dans tous les cas, que ce soit O ou H qui ait le trait, le raisonnement sera le même : pour évaluer le mérite d’un nœud du point de vue du joueur qui a le trait, en connaissant le mérite des positions filles (du point de vue de l’adversaire, qui a le trait sur ces positions), on considère le coup qui maximise (car on veut gagner) l’opposé des mérites des positions filles (car elles ont été évaluées par l’adversaire). Dans tous les cas, la valeur d’un nœud est simplement le maximum des opposés de la valeur des fils. L’écriture de la fonction récursive s’en voit simplifiée. On parle de convention négamax.

Un exemple de parcours par un algorithme minimax est fourni sur la figure 1.1.


Figure 1.1: Parcours minimax d’un arbre de jeu

On constate que l’algorithme minimax doit complètement décrire l’arbre pour fournir une solution, ce qui, on le verra, est souvent excessif. L’algorithme alpha-beta11 est une amélioration de l’algorithme minimax qui réalise un élagage de certaines branches qu’il est inutile de visiter.

1.2.3  Algorithme alpha-beta

Examinons l’arbre de la figure 1.2, alors que l’algorithme minimax a déjà parcouru les deux premières branches de la racine, et va s’engager dans la troisième et dernière branche. On sait alors que la racine a une valeur au moins égale à 3 puisqu’un des nœuds fils a déjà été évalué à 3 et que le nœud racine est de type Max. Lorsque, durant l’exploration de la troisième branche, on évalue la première feuille, celle-ci retourne la valeur 1. Son père, qui est un nœud Min, ne va pas pouvoir dépasser la valeur 1, ceci quelles que puissent être les valeurs des deux fils encore inexplorés. Or, pour modifier la valeur de la racine, et donc le coup à jouer, il faudrait que ce nœud dépasse la valeur 3, puisque la racine est de type Max. Les deux feuilles restantes sont donc inintéressantes et ne seront pas explorées par alpha-beta .

De façon plus synthétique, lorsque dans le parcours de l’arbre de jeu par minimax il y a remise en cause de la valeur d’un nœud, si cette valeur atteint un certain seuil, il devient inutile d’explorer la descendance encore inexplorée de ce nœud.

Il y a en fait deux seuils, appelés pour des raisons historiques, alpha (pour les nœuds Min) et beta (pour les Max) :

Ceci nous amène à l’énoncé de l’algorithme alpha-beta qui maintient ces deux valeurs durant le parcours de l’arbre (cf. Algorithme ??). Lors de son utilisation, on l’appellera par AlphaBeta(Racine,−∞,+∞).

Une définition beaucoup plus concise, mais peut-être moins intuitive, peut être obtenue en utilisant la convention négamax ; il devient alors inutile de distinguer les nœuds Min des nœuds Max (cf. Algorithme ??). Cet algorithme calcule alors la valeur négamax de la racine qui est, au signe près, égale à sa valeur minimax.


Figure 1.2: Parcours alpha-beta d’un arbre de jeu

L’algorithme est d’autant plus efficace que l’on parcourt l’arbre << de la bonne façon >>. Quand le niveau est maximisant, il faut examiner d’abord les coups qui ont le plus de chance de générer des positions à forte valeur d’évaluation et réciproquement. Nous verrons dans la suite de ce chapitre comment réaliser de tels mécanismes. Si l’arbre est parcouru exactement dans le bon ordre, le nombre de feuilles examinées est environ 2 √NN est le nombre de feuilles total de l’arbre, alors que l’algorithme minimax examine, lui, les N feuilles.

1.3  L’algorithme SSS

Il s’agit d’un algorithme relativement peu connu, en tous cas nettement moins connu que l’algorithme alpha-beta . Il a pourtant été démontré qu’il lui est théoriquement supérieur12, dans le sens où il n’évaluera pas un nœud si alpha-beta ne l’examine pas, tout en élaguant éventuellement quelques branches explorées par alpha-beta . Cette qualité supplémentaire se paie, SSS étant un gros consommateur de mémoire. [Stratégie] Étant donné un arbre de jeu J, on appelle stratégie ou sous-arbre solution pour le joueur Max , un sous-arbre de J qui :

Une stratégie indique au joueur Max ce qu’il doit jouer dans tous les cas. S’il s’agit d’un nœud Max , il a toute liberté de choix et jouera donc le coup indiqué par la stratégie. Si c’est un nœud Min, la stratégie contient tous ses fils et envisage donc toutes les réponses éventuelles de l’adversaire. Si Max respecte une stratégie, il est assuré d’aboutir à une des feuilles de la stratégie. Si l’on se place dans le cas habituel où l’arbre de jeu est développé jusqu’à une profondeur n, le mérite des positions terminales étant estimé par une fonction d’évaluation, la valeur d’une stratégie pour Max est donc le minimum des valeurs des feuilles de cette stratégie, gain assuré contre toute défense de Min. Le but de SSS est d’exhiber la stratégie de valeur maximum pour Max . Sa valeur sera, par définition, la valeur minimax de l’arbre J. [Stratégie partielle] Étant donné un arbre de jeu J, on appelle stratégie partielle pour le joueur Max , un sous-arbre de J qui:

Une stratégie partielle P représente implicitement l’ensemble des stratégies complètes auxquelles on peut aboutir en développant P via :

Toutes les stratégies complètes représentées par une stratégie partielle partagent les nœuds de la stratégie partielle, et en particulier, elles partagent les nœuds terminaux sur lesquels on a appliqué la fonction d’évaluation. La valeur d’une stratégie étant égale au minimum de la valeur de ses feuilles, la valeur d’une stratégie partielle constitue une borne supérieure (i.e., une estimation optimiste) de la valeur des stratégies complètes qu’elle représente.

L’algorithme SSS explore un espace d’état dont chaque nœud est une stratégie partielle, en utilisant une approche meilleur d’abord avec une heuristique minorante qui sera la valeur des stratégies partielles et qui garantit l’optimalité. Il ajoute un raffinement permettant d’éviter le développement de certaines stratégies partielles dont on peut démontrer l’absence d’intérêt.


Figure 1.3: SSS et arbre de jeu

Considérons par exemple l’arbre de jeux de la figure 1.3 et appliquons un meilleur d’abord avec une heuristique égale à la valeur des stratégies partielles (valeur de +∞ si la stratégie ne contient pas de nœud terminal). Dans la suite, nous décrirons une stratégie partielle par un couple formé de l’ensemble des nœuds qu’elle contient et de sa valeur estimée. Nous désignerons par G la liste des stratégies partielles.

  1. G=(({1}, +∞ )). Il y a deux façons de développer la stratégie ({1}, +∞ ) : en ajoutant le nœud 2 ou le nœud 3. Cependant, toutes les stratégies complètes issues de 1 contiennent les nœuds 2 et 3 car le nœud 1 est de type Min . Afin d’éviter d’explorer deux voies menant à la même solution, nous commencerons systématiquement par le premier nœud dans l’ordre lexicographique.
  2. G=(({1,2}, +∞)). Le nœud 2 étant de type Max , le rajout des nœuds 4 ou 5 définit deux stratégies partielles distinctes qu’il nous faut envisager.
  3. G=(({1,2,4}, +∞ ) ({1,2,5}, +∞ )). On développe la première stratégie partielle.
  4. G=(({1,2,5}, +∞ ) ({1,2,4,8}, 27)). La stratégie ({1,2,5}, +∞ ) est passée en tête.
  5. G=(({1,2,4,8}, 27) ({1,2,5,10}, 17)). Il faut maintenant affiner l’estimation de la stratégie partielle ({1,2,4,8}, 27). Les différents nœuds envisageables sont 9 et 3. On choisit 9.
  6. G=(({1,2,4,8,9}, 21) ({1,2,5,10}, 17)). À ce point du développement, il faut noter que la stratégie complète optimale issue de 2 est connue. Il s’agit de ({1,2,4,8,9}, 21). On étend la première stratégie avec 3.
  7. G=(({1,2,4,8,9,3}, 21) ({1,2,5,10}, 17)). Le nœud 3 est un nœud Max , il nous faut considérer les deux nœuds 6 et 7.
  8. G=(({1,2,4,8,9,3,6}, 21) ({1,2,4,8,9,3,7}, 21) ({1,2,5,10}, 17)). Puis, on développe 12.
  9. G=(({1,2,4,8,9,3,7}, 21) ({1,2,5,10}, 17) ({1,2,4,8,9,3,6,12}, 13)). On passe à 14.
  10. G=(({1,2,5,10}, 17) ({1,2,4,8,9,3,6,12}, 13) ({1,2,4,8,9,3,7,14}, 9)). La stratégie ({1,2,5,10}, 17) est alors en tête. Or, elle contient la sous-stratégie (2,5,10}, 17) dont on sait, d’après la remarque faite au (6) qu’elle est sous-optimale. Il est donc inutile de l’explorer plus avant.

L’algorithme du SSS s’inspire de cette remarque. À partir du moment où une sous-stratégie optimale est établie (comme au point (6)), la stratégie optimale est marquée, et toutes les sous-stratégies sous-optimales supprimées de G. En voici la description précise. Nous noterons :

  1. f1(n) : le premier fils du nœud n ;
  2. fi(n) : un fils de n ;
  3. fr(n) : le frère suivant de n (quand il existe) ;
  4. p(n) : le père de n.

On dira qu’un nœud est résolu, si la stratégie complète issue de ce nœud a été déterminée. Un nœud qui n’est pas résolu est vivant. Il ne faut pas confondre par la suite nœud (lié à l’arbre de jeu) et état (lié à l’arbre d’exploration des stratégies).

L’algorithme (cf. Algorithme ??) traite le meilleur état courant (n,t,e) selon son type. Si l’état est marqué vivant, cela signifie que la meilleure stratégie issue du nœud correspondanten n’est pas encore encore connue et il faut continuer à la developper :

Si l’état (n,t,e) est marqué résolu, une stratégie complète optimale issue du nœud est connue et il faut faire remonter l’information :

Comme nous l’annoncions initialement, l’algorithme du SSS est supérieur à alpha-betafootnoteIl faut pour cela que les deux algorithmes développent le même arbre, dans un ordre comparable. Ceci nécessite, dans le cas de l’insertion dans G de deux nœuds de même valeur, de mettre en première position le nœud exploré en premier par alpha-beta et entraîne l’emploi de finesse de programmation (ordonnancement fixe des nœuds…) qu’il est inutile de pratiquer lorsqu’on désire employer SSS pour autre chose qu’une comparaison à alpha-beta .. Récemment, un algorithme paramétrable sur la quantité de mémoire (longueur maximum de la liste G) qu’il peut utiliser — l’IterSSS* — a été exhibé [BB86]. Il permet d’obtenir des performances variant entre celles d’alpha-beta (mémoire minimum) et de SSS (mémoire suffisamment importante). Le tableau suivant indique les performances de cet algorithme en pourcentage de nœuds visités sur différents arbres uniformes de facteurs de branchements et de profondeurs variables :

ProfondeurBranchementalpha-betaSSSlongueur GIterSSS
15212,478,5912,4
    6410,36
    1929,37
    2568,5
6516,5111,481315,49
    6312,68
    9512,6
    12511,48
10310,446,441110,11
    1227,75
    2436,44

1.4  L’algorithme Scout

Nous décrirons rapidement l’algorithme Scout , élaboré par J. Pearl [Pea90] comme outil théorique. Son efficacité est, en général, inférieure à celle d’alpha-beta , pour une consommation mémoire du même ordre. Il peut toutefois lui être supérieur.

Scout repose sur une idée fort simple : si l’on disposait d’un moyen efficace pour comparer (sans nécessairement la déterminer) la valeur minimax d’un nœud à une valeur donnée, une quantité importante de recherche pourrait être évitée. Considérons par exemple un nœud Max n, ayant deux fils : f1, dont la valeur ν est connue, et f2. Si l’on sait que la valeur de f2 est inférieure à ν, il est inutile d’explorer la branche de f2.

Scout s’appuie donc sur deux procédures simples : la première, appelée Test  permet de vérifier si la valeur d’un nœud n est strictement supérieure (ou supérieure ou égale) à une valeur donnée v. Nous continuerons à désigner par h la fonction heuristique.

La seconde, Eval, utilise Test et applique le principe donné plus haut pour calculer la valeur minimax d’un arbre de jeu. Elle prend en paramètre un nœud n.

Il pourrait sembler que, du fait de la redondance éventuelle des évaluations, lorsque ScoutTest ne permet pas la coupure, Scout devrait être très inférieur à alpha-beta, voire même à minimax. Une étude mathématique du comportement asymptotique de Scout montre un comportement identique à alpha-beta pour des profondeurs élevées. Dans le cas de certains jeux (jeu de Kalah), il peut même lui être supérieur (jusqu’à 40% d’amélioration à profondeur 5). Bien qu’aucune preuve ne vienne l’appuyer, il semble que Scout soit plus particulièrement adapté aux arbres profonds, ayant un facteur de branchement faible14.

Le tableau suivant reprend l’ensemble des algorithmes de jeu présentés (minimax, alpha-beta , SSS , Scout ) et indique les performances relatives de chacun d’eux,

sur le jeu de l’Othello pour différentes profondeurs p.

pminimaxScoutalpha-betaSSS
13 – 0,374 – 0,453 – 0,363 – 0,36
214 – 1,3821 – 2.0913 – 1,411 – 1,19
361 – 6,045 – 5,037 – 3,935 – 3,7
4349 – 32,5246 – 23,7150 – 14,7795 – 10,0
52050 – 185,7615 – 61,6418 – 41,4292 – 19,2
613773 – 1213,52680 – 254,51830 – 172,91617 – 117,3

On notera les mauvaises performances de Scout à faible profondeur (plus mauvais que le simple minimax) et la nette supériorité de SSS . Il faut cependant noter que nous n’avons pu poursuivre les tests avec SSS au-delà de la profondeur 6 pour des raisons de place mémoire.

1.5  La pratique après la théorie

Les différents algorithmes et résultats présentés ci-dessus sont parfaitement intéressants mais ne sont plus utilisés aujourd’hui sous cette forme. De nombreuses améliorations ont été apportées et il est indispensable de les connaitre pour espérer écrire un programme performant.

1.5.1  Contrôle du temps et alpha-beta

On doit dans la pratique s’intéresser au système de contrôle du temps. Le programme dispose d’un temps total pour jouer l’ensemble de la partie. Il serait possible d’implanter deux techniques pour que l’ordinateur ne consomme pas trop de temps sur un coup. On pourrait tout d’abord accorder un temps donné pour jouer le coup et estimer la profondeur maximale que l’on peut atteindre sans dépasser ce temps. Cette solution présente un inconvénient : il est très difficile de trouver une fonction qui estime le temps que prendra un calcul à une profondeur donnée. On risque de se retrouver en dépassement de temps. On préfère donc utiliser une méthode un peu différente. On fait fonctionner l’algorithme alpha-beta à un niveau minimal (3 par exemple). On compare le temps utilisé avec le temps disponible. S’il reste du temps, on relance la recherche au niveau 4, puis au niveau 5…Cette méthode (habituellement référencée sous le nom de Depth First Iterative Deepening [Kor85, SA78, MS90]) présente un autre avantage. On constate aisément qu’un algorithme alpha-beta est d’autant plus efficace qu’il évalue en premier les meilleurs coups. On profite donc du résultat de la recherche à la profondeur n pour classer les coups et faire examiner en premier au programme les meilleurs coups de la profondeur n lorsqu’il effectue la recherche en profondeur n+1.

1.5.2  Tables de transposition

Le principe des tables de transposition est le suivant : pour chaque position rencontrée dans la recherche, l’algorithme minimax retourne une évaluation. Il s’agit de conserver dans une table la valeur de chacune des positions rencontrées de façon à pouvoir réutiliser directement cette valeur lors des recherches suivantes. Les informations stockées pour une position sont représentées sur la figure 1.4.


positionévaluationmeilleurdistance à la
  coupposition terminale
Figure 1.4: Informations stockées dans une table de transposition

Nous allons voir cela sur un exemple pratique. Soit l’arbre minimax représenté sur la figure 1.5. Les informations stockées pour la position P1 sont représentées figure 1.6.


Figure 1.5: Exemple d’arbre minimax


positionévaluationmeilleurdistance à la
  coupposition terminale
P120Gauche2
Figure 1.6: Valeurs stockées pour la position P1 de l’arbre minimax représenté sur la figure précédente

Supposons que dans une recherche future l’ordinateur rencontre à nouveau la position P1. Si la distance à la racine de P1 est plus grande dans la table de transposition que dans la recherche actuelle, l’ordinateur ne poursuivra pas l’évaluation : il se contentera de recopier la valeur stockée dans la table de transposition. En revanche, si la distance à la racine est plus petite dans la table de transposition que dans l’évaluation courante, le programme terminera normalement l’évaluation de la position et remplacera l’ancienne évaluation de la table de transposition par celle qu’il aura calculée, puis stockera la nouvelle valeur de la distance à la racine.

Si les tables de transposition fonctionnaient suivant ce principe, un problème se poserait rapidement : comment stocker tous les éléments de la table de transposition (et en particulier la position de chacune des pièces sur l’échiquier) dans la mémoire du calculateur, et comment retrouver rapidement une position. On utilise une structure de données connue sous le nom de table de hachage16 ; au lieu d’utiliser la position en entier pour retrouver la valeur de cette position, on utilise un nombre qui caractérise cette position. Nous allons examiner brièvement sur un exemple une méthode permettant de construire ce nombre pour une position aux échecs.

On construit une table contenant, pour chaque pièce de chaque couleur sur chacune des cases de l’échiquier, un nombre binaire de 32 chiffres choisi de façon aléatoire (voir exemple table 1.1). Pour une position donnée, on construit alors le code de hachage en faisant un << ou-exclusif17 >> entre chacune des valeurs associée à chacune des pièces. Ainsi, pour la position représentée sur la figure 1.7, la valeur sera :

Tour blanche en a110101011110110110101010110101101
Roi blanc en e111010110101001001010001011010110
Roi noir en e800100101010110110100100010101000=
 01011000001001001011111111010011

Le grand intérêt de cette méthode est qu’elle permet de calculer la valeur de hachage d’une position après déplacement d’une pièce, simplement en ajoutant à la valeur de hachage de la position originale le code de la pièce sur la nouvelle case et le code de la pièce sur l’ancienne case. C’est une propriété du << ou-exclusif >>.

Un des problèmes des tables de hachage est que rien ne nous garantit que deux positions différentes ne vont pas avoir la même valeur de hachage, ce qui risquerait de nous amener à des conclusions fausses sur la valeur d’une position. Cette probabilité de collision est d’autant plus faible que la taille de la table est importante.

Il reste maintenant à stocker un élément de la table de hachage. On ne peut utiliser la valeur de hachage comme index de tableau car elle est généralement trop grande (un tableau avec un index sur 32 bits occuperait quatre milliards de positions mémoire, ce qui est déraisonnable). On peut par exemple utiliser les 16 premiers bits de la valeur de hachage comme index du tableau. On prend alors le risque que des positions aient des valeurs de hachage différentes et le même index. Il y a alors conflit. Il existe différentes méthodes pour gérer ce type de problème, la plus simple étant de remplacer la plus ancienne des deux valeurs par la plus récente18.

1.5.3  alpha-beta avec mémoire

La méthode des tables de transposition permet d’améliorer de façon spectaculaire la vitesse de recherche d’un calculateur, car elles permettent l’implantation de la version la plus classiquement utilisée de l’alpha-beta , l’alpha-beta avec mémoire. Sa structure est un petit peu plus complexe que celle de l’alpha-beta standard, car il fait appel aux tables de transposition pour stocker les bornes supérieures et inférieurs des positions déjà évaluées. Nous le présentons ici dans sa version la plus aisée à comprendre (algorithme ??).

On peut aisément se demander quel peut-être l’intérêt d’un tel algorithme. Il est de deux ordres. D’une part, dans les jeux où certaines positions se présentent plusieurs fois dans l’arbre, il permet de ne pas recalculer le nœud comme indiqué précédemment. Mais son principal avantage apparait lorsqu’on l’utilise avec des fenêtres de recherche réduite, en particulier avec les algorithmes de la famille MTD(f).

1.5.4  Fenêtre réduite et MTD(f)

On se rappelle que lors du début de l’algorithme alpha-beta, les bornes alpha et beta sont initialisées à + ∞ et − ∞. Or, dans 90% des positions, il est rare que la valeur d’une position évolue beaucoup. On peut donc initialiser les bornes alpha et beta à la valeur de la position courante ± є (ou є est une valeur bien choisie dépendant du jeu et/ou de la fonction d’évaluation). Ainsi, tous les coups dans l’algorithme alpha-beta qui seront en dehors de cette fenêtre seront immédiatement élagués. La méthode est efficace si l’hypothèse initiale est juste (c’est-à-dire qu’on ne peut effectivement pas gagner ou perdre plus de є). Si tel n’est pas le cas, on le détecte aisément car la valeur retournée est alors hors de la fenêtre initiale ]alpha , beta[. Il faut alors relancer l’algorithme en modifiant la fenêtre de recherche ; mais si l’on s’est donné la peine de stocker dans la table de transposition pour chaque position déjà exploré les informations acquises lors de la passe précédente on gagne un temps précieux en ne réexaminant pas certains nœuds.

C’est un poussant ce raisonnement à l’extrème, et en s’inspirant de l’algorithme Scout, qu’est né l’algorithme MTD(f) (algorithme ??).

Cet algorithme présente de nombreuses particularités qui le rendent particulièrement intéressant. Il emprunte en effet certains traits à la plupart des algorithmes que nous avons déjà rencontrés. Son principe est simple : il appelle autant de fois que nécessaire un alpha-beta pour construire un encadrement de la valeur de la position. Quand les deux bornes haute et basse se rencontrent, l’évaluation est terminée et la valeur de la position est connue. L’efficacité de l’algorithme vient de l’élagage violent qu’il effectue à chaque évaluation, car l’alpha-beta avec mémoire est appelé avec une fenêtre de taille 0. Il est d’autant plus efficace que la valeur du paramètre f dont dépend MTD(f) est proche de la valeur réelle de la position. On utilise donc en général comme valeur de f la valeur retourné par l’algorithme lors d’une itération précédente. Remarquons que la technique consistant à utiliser un alpha-beta avec une fenêtre de taille 0 est équivalent à la procédure TEST de l’algorithme SCOUT.

De récents travaux [PSDP96] ont montré d’autre part que MTD(+ ∞) était exactement équivalent à SSS*, c’est à dire qu’il développe les mêmes nœuds dans le même ordre, répondant en cela aux nombreuses questions qui se posaient depuis l’article fondateur de SSS*. On en déduit en particulier que SSS* est moins efficace que MTD(f) pour une valeur de f bien choisie.

1.5.5  Paralléliser un algorithme alpha-beta

Comme pour tous les programmes utilisant des techniques de recherche dans des arbres, la puissance de calcul est un facteur déterminant. Un moyen traditionnel d’augmenter cette puissance consiste à tenter de rendre l’exécution du programme parallèle, c’est-à-dire d’utiliser plusieurs machines (ou plusieurs processeurs) pour exécuter simultanément des parties du programme.

Il est clair que l’on peut aisément paralléliser un algorithme alpha-beta. En effet, il suffit de distribuer la recherche dans l’arbre sur l’ensemble des processeurs. Mais on ne peut pas le faire n’importe comment. On doit choisir entre quatre types de technique (nous retrouverons ce type de mécanisme lorsque nous parlerons de parallélisme en programmation logique) :

Système distribué contre système en étoile :
Dans un système en étoile19 un des processeurs, le processeur maître, est chargé de diriger la résolution. Ainsi, dans le cas qui nous intéresse, le processeur maître envoie à chacune des machines esclaves une position et lui demande de renvoyer sa valuation alpha-beta. Il peut, s’il le désire, interrompre le travail d’un processeur s’il estime ce travail inutile, à la suite d’informations qu’il aurait reçues d’autres processeurs. Ce type de mécanisme est simple à mettre en œuvre, car le contrôle de l’exécution reste séquentiel, toutes les des décisions étant prises par un seul processeur. D’autre part, le nombre d’informations transitant entre les processeurs reste relativement faible.

Dans un modèle totalement distribué, aucun processeur n’a de statut particulier. Chaque processeur choisit au départ une position à évaluer (au hasard et après un délai aléatoire différent de façon à limiter les conflits) et diffuse sur le réseau à l’intention des autres son choix. Au cours de la résolution, il diffuse également, à l’intention de tous les autres processeurs, l’ensemble des informations qui lui paraissent intéressantes (valuations alpha-beta de position par exemple). Ce type de modèle est plus fiable dans la mesure où la défaillance (ou l’absence) d’une machine est plus facilement surmontée. En revanche, il est beaucoup plus complexe à réaliser. En particulier, la gestion des conflits doit être faite avec soin : comment faire si deux processeurs se rendent compte qu’ils ont choisi la même branche ? Une méthode envisageable consiste à faire attendre chaque machine pendant une durée aléatoire, avant de leur faire choisir à nouveau une branche à évaluer. Enfin, un autre inconvénient est l’augmentation du débit des données qui va circuler sur le réseau de communications entre processeurs.

Grosse ou petite granularité :
20 Lorsque l’on distribue la résolution dans l’algorithme alpha-beta, on doit choisir le niveau à partir duquel chaque processeur va commencer une évaluation alpha-beta séquentielle classique. Si nous choisissons de faire commencer l’évaluation au niveau 1 de l’arbre (grosse granularité), nous ne pourrons pas utiliser plus de processeurs qu’il n’y a de positions différentes au niveau 1 (facteur de branchement). Ainsi, pour Othello, il y a en moyenne 16 coups jouables à chaque tour. Si nous disposons de n processeurs avec n>16, nous aurons en moyenne n−16 processeurs inemployés. Si nous distribuons la recherche à partir du niveau 2 (256 positions), nous serons en mesure d’occuper simultanément 256 processeurs. En revanche, le nombre d’informations qui circuleront sur le réseau sera beaucoup plus important et continuera à augmenter au fur et à mesure que nous rendrons la granularité plus petite.

Il faut donc choisir sa stratégie en fonction des capacités des machines et du réseau dont on dispose. Examinons en détail le fonctionnement d’un système à forte granularité :

  1. Au départ, la machine maître est la seule à connaître la position à évaluer (niveau 0). À partir de cette position, elle établit les 15 premières positions que l’on peut générer au niveau 1 et demande à chacun des processeurs esclaves de calculer la valuation alpha-beta pour une de ces positions.
  2. Chaque processeur esclave va, au fur et à mesure que l’évaluation de la position que lui a confiée la machine progresse, renvoyer à la machine maître les évaluations partielles au niveau 1. La machine maître note chacune des évaluations partielles pour chacun des processeurs, en sachant qu’une évaluation partielle de niveau 1 ne peut que diminuer (principe minimax).
  3. À un instant donné, une des machines esclaves termine la résolution de sa position et renvoie à la machine maître l’évaluation définitive de cette position de niveau 1. La machine maître effectue alors la séquence d’opérations suivante :
    1. Elle note ce coup comme le meilleur connu et cette évaluation comme la meilleure évaluation courante et l’appelle p0.
    2. Elle note que ce processeur est disponible.
    3. Elle ordonne à tous les processeurs dont l’évaluation partielle de niveau 1 est inférieure à p0 de s’arrêter : en effet, ils ne pourront trouver que des valeurs inférieures à leur valeur courante (principe alpha-beta-minimax). Elle note que tous ces processeurs sont disponibles.
    4. Elle répartit sur les processeurs disponibles les positions de niveau 1 encore non traitées (la 16ième, 17ième…).
  4. Chaque fois qu’une machine lui communiquera une évaluation partielle inférieure à l’évaluation p0 elle lui communique l’ordre de s’arrêter et lui donne à évaluer une des positions encore disponibles.
  5. Chaque fois qu’une machine lui envoie une évaluation définitive de niveau 1, et que cette évaluation est supérieure à p0, la machine maître répète les opérations ((a)…(d)).
  6. La machine maître poursuit cet algorithme jusqu’à ce que tous les processeurs esclaves soient arrêtés et que toutes les positions de niveau 1 aient été examinées.

Nous avons ainsi décrit une implantation parallèle de l’algorithme alpha-beta21.

1.5.6  Pour conclure?

La recherche dans le domaine des algorithmes de jeu est d’une richesse et d’une vigueur assez extraordinaire et nous n’avons fait qu’effleuré le domaine. Nous n’avons en particulier pas parlé des alternatives au paradigme minimax, comme les algorithmes de type B* ou BPIP (Best Play for Imperfect Player). On peut se reporter avec profit à l’excellente thèse de Jean-Christophe Weill, qui a de plus le grand mérite d’être en Français [Wei95].

1.6  Othello

Nous nous proposons de développer en détail les différentes phases de la programmation du jeu d’Othello. La programmation d’Othello22 doit être divisée en trois phases : l’ouverture, le milieu de partie et la fin de partie. Nous allons nous intéresser successivement à ces trois différents types de jeu.

1.6.1  Les ouvertures

Il existe dans le jeu d’Othello un certain nombre d’ouvertures répertoriées. Il s’agit de séquences connues que l’on doit systématiquement utiliser en début de partie, sous peine de se retrouver en position inférieure. Le jeu d’Othello étant beaucoup plus jeune que le jeu d’échecs, la théorie des ouvertures est beaucoup moins développée. On ne s’intéresse à l’heure actuelle qu’à des séquences allant jusqu’à six coups maximum. D’autre part, les séquences recommandées ne sont souvent choisies que pour des raisons statistiques (on sait que, dans un championnat du monde donné, les meilleurs joueurs ont eu leurs meilleurs résultats avec une certaine séquence : c’est donc qu’il s’agit d’une bonne ouverture).

Les ouvertures ne sont pas stockées sous forme de séquence de coups, mais sous forme de positions indexées. Cela signifie que l’ordinateur ne stocke pas des séquences de positions, chaque séquence correspondant à une ouverture, mais stocke séparément chacune des positions avec le coup à jouer si cette position se rencontre à un instant donné. Pourquoi cette méthode ? Simplement pour éviter que l’ordinateur ne se perde dans une interversion de coups. Afin de retrouver rapidement une position dans l’ensemble des positions stockées, on les indexe en général par un certain nombre de clés (nombre de pions de chaque couleur…).

Cette technique a été amélioré considérablement par Michael Buro pour son programme Logistello, qui est actuellement le meilleur programme mondial. Buro utilise des techniques tout à fait originales pour améliorer en permanence la bibliothèque de son programme. On pourra se reporter avec profit à [Bur97] pour plus de détails.

1.6.2  Les finales

Le jeu d’Othello est intéressant dans la mesure où il s’agit d’un jeu à information totale à nombre de coups précisément connus. On sait en effet que la partie se terminera au plus tard (et en général exactement) au 60ième demi-coup23. En fonction de la puissance de calcul disponible, il est possible de lancer une recherche exhaustive un certain nombre de demi-coups avant la fin (le 60ième coup). Dans ce cas, la fonction d’évaluation est extrêmement simple : il suffit de faire la différence entre son propre nombre de pions et le nombre de pions de l’adversaire. De plus, il s’agit d’une heuristique qui évalue parfaitement le caractère perdant ou gagnant de la position (évidemment !). L’algorithme de recherche est relativement original, puisque l’on considère que le plus efficace dans cet exercice est le NegaC*, un algorithme proche de MTD(f) mais pour lequel on recherche l’encadrement de la valeur de la position par bisection successive de l’intervalle [Wei95].

Cette caractéristique du jeu d’Othello explique en partie la force des programmes d’ordinateur : un humain est totalement incapable d’exécuter un calcul total sur une semblable profondeur sans commettre d’erreurs. Ainsi, un ordinateur jouant à Othello peut se retrouver dans une situation difficile une vingtaine de coups avant la fin de la partie et retourner (au propre et au figuré) complètement la position en sa faveur simplement par la force brute24.

1.6.3  Le milieu de partie

Le milieu de partie est le royaume de l’algorithme alpha-beta et de la fonction d’évaluation. Nous allons examiner en détail la construction d’une fonction d’évaluation trés simple pour Othello. Cette fonction sera une fonction statique dans la mesure où le programme n’est pas capable d’apprentissage. Nous allons nous apercevoir que la construction de la fonction n’est pas chose complètement triviale, même si le jeu est simple et le but raisonnable (il ne s’agit pas de construire un programme champion du monde).

Tout d’abord, on tente d’attribuer à chaque case du jeu une valeur tactique. Cette valeur tactique doit représenter l’intérêt qu’a l’ordinateur à occuper une case ou, au contraire, à la laisser à son adversaire. Une fonction d’évaluation élémentaire consisterait donc à additionner les valeurs des cases que l’on possède et à soustraire la valeur des cases que possède l’adversaire. Une possibilité de valuation des cases est donnée dans la figure 1.8.


500-15030101030-150500
-150-2500000-250-150
3001221030
100216162010
100216162010
3001221030
-150-2500000-250-150
500-15030101030-150500
Figure 1.8: Exemple de valuation de cases pour Othello

On peut rapidement justifier ce tableau en disant que la possession d’un coin est capitale, alors que les cases qui entourent le coin sont à éviter car elles donnent à l’adversaire accès au coin. La possession des cases centrales est importante, car elle augmente généralement les possibilités de jeu. Les bords sont également des points d’appui solides.

Une fois cette évaluation effectuée, il faut la corriger sur-le-champ. En effet, si nous possédons un coin, la valeur des trois cases environnantes doit être considérée comme positive puisqu’elles ne donnent plus accès au coin, qui est déjà occupé. De même, les cases du bord qui sont reliés au coin par une chaîne continue de pions de la même couleur sont beaucoup plus intéressantes car désormais imprenables. Un autre facteur important de la position à Othello est le nombre de cases libres contiguës à ses propres pions. Il faut essayer de le minimiser car plus ce nombre est petit et moins l’adversaire a, en général, de coups disponibles.

1.6.4  Othello et apprentissage

Le programme que nous venons de présenter garantit un niveau de jeu intéressant, mais est cependant très loin des meilleurs programmes d’Othello. Tous les meilleurs programmes utilisent aujourd’hui des techniques d’apprentissage qui peuvent être de plusieurs sortes. Ce type de mécanisme n’est pas nouveau, puisqu’il était déjà utilisé par Arthur Samuel [Sam59] dans son programme de jeu de dames.

La plupart des fonctions d’évaluation sont de la forme Σ citi où les ti sont les caractéristiques de la position et les ci les coefficients qui mesurent l’importance à accorder à telle ou telle caractéristique25. Au fur et à mesure de l’apprentissage, les coefficients ci doivent être modifiés de façon à enregistrer l’information acquise pendant les parties.

Comment modifier les coefficients ? Il est clair que l’on doit augmenter la valeur des coefficients qui prédisent correctement l’issue du coup et diminuer la valeur de ceux qui fournissent des informations incorrectes. Le problème dans un programme de jeu est qu’il faut être capable, après la partie, d’analyser les coups qui se sont révélés bons ou mauvais, de façon à modifier la fonction d’évaluation. On peut implanter ce mécanisme en supposant que toute séquence de coups qui a amené à une bonne situation est une bonne séquence et que les coefficients qui ont encouragé cette séquence doivent être renforcés et ceux qui tendaient à l’éviter, diminués (méthode de la carotte et du bâton). Quant à mesurer en quoi une situation est bonne, c’est facile lorsque l’on est proche de la fin de la partie (car on peut aisément faire des analyses exhaustives), mais en milieu de partie, on doit se fier à la fonction d’évaluation elle-même qui fournit, en quelque sorte, son propre feedback. Ainsi, à chaque coup, Arthur Samuel, dans son programme, comparait la valeur courante de la fonction d’évaluation Sc avec la valeur Sp affectée à cette position lors du calcul au coup précédent (soit deux demi-coups, et donc deux niveaux auparavant). Il en tirait alors les conséquences suivantes :

Il ne reste alors plus qu’à modifier les coefficients d’évaluation26.

Une autre technique classique consiste à faire jouer le programme contre une copie de lui-même avec certains coefficients de la fonction d’évaluation modifiés. Si la nouvelle copie l’emporte, alors on conserve la nouvelle valeur des coefficients, sinon on conserve l’ancienne et on essaie une autre modification.

L’apprentissage de base, consiste quant à lui à mémoriser, chaque fois que l’on effectue l’évaluation d’une position, la position ainsi que la valeur associée. Si par la suite, dans une recherche, cette même position est rencontrée, on ne tente pas de l’analyser avec la fonction d’évaluation mais on récupère la valeur stockée en mémoire, qui est évidemment plus précise puisqu’elle a elle-même été évaluée par une recherche alpha-beta profonde. L’inconvénient principal de cette méthode est qu’elle réclame de très importantes capacités de stockage.

La plupart des programmes d’Othello utilisent quand à eux un apprentissage sur des formes standards. Le principe en est simple : on estime (en simplifiant) que la valeur d’une position d’Othello ne dépend que de la structure des 4 bords, des 4 coins 3× 3 et du nombre de libertés des pions. On peut alors décider, par exemple, de stocker systématiquement tous les résultats de toutes les parties jouées, et en attribuer le mérite aux structures rencontrées sur les bords et dans les coins au cours de ces parties.

Un programme utilisant correctement de tels concepts devraient figurer dans les dix ou vingt meilleurs programmes mondiaux. Notons pour conclure que le problème de la suprématie homme/machine pour Othello a été réglé de façon à peu près définitive en 1997 où un match opposant Logistello au champion du monde humain Takeshi Murakami s’est terminé par le score sans appel de 6 à 0 pour le programme.

1.7  Les échecs

Les échecs sont considérés comme le jeu des Rois et surtout le Roi des jeux. Dès les débuts de l’IA, c’est sur les échecs que s’est porté l’effort le plus important et ce sont les échecs qui ont donné lieu à des luttes epiques que se sont livrés les meilleures équipes universitaires comme (hitech mené par Hans Berliner27, ou deep thought, mené par Feng-Hsiung Hsu28) devenus depuis deep blue avec le succès que l’on sait. Il faut sans doute craindre que la victoire de deep blue face à Gary Kasparov en mai 1997 n’ait des repercussions que l’on pourrait qualifier de néfastes : le plus grand défi que l’on s’était lancé (la victoire d’un programme sur le champion du monde humain dans le cadre de partie à cadence de tournoi et sur six parties) a été réalisé et il est probable que les efforts se porteront davantage dans d’autres directions. D’autre part, même si la lutte entre les plus importantes firmes commerciales restent réels, le niveau des programmes disponibles pour micro ordinateurs est maintenant tellement élevé qu’ils battent systématiquement 99% des joueurs. On accordera donc plus d’importance à la qualité de l’interface avec l’utilisateur qu’à la force pure du programme. Mais les grandes avancées liées aux échecs demeureront.

Les pères fondateurs de l’IA, Simon et Newell, menèrent, ainsi que le psychologue hollandais de Groot et le psychologue et Grand Maître soviétique Nicolaï Kroguious une analyse de la méthode de réflexion des grands champions d’échecs. Nous allons rapidement parler des résultats de ces études avant d’aborder les techniques de programmation proprement dites. Deux raisons à cela : tout d’abord les résultats mis en évidence par de Groot [Gro65] et Kroguious [Kro86] sont très intéressants car ils sont applicables à la plupart des raisonnements humains dans tous les domaines ; enfin, ces résultats n’ont en rien influencé les programmes d’échecs (du moins les meilleurs) qui utilisent des méthodes de raisonnement totalement différentes aujourd’hui, preuve qu’il est bien difficile d’appliquer des techniques humaines pour faire résoudre des problèmes à des machines.

1.7.1  Les ouvertures

La programmation de l’ouverture est certainement la chose la plus simple à réaliser. Les techniques à utiliser sont exactement les mêmes que pour la programmation des ouvertures pour Othello. Cependant, le nombre de positions aux échecs rend le problème un peu plus complexe. Il faut savoir que l’encyclopédie des ouvertures doit dépasser les 2000 pages.

Il s’agit plus d’un travail de bénédictin que de la réalisation exaltante d’algorithmes évolués. Notons une fois de plus la nécessité de ne pas stocker les séquences de coups, mais bien les positions en les indexant de façon correcte, afin de ne pas être trompé par une inversion de coups. Certains programmes se font encore duper. On peut aisément le vérifier avec la séquence suivante : e2e4 e7e6 g1f3 c7c5

Il suffit alors de demander à l’ordinateur le coup qu’il jouerait face à la position résultante. S’il répond immédiatement d4, c’est qu’il a reconnu l’inversion de coup qui a transformé une partie française en une sicilienne. La séquence classique pour atteindre cette position sicilienne est en effet : e4 c5 Cf3 e6. Le coup e6 en premier par le joueur noir fait au contraire croire à un ordinateur primaire que l’on va jouer une partie française, auquel cas il attend comme séquence standard : e4 e6 Cf3 d5

Ne trouvant pas cette séquence standard (c5 au lieu de d5), il est perdu s’il stocke ses ouvertures sous forme de séquences de coups et non sous forme de positions indexées, car il ne reconnaît aucune séquence standard et est incapable de reconnaître une position (sicilienne).

Une technique classique consiste, pour accélérer la recherche, à indexer la position sur le numéro du demi-coup où on peut la rencontrer. On peut, bien entendu, écrire un programme qui, connaissant les séquences d’ouverture, génère la structure de données appropriée pour faire de la reconnaissance de position, la réalisation d’une telle structure par un être humain étant réellement fastidieuse.

En fait, une technique plus efficace encore consiste à réaliser un programme qui utilise conjointement les deux méthodes : mémorisation des séquences d’ouverture pour une plus grande rapidité et mémorisation des positions pour la généralité. Il n’aurait recours à la seconde méthode que lorsque la première ne lui permettrait pas de conclure efficacement.

Hormis ces détails techniques, la programmation des ouvertures ne pose aucun problème difficile.

1.7.2  Les finales

Les finales furent longtemps le talon d’Achille des programmes d’échecs avant de devenir un de leur point relativement fort.

Quel problème avait-on à résoudre ? Les ordinateurs sont efficaces en milieu de partie en raison de leur formidable habileté tactique, liée à leur grande capacité de calcul et à leurs algorithmes de recherche efficaces. Mais dans une finale, la capacité à calculer doit être bien différente. Prenons un exemple trivial. Si nous sommes dans une finale Roi et pion contre Roi et pion, et que la disposition des pièces est la suivante : pion blanc en a2, Roi noir en g4, pion noir en h2, Roi blanc en h1 avec trait au blanc (figure


Figure 1.9: Effet horizon dans une finale

La partie peut être considéré comme terminée. En effet, le Roi noir ne peut empêcher le pion blanc d’aller à Dame en a8 et le pion noir en h2 ne peut aller à Dame, bloqué qu’il est par le Roi blanc en h1. C’est l’analyse que réalise immédiatement tout joueur, même débutant. Le bon coup est évidemment a4. Mais un ordinateur raisonnant avec un algorithme alpha-beta à profondeur fixe va considérer les choses différemment. Tout d’abord, il voit qu’il peut prendre le pion h2 sur le champ, et qu’en revanche s’il ne le prend pas, il ne pourra pas le prendre au coup suivant si les noirs jouent Th3, il y a donc manque à gagner. D’autre part, il lui faudrait analyser la position à 10 demi-coups de profondeur pour s’apercevoir que le pion blanc ne peut aller à Dame que s’il est avancé sur le champ. Cette profondeur étant déraisonnable pour beaucoup d’ordinateurs, il sera aveuglé par sa gloutonnerie et jouera |Rxh2|, la partie se terminant alors par une nulle (le Roi noir capturera le pion blanc sans difficulté au bout de 10 demi-coups). Cet exemple nous montre la nécessité d’inclure dans le programme des règles particulières permettant de déterminer aisément la valeur d’un pion dans une finale sans être contraint à des analyses en profondeur trop importantes.

Un autre exemple typique de problème de finales est le suivant. On considère la position : Roi noir en f6, pion noir en g6, Roi blanc en g2, Fou blanc en f5 Cavalier blanc en g5 et Fou blanc en h1 (figure 1.10).


Figure 1.10: Reconnaissance d’une finale Fou-Cavalier

Le programme ne peut défendre simultanément son Fou en f5 et son Cavalier en g5. Il jouera donc |Fxg6|, gagnant un pion avant de perdre le Fou. Il se retrouve alors à jouer une finale Roi, Fou, Cavalier contre Roi qui est gagnante. Jusque-là pas d’erreur. Remplaçons maintenant le Fou blanc en h1 par un Cavalier blanc(figure 1.11).


Figure 1.11: Reconnaissance de la finale Cavalier-Cavalier

Le problème est apparemment inchangé, la meilleure solution semble encore de jouer |Fxg6| pour gagner un pion avant de perdre une pièce. C’est d’ailleurs ce que font tous les programmes de l’ancienne génération et nombre de joueurs d’échecs novices. Il s’agit pourtant d’une erreur grave. En effet, la finale Roi, Cavalier, Cavalier contre Roi est toujours nulle. Le coup correct ici est |Fd3|, pour sauver le Fou. Après |Rxg5|, les blancs élimineront sans difficulté le pion noir restant avec leur coalition Roi, Fou, Cavalier puis materont le Roi noir. Mais là encore, il faut savoir sacrifier le court terme pour le long terme et surtout il faut savoir reconnaître certains types de positions particulières.

Signalons un dernier point capital dans beaucoup de finales : la nécessité d’établir un plan. Considérons la position suivante : Roi noir en e4, Roi blanc en g7, Fou blanc en h8, Cavalier blanc en g8 (figure 1.12).


Figure 1.12: Établir un plan

Il s’agit d’une typique finale Roi, Fou, Cavalier contre Roi. Cette finale est gagnante. Encore faut-il mater en moins de 50 coups29. Nombre de joueurs de club ont échoué dans une semblable finale et tous les programmes de l’ancienne génération échouaient également. Le mat ne peut être atteint que par un jeu précis et un plan parfaitement établi. Un problème encore plus difficile est posé par la finale Roi, Cavalier, Cavalier contre Roi et Pion qui peut être gagné dans certains cas30. Mais la réalisation du mat en 50 coups est excessivement difficile sans plan précis.

Nous avons donc vu la nécessité d’introduire trois éléments fondamentalement nouveaux dans les programmes de finale :

Les progrès réalisés ces cinq dernières années par les programmes en résolution de finales sont extrêmement spectaculaires31. Tous les exemples que nous avons présentés ci-dessus sont maintenant résolus par des programmes que l’on peut trouver dans le domaine public sur internet. Deux facteurs ont largement contribué à la progression des ordinateurs dans les finales : les tables de transposition (que nous avons déjà présentées), et l’analyse rétrograde que nous allons maintenant détailler.

Il s’agit d’une méthode permettant de constituer des base de données indiquant à l’ordinateur quel est le coup à jouer dans une position donnée pour arriver au gain de la façon la plus rapide. La constitution de semblables bases s’est beaucoup développée dans les dix dernières années. Ainsi, il existe une base de données permettant de jouer parfaitement des finales comme (Roi + Cavalier + Fou) contre (Roi + Cavalier), une finale que même un champion du monde aurait des difficultés à gagner32.

Pour construire de semblables bases de données, les ordinateurs utilisent une méthode appelée analyse rétrograde. Prenons comme exemple la finale (Roi + Dame) contre (Roi). Il existe, si on néglige les symétries, 64× 64 × 64=262144 positions de départ. Certaines de ces positions sont impossibles (les deux Rois adjacents par exemple) : elles sont éliminées. Dans les positions restantes, on recherche celles où les noirs sont mats : ce sont les positions où le Roi noir est déjà en échec et où aucun des coups dont il dispose ne permet de le soustraire à cet échec. À partir de là, on détermine aisément les positions de mat en un coup. Ce sont les positions qui permettent au blanc d’atteindre en un coup une position de mat. On peut ainsi déterminer récursivement les positions de mat en n+1 coups à partir des positions de mat en n coups.

La constitution de bases de données de ce type est une technique bien particulière, relativement éloignée de la programmation classique des jeux, mais fort intéressante. Les problèmes à 5 pièces (sans pion) ont été exhaustivement résolus33, et l’on travaille activement sur les problèmes à 6 pièces. En Octobre 1991, Larry Stiller (avec l’aide de Noam Elkies et Burton Wendroff) a construit la plus longue finale gagnante connue à ce jour. La position initiale est représentée sur la figure 1.13. La résolution complète demande 223 coups. Il est clair que ce type de finale est inaccessible à l’être humain. La question est de savoir si les règles doivent être modifiées pour en tenir compte.


Figure 1.13: Position initiale de la plus longue finale connue

1.7.3  Le milieu de partie

Nous allons retrouver les deux grands protagonistes du milieu de partie : la fonction d’évaluation et l’algorithme alpha-beta. Mais nous introduirons également quelques techniques spécifiques ou, en tout cas, surtout utilisées pour les échecs.

La fonction d’évaluation aux échecs est extrêmement complexe. La base d’une fonction d’évaluation est la valeur accordée aux pièces. On peut dire que les valeurs que la plupart des programmes accordent aux pièces sont les suivantes :

Dame:9
Tour:5
Fou:3
Cavalier:3
Pion:1

Il reste maintenant à raffiner la fonction d’évaluation. Tout un ensemble de paramètres interviennent. En voici quelques uns :

Ce n’est qu’un petit aperçu de ce que doit être une bonne fonction d’évaluation aux échecs.

Notons cependant un point capital : la notion de plan stratégique d’ensemble est absente. On peut, certes, introduire dans la fonction d’évaluation quelques éléments pseudo-stratégiques, comme l’attaque sur le roque adverse << à la baïonnette34 >>, mais cela reste très limité. Il s’agit bien là du principal défaut des programmes d’ordinateurs. Cela est particulièrement sensible lorsqu’ils passent de la séquence d’ouverture qu’ils jouent << par cœur >> au milieu de partie. En effet, à chaque ouverture est associée une idée stratégique et la suite de la partie doit développer cette idée. Ainsi une sicilienne doit être jouée de façon agressive par les blancs qui doivent attaquer rapidement le petit roque noir, alors que la chance des noirs se situe en général à l’aile dame. Or un programme est incapable de saisir ces subtilités stratégiques et appliquera la même fonction d’évaluation quelle qu’ait été l’ouverture. Tous les programmes d’ordinateur, même les meilleurs, manquent de << liant >> dans leur jeu, ce qui rend leur style facilement reconnaissable et les laisse encore vulnérables. On ne connaît actuellement aucune méthode pour remédier à cet état. Simplement, la force tactique des programmes leur permet de compenser leur faiblesse stratégique.

La technique de recherche dans l’arbre de jeu est un algorithme alpha-beta tel que nous l’avons décrit au paragraphe précédent. La technique de contrôle de temps de jeu et de reclassement des coups avant d’aborder des recherches plus profondes est également identique. Il faut cependant introduire certaines techniques indispensables aux échecs35 :

L’élagage de futilité :
Nous savons que l’algorithme alpha-beta élague une branche au niveau n dès que l’évaluation partielle de cette branche est inférieure (ou supérieure si le niveau est pair) à l’évaluation définitive du niveau n−1. Supposons par exemple que l’évaluation du niveau n−1 soit 3 et qu’une évaluation partielle au niveau n soit 3.01. Certes, l’évaluation n’est pas inférieure, mais il est clair qu’elle ne sera pas non plus franchement meilleure. On peut donc élaguer cette branche. Cette technique est appelée élagage de futilité.
Le coup meurtrier :
Supposons que lors de la recherche alpha-beta, l’algorithme note que le coup de premier niveau p1 est détruit par la riposte de d1 (c’est-à-dire que si l’adversaire répond d1 après p1 le score de la position s’effondre). Cela signifie que d1 est un coup meurtrier. Lors de l’examen du coup de premier niveau suivant p2, la première riposte que l’algorithme alpha-beta devra examiner sera précisément (si cela est possible) d1 car si le coup d1 a été meurtrier pour p1, il a de fortes chances de l’être également pour p2. De tels coups sont liés, aux échecs, à la notion de menace et la même menace reste souvent valable face à de nombreux coups. En procédant de cette façon, on améliore encore l’efficacité de l’élagage de l’algorithme alpha-beta.
Utilisation du temps de réflexion de l’adversaire :
Après avoir joué un coup, il est bon de retenir l’intégralité de la branche. En effet, on peut relancer la recherche alpha-beta pendant le temps de réflexion de l’adversaire sur la position telle qu’elle se produirait si l’adversaire joue la riposte que nous estimons la meilleure pour lui. De cette façon, si l’adversaire joue effectivement ce coup, nous aurons déjà effectué une grande partie de l’évaluation de la position.
Retour à l’équilibre :
Si l’algorithme alpha-beta travaille à une profondeur fixe, il s’expose à de sérieux ennuis. Supposons en effet que l’algorithme alpha-beta descende à une profondeur 3 et qu’il trouve une séquence du genre : je déplace mon Cavalier (premier niveau), on me le prend (deuxième niveau), je prends la Dame adverse (troisième niveau). Bien qu’il enregistre la perte de son Cavalier, le résultat est globalement positif puisque le programme comptabilise la prise de la Dame adverse. Mais supposons que le quatrième coup (non examiné puisqu’il s’est arrêté à la profondeur 3) est la prise de sa Dame. Le bilan global de l’opération est là franchement négatif. Pour éviter ce type de comportement, tous les algorithmes utilisent une stratégie dite de retour à l’équilibre. Une fois atteint leur profondeur maximale d’évaluation, ils poursuivent le calcul de la position terminale en continuant à examiner toutes les positions (et seulement les positions) découlant de prises ou d’échecs, jusqu’à ce qu’il n’y en ait plus. Ils peuvent ainsi éviter ce type de mauvaise évaluation.
Recherche secondaire :
Un autre problème qui guette les ordinateurs est l’effet horizon. Voici un exemple classique dû à Hans Berliner (cf. figure 1.14).

Figure 1.14: Effet horizon lié à un coup intermédiaire

Le Fou blanc en a4 est perdu. En effet, il ne pourra échapper au pion b5 ou au pion c5 (qui va venir en c4). La séquence qui provoquera la perte du Fou est |Fb3| suivi de c4 par les noirs et le Fou est perdu. Mais un algorithme alpha-beta tente simplement de repousser cette éventualité au-delà de son horizon de recherche (d’où le nom d’effet horizon). Il va donc tenter de jouer une séquence de coups à riposte forcée qui repoussera hors de son champ de vision la séquence << déplaisante >>. Dans le cas présent, il prévoit par exemple (profondeur 5) : |1. e5,d*e5| (obligatoire car sinon le Cavalier en f6 tombe), |2.Cd5,C*d5| (on ne peut jouer |2.:b*a4| car alors |3.C*e7+|), |3.T*d5|.

Arrivé à cette position, le programme applique son mécanisme de retour à l’équilibre. Mais il ne voit rien de dangereux car après |3.:b*a4| il voit |4. T*d7| et récupère le Fou. En fait, son raisonnement est incorrect car les noirs intercalent le coup intermédiaire |Fe6| et le jeu se poursuit en fait par : |3.:Fe6; 4.Fb3,c4| et le Fou est perdu.

Le programme, pour trouver la solution correcte, devrait effectuer la recherche à la profondeur 7, ce qui est prohibitif pour un ordinateur moyen. Certains écrivaient, il y a quelques années, que ce type de situation était ingérable par un ordinateur. En fait, la plupart des bons programmes de jeu utilisent aujourd’hui une technique appelée recherche secondaire qui leur permet de trouver la solution du problème précédent en quelques secondes. Il s’agit simplement de relancer la recherche alpha-beta à une profondeur supérieure, mais uniquement sur la branche (voire uniquement sur la position terminale de la branche) qui contient le coup sélectionné. Il s’agit, en quelque sorte, d’une vérification de la validité du coup choisi. Comme l’évaluation n’est faite que sur la position terminale sélectionnée, le temps nécessaire est raisonnable. Certes, ce mécanisme ne permet pas de faire disparaître l’effet horizon, mais il en limite considérablement les effets36.

L’algorithme SEX :
L’algorithme SEX (Search EXtension) [LBT89] a aussi pour but de limiter les problèmes d’effet horizon. Dans un mécanisme de recherche minimax classique, la profondeur de recherche est fixée au départ à n et à chaque descente d’un niveau dans l’arbre, on diminue de 1 la valeur de n. Lorsque n atteint 0, la recherche est terminée.

Avec l’algorithme SEX, on utilise une variable SX qui prend une valeur nettement plus grande que la profondeur à laquelle on veut chercher (une valeur typique est dix fois la profondeur, si n vaut 3, SX vaut 30), mais à chaque descente d’un niveau dans l’arbre, on diminue SX d’une quantité variable en fonction de l’intérêt du coup joué. Ainsi, un coup << moyen >> soustrait 10 à SX, une prise ou un échec est un coup intéressant, et on diminue peu SX (2 ou 3) ; en revanche, une retraite de pièces est un coup peu intéressant et on diminue beaucoup SX (jusqu’à 35). La recherche est terminée quand SX devient négatif ou nul.

De cette façon, les coups intéressants sont étudiés de façon plus profonde, et les coups << peu intéressants >> sont rapidement abandonnés.

L’heuristique du << coup nul >> :
Appelé Null Move Heuristic en anglais, cette technique consiste à supposer que, dans une situation donnée, un joueur exécute deux coups successifs37 (son adversaire ne joue pas, d’où le nom de << coup nul >>). Si la situation ainsi générée n’est pas clairement favorable, alors le premier coup est élagué de l’arbre de recherche. Cette technique permet d’améliorer l’efficacité de l’élagage mais provoque parfois des élagages intempestifs, comme un match du programme Mephisto au tournoi ACM de 1991 le montra…

Signalons, pour conclure, un des inconvénients de la méthode minimax. Si l’ordinateur se trouve dans une situation perdante et qu’il a le choix entre deux coups, dont le second est légèrement plus mauvais que le premier mais tend un piège à l’adversaire, il sera incapable de s’en apercevoir. Le principe minimax choisira obligatoirement le premier, alors qu’il garantit presque assurément la perte de la partie, alors qu’un joueur humain tentera le tout pour le tout et jouera le second coup. La notion de piège est bien difficile à formaliser, cependant Donald Michie proposa, il y a quelques années, une intéressante méthode qu’il est bon de rapporter. Supposons que nous ayons un arbre à deux niveaux que nous parcourons par une méthode minimax. L’ordinateur cherche la valeur S1 du premier coup de niveau 1. À partir de la position P1 correspondant à ce coup, son adversaire peut atteindre trois positions P11, P12 et P13 dont les scores sont respectivement S11, S12, S13. Théoriquement, l’ordinateur devrait remonter comme valeur au niveau 1 le minimum de ces trois valeurs. Michie propose de raffiner la méthode en prenant comme valeur du niveau 1 non pas le minimum, mais la combinaison linéaire :

p11 × S11p12 × S12 + p13 × S13 

p11, p12, p13 représentent les probabilités que l’adversaire a de jouer les coups S11, S12, S13 d’après l’ordinateur.

Comment évaluer ces probabilités ? Michie a mis au point une méthode pour les échecs, qu’il appelle modèle de discernement. Il estime que le discernement d’un joueur face à une position donnée est donné par la formule empirique :

d= (C/1000 +1) 31/(n+0.01) 

C représente le classement ELO38 du joueur que l’on affronte et n le nombre de coups dont on a calculé une valuation. Pourquoi cette formule ? Il est clair qu’un joueur joue d’autant mieux qu’il est plus fort. D’autre part, nous savons que plus il y a de coups différents possibles et plus le choix est difficile, surtout s’ils ont des valeurs proches. Michie estime alors que la probabilité qu’un joueur de discernement d face à une position joue un coup menant à un score estimé v sera :

p = A dv 

A est un coefficient bien choisi pour normer la probabilité. Il serait intéressant de tester la méthode de Michie, mais aucun programme ne semble l’utiliser aujourd’hui.

Enfin, et d’après39 Feng-Hsiung Hsu (responsable du projet deep thought), les programmes d’échecs à l’heure actuelle n’utilisent pas de technique d’apprentissage40 :

<< Une grave erreur doit être évitée : deep thought n’apprend pas. La fonction d’évaluation que nous utilisons est linéaire par rapport à presque tous ses termes (de 100 à 150). Nous ne faisons qu’une optimisation du modèle de mérite dans un espace multi-dimensionnel, en utilisant un mécanisme de régression linéaire. Ce processus produit des résultats intéressants, même s’il n’est pas clair qu’il produise toujours les effets désirés. >>

Pour plus d’informations sur les programmes qui jouent aux échecs, on ne peut que conseiller [LN91, MS90].

1.8  Le bridge

Notre exposé sur la programmation du bridge sera moins détaillé et moins complet que celui consacré aux échecs. La raison en est simple : peu de gens se sont intéressés à la programmation du bridge. On peut penser que la raison de ce désintérêt est l’aspect << chance >> qui existe au bridge. Les gens pensent que si un programme d’échecs l’emporte, il est meilleur, alors qu’un programme de bridge peut simplement << avoir de la chance >>. Il y a également le facteur << convivialité >> du bridge : on ne joue aux échecs qu’avec un partenaire, alors que le bridge se joue à quatre et on joue souvent au bridge plus pour être entre amis que pour améliorer son niveau de jeu. Enfin, une raison technique est que la réalisation d’un programme, même élémentaire, est beaucoup plus difficile qu’aux échecs : il faut en effet écrire un programme d’annonces correct, ce qui n’est déjà pas simple, puis introduire, au lieu des mécanismes de recherche classiques, des analyses probabilistes portant à la fois sur les informations fournies par les annonces et sur les informations fournies par le jeu de la carte. Il faut également utiliser des notions de planification pour choisir, avant de commencer le jeu de la carte (du moins pour le camp déclarant), la façon dont on estime pouvoir réaliser son contrat. En fait, tous les jeux à information incomplète sont difficiles à programmer, car il est impossible d’utiliser directement des méthodes de recherche classiques, en raison du très important nombre de distributions possibles de mains.

1.8.1  Les annonces

Le premier problème qui se pose au bridge est de construire un programme d’annonces efficace. Les annonces au bridge sont quelque chose de complexe et de très codifié. On pourrait penser qu’il est raisonnable de créer un système capable de contenir l’ensemble des situations possibles. C’est en fait irréalisable. Il faut donc construire un système à mi-chemin entre le << par cœur >> et des mécanismes heuristiques plus généraux. Un exemple typique de la difficulté de la programmation des enchères au bridge est le suivant : Nord annonce 1♠. Cela signifie qu’il a entre 13 et 20 points distribution-honneurs41 et au moins cinq Piques. Il attend alors la réponse de son partenaire Sud. Les réponses de Sud sont également codifiées de façon très précise comme l’est la première enchère. Mais supposons qu’Est intervienne entre Nord et Sud. Voilà Sud dans une situation bien difficile. Il devra moduler sa réponse en fonction de l’intervention d’Est. Si Est a simplement dit 1SA42, il pourra reparler au niveau de 2 et ne sera privé que de l’enchère de 1SA. En revanche, si Est a fait une enchère de barrage au niveau de 4, le problème est bien différent.

Le problème des enchères est encore compliqué par le fait qu’il existe plusieurs systèmes d’enchères différents, ainsi que des conventions spéciales que le programme doit également connaître.

Enfin, un bon programme doit également savoir utiliser les informations que donnent les enchères pour mettre à jour les probabilités de présence des cartes chez les autres joueurs. Ainsi, supposons qu’un des adversaires ouvre de 1♠. Nous savons qu’il a entre 12 et 20 points d’honneur43 et au moins cinq Piques. Nous pouvons donc modifier les probabilités de présence des cartes dans sa main. Jusque-là, pour toute carte que nous ne possédions pas, nous pouvions supposer que chacun des autres joueurs avait une probabilité de 1/3 de la posséder. Si je possède moi-même 10 points d’honneur, il en reste 30 dans le jeu. Le joueur qui a ouvert doit avoir en moyenne 13 points d’honneur44, donc je dois désormais donner à chacun des honneurs qu’il peut avoir dans sa main, une probabilité de 13/30=0.43. Nous devons, en conséquence, modifier la probabilité de présence de ces mêmes cartes dans toutes les autres mains. Le processus doit se poursuivre tout au long des enchères. À la fin, un bon programme doit avoir accumulé suffisamment d’informations pour pouvoir planifier correctement son jeu.

1.8.2  Le jeu de la carte

Le jeu de la carte est excessivement difficile à programmer. Il faut en effet planifier le jeu avant l’entame, modifier les plans en cours de partie si les défendants ne suivent pas la ligne prévue ou que les cartes ont une distribution défavorable, déclencher une recherche exhaustive quand la position de l’ensemble des cartes est connue ou quand le nombre de distributions possibles est réduit, et modifier en permanence les probabilités de présence des cartes dans les autres mains en fonction des renseignements que donnent les cartes jouées.

Considérons ce dernier point sur un exemple, pour bien montrer comment réaliser les modifications de probabilité. Supposons que l’ordinateur (en Nord) est le déclarant, qu’il a la main et décide de jouer le 4 de Pique alors que les Piques qu’il connaît sont répartis de la façon suivante (Pique n’a pas encore été joué, et comme Nord est le déclarant, Sud est le mort) :

Nord :
As, Roi,4 ;
Sud :
9,7,2.

Supposons qu’Est fournisse le 5, Sud le 9, qu’Ouest fasse le pli avec la Dame de Pique. Quelles informations pouvons-nous en retirer ? Sur Est peu de chose ; en revanche, nous pouvons améliorer nos connaissances sur Ouest. Comme nous possédons le Roi et l’As, nous savons qu’Ouest devait jouer le 10, le Valet ou la Dame pour réaliser la levée. S’il avait eu la Dame et le 10 sans le Valet, il aurait certainement joué le 10. Donc, nous savons qu’il a une des trois45 distributions suivantes : (Dame, Valet, 10) ou (Dame, Valet) ou (Dame). Si nous ne disposons d’aucune information venant de l’ouverture concernant Pique, nous pensons que chaque carte non localisée a une chance sur deux de se trouver en Ouest. Donc la probabilité de chaque distribution est :

Dame,Valet,10 :0.5 × 0.5 × 0.5=0.125
Dame,Valet :0.5 × 0.5 × (1−0.5)=0.125
Dame :0.5 × (1−0.5) × (1−0.5)=0.125

D’après le théorème de Bayes, nous savons que la probabilité que la Dame provienne d’une de ces distributions est :

Dame,Valet,10 :0.125/(0.125+0.125+0.125)=1/3
Dame,Valet :0.125/(0.125+0.125+0.125)=1/3
Dame :0.125/(0.125+0.125+0.125)=1/3

D’après ces résultats, nous voyons que la probabilité qu’Ouest ait le 10 est 0.33 et celle qu’il ait le Valet de 0.67. Nous devons donc ajuster les probabilités dans le jeu d’Ouest ainsi que dans le jeu d’Est. Nous venons de voir, sur cet exemple, que le re-calcul des probabilités n’est pas chose totalement triviale, même sur un cas simple.

Il nous reste maintenant à examiner comment jouer effectivement. À partir du moment où nous avons localisé l’intégralité des cartes, ou tout au moins que nous n’avons plus qu’un nombre de distributions possibles réduit, nous pouvons lancer une recherche exhaustive sur l’arbre de jeux. La fonction d’évaluation devra prendre en compte, non pas uniquement le nombre de plis faits, mais également le gain ou la perte au score. Il faudra aussi, dans certains cas, ne pas hésiter à utiliser la méthode de Michie telle que nous l’avons décrite, si, par exemple, nous devons, pour réaliser notre contrat, compter sur une faute adverse.

En début de partie, il faudra, si l’on est le déclarant, établir un plan de jeu. Réaliser un plan de jeu passable est relativement simple, on peut par exemple utiliser l’algorithme suivant :

Il est bien évident qu’un semblable algorithme serait complètement insuffisant pour réaliser un programme véritablement fort.

En ce qui concerne le jeu << au jour le jour >>, on peut implanter un certain nombre d’heuristiques classiques :

Ces heuristiques ne permettront pas de réaliser un programme très fort mais doivent suffire à écrire un programme médiocre. On doit également utiliser les probabilités de répartition des cartes lorsque cela est possible.

Il existe bien d’autres heuristiques que l’on peut implanter, mais on ne possède que peu de résultats sur leur efficacité. Il existe quelques machines commerciales disponibles, mais elles sont toutes très faibles, même pas du niveau d’un joueur de club moyen.

1.9  Autres jeux

D’autres jeux ont été programmés avec plus ou moins de succès :

Le backgammon :
Sans doute le domaine où a été obtenu le résultat le plus probant. Le programme bkg de Hans Berliner (qui faisait là son galop d’essai avant de se concentrer complètement sur les échecs) a en effet battu le champion du monde de Backgammon. On peut lire pour plus de renseignements [Ber80]. Berliner reconnaît cependant que le programme a eu de la chance lors de son match et il n’accordait à son programme que 25% de chances de gagner.
Les dames :
On ne connaît pas de programme de dames françaises. En revanche, il existe de nombreux programmes pour les dames américaines46 (checkers) dont le premier fut celui d’Arthur Samuel. Le niveau de ces programmes est extrêmement élevé. Le programme actuellement le plus fort est chinook (Jonathan Schaeffer, Joseph Culberson, Norman Treloar, Brent Knight, Paul Lu and Duane Szafron (University of Alberta, Edmonton, Canada)). Au mois d’août 90, chinook a participé et remporté l’Open du Mississipi en gagnant 7 parties, en annulant 7 et n’en perdant aucune. Il battit à cette occasion 2 des dix meilleurs joueurs mondiaux. Il participa ensuite à l’Open des États-Unis, où étaient présents neuf des dix meilleurs joueurs du monde dont le champion du monde Marion Tinsley47.

Le tournoi se déroulait en huit matches de quatre parties chacun. chinook en gagna quatre, fit quatre nulles et termina ainsi second du tournoi derrière Tinsley (+5, =3, -0). Le match contre Tinsley se termina par une nulle (+0, =4, -0). chinook est ainsi le premier ordinateur à se qualifier pour une finale officielle de championnat du monde. La fédération américaine ayant refusé que le programme soit désigné comme challenger officiel, Tinsley a abandonné son titre et a affronté chinook dans un match qui pouvait être considéré comme un championnat du monde officieux, à Londres, au mois d’août 1992. Tinsley l’emporta au terme des 40 parties sur le score de 4 parties gagnées, 2 parties perdues et 34 parties nulles, une performance remarquable pour chinook. Un match revanche eut lieu en 1994, qui vit la victoire de chinook par abandon, Marion Tinsley étant déjà affaibli par la maladie qui devait l’emporter. Depuis, chinook a affronté le successeur de Tinsley, Don Lafferty, et a successivement annulé le premier match en 1994 et gagné le second en 1995. Il faut noter que la fédération de checkers autorise désormais chinook à participer à la majorité des grands tournois, et a créé un titre spécial de champion du monde homme-machine qui sansctionne le vainqueur du match opposant le champion du monde humain au meilleur programme.

Les principes généraux pour la programmation du jeu de Checkers sont les mêmes que pour le jeu d’échecs avec quelques différences notables :

Les gens intéressés par chinook et la programmation des dames américaines peuvent se reporter aux excellents articles de Jonathan Schaeffer [Sch89a, Sch89b, SCT+91, Sch91, SCT+92].

Jonathan Schaeffer estime que, dans l’état actuel de la technologie, il doit être possible de résoudre complètement le jeu de checkers [SCT+92], c’est-à-dire de construire un programme capable de jouer parfaitement de façon certaine. Si l’équipe de chinook y parvient, les checkers seront le premier jeu réellement complexe48 à être résolu.

Le Go :
Le Go fait partie des jeux extrêmement difficiles à programmer, bien qu’il soit à information complète. En effet, l’arbre de jeu ne peut pas être examiné de façon complète, même sur deux niveaux, en raison du très grand nombre possible de coups à chaque tour de jeu (plus de 300 en début de partie). D’autre part, le jeu est avant tout lié à des concepts positionnels stratégiques très difficiles à formaliser simplement. Le Go est très étudié en ce moment. Il s’agit probablement du prochain grand défi après les échecs. On peut lire avec profit [CKMN90] et [Shi90] sur le sujet. Un des meilleurs programmes de Go est mfgo (Many Faces of Go), de David Fotland. Il a une force approximative de 13 Kyu49, ce qui le place loin des très bons joueurs.

Dans un programme de Go, il y a trois parties principales : les structures qui représentent la connaissance, la fonction d’évaluation pour déterminer le score et la fonction de sélection des coups.

La représentation des connaissances :
Il faut organiser la connaissance de façon à pouvoir l’utiliser efficacement et rapidement. Les structures ne sont pas relatives à des cases, ni globales, mais sont attachées à des groupes, des chaînes de pierres, des connexions ou des yeux.
L’évaluation :
La fonction d’évaluation tente de donner à chaque groupe une valeur heuristique en terme de vie ou de mort. Un groupe ayant deux yeux sera inconditionnellement vivant et aura la plus forte évaluation, un groupe pouvant être capturé en peu de coups sera inconditionnellement mort. Entre ces deux extrêmes, David Fotland distingue 23 catégories en fonction des yeux potentiels, de la possibilité de s’échapper, le nombre de groupes voisins faibles…Cette fonction d’évaluation utilise un programme de recherche tactique pour évaluer les prises possibles.
La sélection de coups :
Plutôt que de tester chaque coup, le programme utilise un ensemble de règles expertes qui lui suggèrent des coups à essayer en priorité, en fonction de certains critères. On vérifie, après la réalisation du coup suggéré, qu’il a bien mené au but recherché. Par exemple, si une règle offensive suggère d’attaquer un groupe, le groupe doit être plus faible après que le coup ait été réalisé.

Cette rapide description montre bien que l’approche de la programmation du Go se distingue très nettement de celle des autres jeux. Elle s’appuie plus sur des considérations expertes que sur des considérations de force brute. Il reste à savoir quel sera l’avenir de ces programmes. Les premiers programmes d’échecs étaient eux aussi des programmes plus orientés vers l’expertise que vers la force, et la tendance s’est lentement inversée.


1
Voir [MS90] : un ouvrage de référence, à la fois sur les techniques de programmation, et sur les relations de la programmation des jeux et particulièrement des échecs avec l’IA.
2
Charles Babbage (1792–1871) peut être considéré comme un des pères des machines programmables. Il définit dès 1833 les principes fondamentaux qui allaient amener à la réalisation des ordinateurs modernes. Protégé et financé par la comtesse Ada Lovelace, fille de Lord Byron, il ne put cependant mener à bien son projet en raison du manque de moyens technologiques de son époque.
3
Claude Shannon est un des pères de la théorie de l’information.
4
Le petit article [Mar90] de Tony Marsland fait le point sur l’histoire de la programmation du jeu d’échecs.
5
Il est particulièrement intéressant de remarquer qu’aujourd’hui les meilleurs programmes s’appuient sur des méthodes de force brute et non sur des modèles cognitifs. Sur le problème de la force brute dans la programmation des jeux, voir [Mic90].
6
La phrase << Les échecs sont la drosophile de l’Intelligence Artificielle >> doit être attribuée, d’après John McCarthy, au physicien soviétique Alexandre Kronrod, qui l’utilisa sans doute pour la première fois en 1966. McCarthy a repris l’expression a son compte dans [McC90].
7
Voir [Kai90] : un excellent article faisant le point sur les méthodes modernes de recherche dans les arbres de jeux.
8
Le facteur de branchement est le nombre de nœuds moyens que l’on peut générer à partir d’une position.
9
On peut trouver une présentation complète de cet algorithme avec bien d’autres dans [AVAD52].
10
Les premières descriptions de cet algorithme remontent à la fin des années 40. Ce sont Turing et Shannon qui, les premiers, ont envisagé ce mécanisme de recherche pour les ordinateurs.
11
L’algorithme alpha-beta a été explicitement décrit pour la première fois par Hart et Edwards en 1961.
12
Lors de l’exploration du même arbre, les feuilles étant ordonnées de façon similaire dans les deux cas.
13
Ces fonctionnalités peuvent être obtenues par une structure de données du type << file de priorité >> ou Heap [CLR90].
14
Le lecteur intéressé pourra l’appliquer à l’Awale, proche du jeu de Kalah, jeu africain dont le facteur de branchement est inférieur à 6.
15
Algorithmes tous réalisés en le_lisp, utilisant la même fonction heuristique, les mêmes fonctions d’exploration de l’arbre de jeu. Les temps sont sans unité.
16
En anglais, hash table. Voir par exemple [CLR90].
17
L’addition de nombres binaires sans retenue (qui correspond à un ou exclusif bit à bit) consiste à additionner chaque chiffre en utilisant comme règle : 0 ⊕ 0 = 0, 0 ⊕ 1 =1 et 1 ⊕ 1 = 0.
18
On appelle cette structure hash cache table en anglais. Notons qu’il existe des stratégies plus évoluées.
19
Appelé aussi modèle maître-esclaves.
20
Le terme de granularité semble adapté à la représentation intuitive que l’on se fait de la parallélisation d’une tâche. On peut considérer la tâche comme un bloc monolithique. La paralléliser va consister à la réduire en sous-tâches plus petites. Si nous découpons la tâche en gros blocs, on parlera de grosse granularité (peu de sous-tâches, et chaque sous-tâche est importante). Si nous décomposons la tâche en de multiples petites sous-tâches, on parlera de petite granularité.
21
Il existe d’autres implantations parallèles de l’algorithme alpha-beta beaucoup plus efficaces. Le problème principal de cette implantation est que dans une résolution par un mécanisme alpha-beta, la réponse au premier coup prend généralement 50% du temps de résolution. Donc répartir également chacun des coups du premier niveau est clairement une erreur. L’algorithme PVSA (Principal Variation Splitting Algorithm) améliore le système en parallélisant les réponses pour le premier coup à chaque niveau de l’arbre. On peut se reporter à [ABD82, Sch89a, MS90, Kus95] pour des méthodes encore plus efficaces.
22
On peut se demander pourquoi présenter Othello. Plusieurs raisons à cela : c’est un des jeux où les ordinateurs ont obtenu les performances les plus probantes ; un des auteurs de cet ouvrage est également l’auteur du programme d’Othello présenté dans ces quelques lignes, (programme qui battit il y a quelques années un bon joueur français et reste cependant assez loin des tous meilleurs programmes), et connaît donc assez bien les techniques utilisées ; enfin, c’est un jeu relativement connu et dont les règles se comprennent rapidement.
23
À distinguer des échecs où une partie peut durer moins de 10 coups ou plus de 100.
24
On est loin des principes cognitifs fondateurs de l’IA !
25
Nous simplifions ici à l’extrême. En fait, nombre de programmes utilisent des fonctions d’évaluation contenant des termes non linéaires.
26
Il peut se produire un problème si la position à laquelle nous nous trouvons n’a pas été étudiée au coup précédent parce que l’algorithme alpha-beta l’a élaguée. Normalement, ce type de situation ne se produit que si l’adversaire fait une erreur, et peut donc être négligé.
27
Hans Berliner présente la caractéristique intéressante d’être un très fort joueur d’échecs, puisqu’il fut champion du monde d’échecs par correspondance. Il s’intéresse à la programmation du jeu d’échec depuis de nombreuses années et passa son PhD en 1974 sur ce sujet. Pour une description de Hitech, voir [Ber90].
28
Pour une description de deep thought, voir [HACN90].
29
Rappelons qu’il existe aux échecs une règle qui stipule qu’une partie est nulle s’il se produit une séquence de cinquante coups sans prise de pièce ou de pion.
30
C’est une des bizarreries des échecs. La finale Roi, Cavalier, Cavalier contre Roi est nulle, mais la finale Roi, Cavalier, Cavalier contre Roi et Pion peut être gagné, le pion noir étant utilisé par les blancs pour bloquer une case de fuite du Roi noir.
31
Une des critiques que l’on peut adresser à la présentation des techniques de jeu dans [Lau86] est qu’elle date sérieusement par rapport aux résultats actuels.
32
L’ordinateur a d’ailleurs prouvé que les règles actuelles du jeu d’échecs étaient, dans un certain sens, << incorrectes >>. En effet, la règle stipule qu’une partie est déclarée nulle si aucune prise de pièces ou aucune promotion n’a eu lieu en cinquante coups. Or, il existe des cas où la finale (Roi + Cavalier + Fou) contre (Roi + Cavalier) ne peut être gagnée qu’en soixante-dix-sept coups.
33
Pour être tout à fait précis, Larry Stiller calcula exhaustivement les 80 positions les plus intéressantes en 227 minutes sur une connection-machine [TMC91] à 32000 processeurs (une demi-connection-machine en fait).
34
Technique consistant à attaquer le roque adversaire avec les pions.
35
Ces techniques peuvent s’appliquer, avec plus ou moins de bonheur ou d’utilité, à d’autres jeux.
36
Sur les techniques dites de Singular Extension, voir [ACH90].
37
Pour une description précise, voir [GC90].
38
Le classement ELO d’un joueur est une procédure internationale permettant d’attribuer une force à un joueur d’échecs. La méthode de calcul de ce nombre de points est complexe. Disons que l’on gagne des points chaque fois que l’on bat ou que l’on annule contre un joueur plus fort que soi, et que l’on en perd dans le cas contraire (présentation fort sommaire et quelque peu inexacte). Pour donner une idée, le champion du monde actuel a un ELO de l’ordre de 2800, un GMI tourne autour de 2500, un MI autour de 2200, la moyenne de l’ensemble des joueurs d’échecs est d’environ 800. Les meilleurs programmes commerciaux actuels ont une force de l’ordre de 2500/2600 points.
39
Correspondance privée.
40
Sans qu’il soit toujours simple de préciser ce qui est ou n’est pas de l’apprentissage. Il est souvent très tentant, et dans tous les domaines, d’utiliser ce genre de mot, à la sémantique << attirante >> et mal définie, pour séduire les financeurs potentiels. Ceux-ci devraient, comme dans les restaurants, se méfier des menus aux noms pompeux et aller faire un tour en cuisine…
41
Un honneur au bridge est soit un As, soit un Roi, soit une Dame, soit un Valet. On compte les points en prenant comme valeur As : 4, Roi : 3, Dame : 2, Valet : 1. Les points de distribution sont : 3 pour une chicane, 2 pour un singleton, 1 pour un doubleton.
42
SA : Sans-Atout. 1SA : enchère de 1 Sans-Atout.
43
Pas exactement, mais nous ne rentrerons pas dans trop de détails.
44
Cela peut paraître curieux, mais c’est ainsi.
45
Il peut, bien sûr, posséder d’autres cartes à Pique, mais nous ne nous intéressons qu’à ces trois cartes-là : Dame, Valet, 10.
46
La différence principale vient de la taille du damier (8x8) au lieu de (10x10), et à certaines règles de prise.
47
Le Dr. Marion Tinsley fut le meilleur joueur de checkers pendant près de 40 ans et durant cette période, où il joua des milliers de parties, il n’en perdit qu’une dizaine.
48
Le tic-tac-toe est un jeu résolu, mais il n’est pas franchement complexe…
49
Le classement des joueurs de Go est complexe. Les joueurs << faibles >> sont classés en Kyu. Plus faible est le Kyu, plus fort est le joueur. Les débutants ont une force de 30 Kyu approximativement. Un joueur pratiquant régulièrement en club, pendant un ou deux ans, doit atteindre une force de l’ordre de 10 Kyu. Lors d’une partie, la différence des Kyu des deux joueurs est utilisée pour déterminer le nombre de pierres de handicap. Arrivé à 1 Kyu, le rang suivant est 1 Dan, et le rang le plus élevé possible est 9 Dan. Les meilleurs joueurs amateurs ont une force de 7 Dan environ. David Fotland, l’auteur de mfgo, a une force de 3 Dan.

Références

[ABD82]
S. G. AKL, D. T. Barnard, and R. J. Doran. Design, analysis and implementation of a parallelel tree search. IEEE-PAMI, 4(2), 1982.
[ACH90]
T. S. Anantharaman, M.S. Campbell, and F. H. Hsu. Singular extensions: Adding selectivity to brute-force searching. Artificial Intelligence, 43(1):99–110, 1990.
[AJS91]
David Applegate, Guy Jacobson, and Daniel Sleator. Computer analysis of Sprouts. Technical Report (CMU–CS–91–144), Carnegie Mellon University, Pittsburgh, PA 15213, May 1991.
[AVAD52]
Adelson-Velsky, Arlazarov, and Donskoy. Algorithms for games. Springer-Verlag, 1952. ISBN: 0-387-96629-3.
[BB86]
S. Bhattacharya and A. Bagchi. Making use of available memory when searching game trees. In Proc. of AAAI-86, Philadelphia, PA, August 11–15 1986. Présentation de l’IterSSS*.
[Ber70]
Claude Berge. Graphes et hypergraphes. Dunod, Paris, France, 1970.
[Ber80]
Hans Berliner. L’ordinateur champion de backgammon. Pour la science, Août 1980.
[Ber90]
Hans Berliner. Hitech. In Computers, Chess and Cognition. Springer-Verlag, 1990. In [MS90].
[Bur97]
Michael Buro. Toward opening book learning. In Proceedings of IJCAI97 workshop on computer games, 1997.
[CBG82]
J. H. Conway, E. Berkelamp, and R.K. Guy. Winning Ways (for your mathematical plays). Academic Press, New York, 1982. ISBN : 0-12-091150-7.
[CKMN90]
K. Chen, A. Kierulf, M. Muller, and J. Nievergelt. The design and evolution of Go Explorer. In Computers, Chess and Cognition. Springer-Verlag, 1990. In [MS90].
[CLR90]
Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to algorithms. MIT Press, 1990. ISBN : 0-262-03141-8.
[Con76]
John Horton Conway. On Numbers and Games. Academic Press, 1976. ISBN: 0-12-186350-6.
[GC90]
G. Goetsch and M.S. Campbell. Experiments with the Null-Move Heuristic. In Computers, Chess and Cognition. Springer-Verlag, 1990. In [MS90].
[Gro65]
Adrian De Groot. Thought and choice in chess. In Nico Frijda and Adrian De Groot, editors, Otto Selz, his contribution to psychology. Mouton, The Hague, 1965. ISBN: 902793438X.
[HACN90]
F.h Hsu, T.S. Anantharam, M.S. Campbell, and A. Nowatzyk. deep thought. In Computers, Chess and Cognition. Springer-Verlag, 1990. In [MS90].
[Kai90]
H. Kaindl. Tree Searching Algorithms. In Computers, Chess and Cognition. Springer-Verlag, 1990. In [MS90].
[Kor85]
R. E. Korf. Depth first iterative deepening : An optimal admissible tree search. Artificial Intelligence, 27:97–109, 1985.
[Kro86]
Nicolai Kroguious. La psychologie au jeu d’échecs. Grasset - Europe Échecs, 1986. Recueil d’articles du psychologue et GMI Kroguious parus en 1967, 1968 et 1969.
[Kus95]
Bradley Kuszmaul. The star tech massively parallel chess program. Journal of the International Computer Chess Association, 18(1), March 1995.
[Lau86]
J. L. Laurière. Intelligence Artificielle, Tome I: résolution de problèmes par l’homme et la machine. Eyrolles, 1986.
[LBT89]
David Levy, David Broughton, and Mark Taylor. The SEX algorithm in computer chess. ICCA journal, 12(1), 1989.
[LN91]
David Levy and Monty Newborn. How Computers Play Chess. Computer Science Press, 1991. ISBN: 0-7167-8239-1, 0-7167-8121-2.
[Mar90]
T. A. Marsland. A short history of computer chess. In Computers, Chess and Cognition. Springer-Verlag, 1990. In [MS90].
[McC90]
John McCarthy. Chess as the Drosophilia of AI. In Computers, Chess and Cognition. Springer-Verlag, 1990. In [MS90].
[Mic90]
Donald Michie. Brute force in Chess and Science. In Computers, Chess and Cognition. Springer-Verlag, 1990. In [MS90].
[MS90]
T. Anthony Marsland and Jonathan Schaeffer. Computers, Chess and Cognition. Springer-Verlag, 1990. ISBN : 0-387-97415-6.
[Pea85]
Judea Pearl. Heuristics — Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishing Comp., 1985.
[Pea90]
Judea Pearl. Heuristique - Stratégies de recherche intelligentes pour la résolution de problèmes par ordinateur. Cepadues Éditions, 1990. Traduction française de [Pea85].
[PSDP96]
Aske Plaat, Jonathan Schaeffer, Arie DeBruin, and Wim Pijls. A minimax algorithm better than sss*. Artificial Intelligence, 87(1–2):255–293, 1996.
[SA78]
D. J. Slate and L. R. Atkin. Chess 4.5, the northwestern university chess program. In P. Frey, editor, Chess Skill in Man and Machine, pages 82–118. Springer-Verlag, 1978. ISBN: 0-387-07957-2.
[Sam59]
Arthur Samuel. Some studies in machine learning using the game of checkers. IBM journal of research development, 3(3):210–229, 1959.
[Sch89a]
Jonathan Schaeffer. Distributed game tree searching. Journal of parallel and distributed computing, 6(2):90–114, 1989.
[Sch89b]
Jonathan Schaeffer. The history heuristics and alpha-beta search enhancemants in practice. IEEE transactions on pattern analysis and machine intelligence, 11(11):1203–1212, 1989.
[Sch91]
Jonathan Schaeffer. Checkers: a preview of what will happen in chess? Journal of the International Computer Chess Association, 14(2):71–78, 1991.
[SCT+91]
J. Schaeffer, J. Culberson, N. Treloar, B. Knight, P. Lu, and D. Szafron. Reviving the game of checkers. In D. N. L. Levy and D. F. Beal, editors, Heuristic Programming in Artificial Intelligence, the second Olympiad, pages 161–173. Ellis Horwood, London, 1991. ISBN: 0-13-382615-5.
[SCT+92]
Jonathan Schaeffer, Joseph Culbertson, Norman Treloar, Brent Knight, Paul Lu, and Duane Szafron. A world championship caliber checkers program. Artificial Intelligence, 1992.
[Shi90]
K. Shirayanagi. Knowledge representation and its refinement in Go programs. In Computers, Chess and Cognition. Springer-Verlag, 1990. In [MS90].
[TMC91]
TMC. Connection machine – Model CM5 – Technical summary. Technical report, Thinking Machine Company, Cambridge, Massachusetts, October 1991.
[VB93]
Kim J. Vicente and William F. Brewer. La mémoire trompeuse des scientifiques. La recherche, 24(258), October 1993.
[Wei95]
Jean-Christophe Weill. Programme d’échecs de championnat, architecture logicielle, synthèse de fonction d’évaluation, parallélisme de recherche. PhD thesis, Université paris 8, Janvier 1995.

Retour à ma page principale

Le téléchargement ou la reproduction des documents et photographies présents sur ce site sont autorisés à condition que leur origine soit explicitement mentionnée et que leur utilisation se limite à des fins non commerciales, notamment de recherche, d'éducation et d'enseignement.
Tous droits réservés.

Dernière modification: 17:30, 21/03/2011 xhtml validation