Micro Systèmes n°33 jui/aoû 1983
Micro Systèmes n°33 jui/aoû 1983
  • Prix facial : 21 F

  • Parution : n°33 de jui/aoû 1983

  • Périodicité : mensuel

  • Editeur : Société Parisienne d'Edition

  • Format : (203 x 271) mm

  • Nombre de pages : 198

  • Taille du fichier PDF : 154 Mo

  • Dans ce numéro : spécial NCC'83... les nouveaux produits présentés à Los Angeles.

  • Prix de vente (PDF) : gratuit

Dans ce numéro...
< Pages précédentes
Pages : 124 - 125  |  Aller à la page   OK
Pages suivantes >
124 125
Encadré A LES ALGORITHMES DES JEUX D'ECHECS  : MINIMAX ET ALPHA-BETA L'ensemble des coups légaux pour une situation donnée est définie comme l'ensemble des déplacements permis par les règles du jeu. Leur génération est effectuée à l'aide d'une analyse systématique de l'ensemble des cases de l'échiquier. Imaginons que c'est au tour des blancs de jouer  : lorsque le programme rencontre une case occupée par une pièce blanche, il détermine la nature de la pièce. Il en déduit les déplacements autorisés  : ceux-ci peuvent être représentés sous la forme de distances relatives dans un repère cartésien. Par exemple, les déplacements du cavalier sont donnés par la liste  : (+2 + I) (+2 —1) (+1 +2) (+1 —2) (-1 +2) (-1 —2) (-2 +1) (-2 —1). Grâce à ces données, une procédure génère tous les coups en éliminant ceux qui ne sont pas permis, c'est-à-dire ceux qui placent la pièce en dehors de l'échiquier ou bien qui aboutissent à une case occupée par une pièce amie. Bien entendu s'il s'agit d'une pièce ennemie, elle sera prise. En moyenne, chaque position entraîne une trentaine de coups légaux. La nouvelle position obtenue est évaluée à l'aide d'une formule empirique qui prend en compte la valeur du matériel de chaque camp, les avantages positionnels, la mobilité des pièces, etc. Il faut savoir qu'aucune méthode ne s'avère totalement valable. Il n'existe pas de fonction d'évaluation parfaite. L'opération de génération des coups est ensuite réitérée jusqu'à parvenir à une profondeur de recherche déterminée. La figure A présente une arborescence simplifiée d'une profondeur de deux demi-coups  : ici, le programme examine non seulement le résultat de ses mouvements, mais aussi les ripostes de l'adversaire. La largeur de l'arborescence a volontairement été réduite à quatre coups maximum, quatre déplacements possibles pour les blancs comme pour les noirs. La méthode du minimax sert à déterminer quel est le bon déplacement à effectuer compte tenu de la riposte des noirs. Au premier niveau, on cherche à maximiser ses gains pour le développement de son propre jeu, c'est l'étape de maximisation. Au second, on suppose que l'adversaire en fera de même. Il est censé jouer le coup lui apportant le plus de réussite et qui correspond donc pour nous au gain minimum ; c'est l'étape de minimisation. Cette technique revient donc à effectuer le déplacement qui donne la plus forte des plus faibles valeurs provenant des réponses noires. Dans notre exemple, il faut jouer A, car il vaut +1, maximum des valeurs (+1 —2 —6 —8), résultat de la minimisation des positions situées à l'étage inférieur. La méthode du minimax est donc simple. Les résultats remontent des feuilles jusqu'à la racine de l'arbre, une fois en minimisant, une fois en maximisant, etc. Il a fallu attendre plus de quinze ans, à partir de la découverte du minimax, pour se rendre compte qu'il n'était pas nécessaire d'explorer entièrement l'arborescence tout en disposant des mêmes résultats. En effet, il est possible d'employer les valeurs déjà trouvées pour réduire l'éventail des évaluations susceptibles d'être intéressantes et ainsi « couper » les branches inutiles. Reprenons notre exemple. Connaissant la valeur +1, résultat de l'évaluation des sous-branches situées sous le noeud A, et parcourant l'arbre de gauche à droite, nous atteignons ensuite la sous-branche I issue de la position B, dont la valeur est —1. Le résultat de cette analyse nous suffit pour rendre superflue toute exploration ultérieure des autres positions, c'est-àdire des branches J et K. En effet, la valeur ramenée au niveau B sera au plus inférieure ou égale à —I (c'est l'étape de minimisation) et ne pourra donc être prise en considération à l'étage de maximisation (fig. B). Les branches J et K peuvent donc être coupées, les explorer ne changera rien au résultat final. Cette démarche peut se répéter (pour les branches suivantes). L'analyse de la première position du second groupe donne —6. Puisqu'il s'agit de l'étape de minimisation, la valeur ramenée à la branche C sera au plus égale à —6. Comme l'étape suivante est celle de maximisation et qu'une valeur supérieure à —6 a déjà été trouvée, toutes les positions issues du noeud C sont sans effet sur le résultat final. Cette opération « d'élagage des branches » est connue sous le nom d'alpha-bêta. Cette méthode est très intéressante pour augmenter la rapidité des programmes  : il suffit parfois d'analyser une position pour rendre inutile l'exploration de tout un groupe de branches. Ses performances dépendent directement de l'ordre d'évaluation des coups légaux. Par rapport au minimax, le nombre des positions à explorer peut théoriquement être réduit à la racine carrée de toutes les situations possibles. Un programme, qui avec un simple minimax dure cent secondes avant d'obtenir un résultat, peut voir son temps de réponse ramené à seulement dix secondes. Malheureusement, le réarrangement des coups, directement responsable des performances de cet algorithme, doit intervenir avant l'évaluation, c'est-à-dire avant de savoir quelles sont les positions. Un véritable cercle vicieux  : si le meilleur coup était connu avant évaluation, c'est toute l'exploration de l'arborescence qui deviendrait alors inutile. C'est pourquoi l'optimum théorique a finalement peu de chances de se produire en pratique. Tout l'art des programmeurs consiste à trouver le plus souvent empiriquement, des méthodes pour réordonner les coups  : par exemple, examiner toutes les positions qui possèdent des pièces en prise. C'est là qu'interviennent les heuristiques et, en réalité, la seule véritable « intelligence » que renferment ces jeux. 0 0 0 0 0 0 0 0 0 0 0 0 0 Fig. A. — La technique du minimax revient à explorer l'ensemble de l'arborescence en évoluant chacune des positions. Fig. B. — La méthode de l'alpha-bêta permet d'éviter l'analyse oc toutes les positions de l'arborescence en tenant compte des évaluations précédentes. 124 — MICRO-SYSTEMES Juillet-Août 1983
t IvInTre-1. ÉLerrnorur, COMPUTER CHESS• 01011 111r1 8 8 8 8 8 8 8 8'UV"'I W11 11A• 111'INOVI 11110VI, I1• -• I•\• 1•'V ( « Computer Chess un modèle présentant une symbolique originale des pièces (doc. Matte'I. d'abord tous les coups légaux qu'il peut jouer à partir d'une position initiale, puis toutes les ripostes de son adversaire, ainsi que toutes les répliques qu'il effectuera lui-même, etc. Les feuilles de l'arbre, c'est-à-dire les positions terminales, sont alors évaluées. Plus les valeurs obtenues sont élevées, plus le programme tentera de parvenir à ces situations. Plus elles sont faibles, plus il cherchera à les éviter (voir encadré A). Cette technique, le minimax et son corollaire l'alpha-bêta, est une méthode d'évaluation valable dans toutes sortes de cas, et pas seulement aux échecs. Elle revient à déterminer la meilleure stratégie possible en « remontant » des valeurs terminales vers la racine, afin de déterminer le « bon » coup, c'est-à-dire celui devant mener à la victoire, ou tout du moins à la position la plus favorable. Les heuristiques  : des choix sans certitude L'exploration combinatoire totale, telle qu'elle découle d'une énumération explicite comme le minimax, ou implicite, caractéristique de l'alphabêta, fournit des résultats certains, compte tenu des critères qui lui sont imposés  : un optimum par rapport à la fonction d'évaluation et la profondeur de recherche désirée. Cependant, cette démarche est lente dans le cas général et les chercheurs ont été amené à trouver des solutions pour accélérer ces processus d'explora- r 3 A A pe/À à r 4,tr À 4• re r7,, Are/r A À A Fig. 2. - Le bon coup à jouer pour les blancs est Rdi-d4 ou Rd3-c-I. Mais l'ordinateur, ici Coko HL ne l'a pas vu à cause de l'effet horizon qui limite sa vision du jeu. tion et améliorer le raisonnement. Dans notre environnement quotidien, nous devons en permanence faire face à des problèmes à résoudre sans être sûr d'employer la « meilleure » solution. Nous sommes alors dans ce que l'on appelle un univers incertain, et nous avons choisi sans certitude entre plusieurs possibilités. Cette caractéristique de l'intelligence humaine se formule, informatiquement parlant, sous forme d'heuristiques. Heuristique « Escorter, ›  : modèle classique avec pièces Staunton, l'or et l'argent remplaçant les traditionnels noirs et blancs (doc. Lansav). vient du grec « heuriskein » qui signifie « trouver en cherchant, imaginer, inventer ». C'est une méthode qui permet donc de résoudre un problème sans que l'on puisse dire si la solution atteinte est la meilleure. L'apparition de cette notion fit émerger l'informatique de sa démarche par trop mécaniste dans laquelle elle s'était engagée depuis sa création. Un dicton, tel que « novembre au balcon, Noël aux tisons », exprime une loi incertaine mais souvent vraie, dont le but est de nous aider à mieux comprendre notre environnement (à lui donner une organisation) et nous permettre de prendre des dispositions concernant l'avenir. Les programmes de jeu, pour s'améliorer, ont dû faire appel à ces méthodes moins rigoureuses mais plus souples. Dans le jeu d'échecs, par exemple, l'effort des informaticiens a porté sur la limitation de l'explosion combinatoire, c'est-à-dire du nombre de positions à évaluer, tout en conservant leur fiabilité aux programmes. Dans ce but, ils améliorèrent la performance des algorithmes de minimax et d'alpha-bêta en les complétant par des heuristiques. L'une d'entre elles, maintenant classique dans les jeux d'échecs, s'intitule la « killer heuristic », l'heuristique du tueur. Elle consiste à choisir et à examiner en premier les situations concernant les pièces mises en « échec ». Ce principe s'appelle aussi réfutation. Il revient à conserver en mémoire les coups qui conduisent à une situation trop mauvaise, ou trop bonne  : mats, échecs importants, prises de pièces, etc. pour ne pas avoir à les recalculer par la suite. Ainsi dans les problèmes conduisant à un mat, en deux coups par exemple, il a été montré que l'on peut obtenir le résultat escompté jusqu'à cinq fois plus vite avec un tel dispositif. D'autres heuristiques sont à mentionner  : « bouger le roi vers les pions », en fin de partie, aurait pu donner la victoire au programme Coko III devant J. Biit au cours de l'une des parties du premier tournoi américain de programmes d'échecs qui eut lieu à New York, en 1970. Après avoir joué 81 coups, la partie semble symétrique (fig. 2), mais les blancs peuvent gagner en jouant Rd4 ou Rc4. Mais Coko III ne peut voir Juillet-Août 1983



Autres parutions de ce magazine  voir tous les numéros


Liens vers cette page
Couverture seule :


Couverture avec texte parution au-dessus :


Couverture avec texte parution en dessous :


Micro Systèmes numéro 33 jui/aoû 1983 Page 1Micro Systèmes numéro 33 jui/aoû 1983 Page 2-3Micro Systèmes numéro 33 jui/aoû 1983 Page 4-5Micro Systèmes numéro 33 jui/aoû 1983 Page 6-7Micro Systèmes numéro 33 jui/aoû 1983 Page 8-9Micro Systèmes numéro 33 jui/aoû 1983 Page 10-11Micro Systèmes numéro 33 jui/aoû 1983 Page 12-13Micro Systèmes numéro 33 jui/aoû 1983 Page 14-15Micro Systèmes numéro 33 jui/aoû 1983 Page 16-17Micro Systèmes numéro 33 jui/aoû 1983 Page 18-19Micro Systèmes numéro 33 jui/aoû 1983 Page 20-21Micro Systèmes numéro 33 jui/aoû 1983 Page 22-23Micro Systèmes numéro 33 jui/aoû 1983 Page 24-25Micro Systèmes numéro 33 jui/aoû 1983 Page 26-27Micro Systèmes numéro 33 jui/aoû 1983 Page 28-29Micro Systèmes numéro 33 jui/aoû 1983 Page 30-31Micro Systèmes numéro 33 jui/aoû 1983 Page 32-33Micro Systèmes numéro 33 jui/aoû 1983 Page 34-35Micro Systèmes numéro 33 jui/aoû 1983 Page 36-37Micro Systèmes numéro 33 jui/aoû 1983 Page 38-39Micro Systèmes numéro 33 jui/aoû 1983 Page 40-41Micro Systèmes numéro 33 jui/aoû 1983 Page 42-43Micro Systèmes numéro 33 jui/aoû 1983 Page 44-45Micro Systèmes numéro 33 jui/aoû 1983 Page 46-47Micro Systèmes numéro 33 jui/aoû 1983 Page 48-49Micro Systèmes numéro 33 jui/aoû 1983 Page 50-51Micro Systèmes numéro 33 jui/aoû 1983 Page 52-53Micro Systèmes numéro 33 jui/aoû 1983 Page 54-55Micro Systèmes numéro 33 jui/aoû 1983 Page 56-57Micro Systèmes numéro 33 jui/aoû 1983 Page 58-59Micro Systèmes numéro 33 jui/aoû 1983 Page 60-61Micro Systèmes numéro 33 jui/aoû 1983 Page 62-63Micro Systèmes numéro 33 jui/aoû 1983 Page 64-65Micro Systèmes numéro 33 jui/aoû 1983 Page 66-67Micro Systèmes numéro 33 jui/aoû 1983 Page 68-69Micro Systèmes numéro 33 jui/aoû 1983 Page 70-71Micro Systèmes numéro 33 jui/aoû 1983 Page 72-73Micro Systèmes numéro 33 jui/aoû 1983 Page 74-75Micro Systèmes numéro 33 jui/aoû 1983 Page 76-77Micro Systèmes numéro 33 jui/aoû 1983 Page 78-79Micro Systèmes numéro 33 jui/aoû 1983 Page 80-81Micro Systèmes numéro 33 jui/aoû 1983 Page 82-83Micro Systèmes numéro 33 jui/aoû 1983 Page 84-85Micro Systèmes numéro 33 jui/aoû 1983 Page 86-87Micro Systèmes numéro 33 jui/aoû 1983 Page 88-89Micro Systèmes numéro 33 jui/aoû 1983 Page 90-91Micro Systèmes numéro 33 jui/aoû 1983 Page 92-93Micro Systèmes numéro 33 jui/aoû 1983 Page 94-95Micro Systèmes numéro 33 jui/aoû 1983 Page 96-97Micro Systèmes numéro 33 jui/aoû 1983 Page 98-99Micro Systèmes numéro 33 jui/aoû 1983 Page 100-101Micro Systèmes numéro 33 jui/aoû 1983 Page 102-103Micro Systèmes numéro 33 jui/aoû 1983 Page 104-105Micro Systèmes numéro 33 jui/aoû 1983 Page 106-107Micro Systèmes numéro 33 jui/aoû 1983 Page 108-109Micro Systèmes numéro 33 jui/aoû 1983 Page 110-111Micro Systèmes numéro 33 jui/aoû 1983 Page 112-113Micro Systèmes numéro 33 jui/aoû 1983 Page 114-115Micro Systèmes numéro 33 jui/aoû 1983 Page 116-117Micro Systèmes numéro 33 jui/aoû 1983 Page 118-119Micro Systèmes numéro 33 jui/aoû 1983 Page 120-121Micro Systèmes numéro 33 jui/aoû 1983 Page 122-123Micro Systèmes numéro 33 jui/aoû 1983 Page 124-125Micro Systèmes numéro 33 jui/aoû 1983 Page 126-127Micro Systèmes numéro 33 jui/aoû 1983 Page 128-129Micro Systèmes numéro 33 jui/aoû 1983 Page 130-131Micro Systèmes numéro 33 jui/aoû 1983 Page 132-133Micro Systèmes numéro 33 jui/aoû 1983 Page 134-135Micro Systèmes numéro 33 jui/aoû 1983 Page 136-137Micro Systèmes numéro 33 jui/aoû 1983 Page 138-139Micro Systèmes numéro 33 jui/aoû 1983 Page 140-141Micro Systèmes numéro 33 jui/aoû 1983 Page 142-143Micro Systèmes numéro 33 jui/aoû 1983 Page 144-145Micro Systèmes numéro 33 jui/aoû 1983 Page 146-147Micro Systèmes numéro 33 jui/aoû 1983 Page 148-149Micro Systèmes numéro 33 jui/aoû 1983 Page 150-151Micro Systèmes numéro 33 jui/aoû 1983 Page 152-153Micro Systèmes numéro 33 jui/aoû 1983 Page 154-155Micro Systèmes numéro 33 jui/aoû 1983 Page 156-157Micro Systèmes numéro 33 jui/aoû 1983 Page 158-159Micro Systèmes numéro 33 jui/aoû 1983 Page 160-161Micro Systèmes numéro 33 jui/aoû 1983 Page 162-163Micro Systèmes numéro 33 jui/aoû 1983 Page 164-165Micro Systèmes numéro 33 jui/aoû 1983 Page 166-167Micro Systèmes numéro 33 jui/aoû 1983 Page 168-169Micro Systèmes numéro 33 jui/aoû 1983 Page 170-171Micro Systèmes numéro 33 jui/aoû 1983 Page 172-173Micro Systèmes numéro 33 jui/aoû 1983 Page 174-175Micro Systèmes numéro 33 jui/aoû 1983 Page 176-177Micro Systèmes numéro 33 jui/aoû 1983 Page 178-179Micro Systèmes numéro 33 jui/aoû 1983 Page 180-181Micro Systèmes numéro 33 jui/aoû 1983 Page 182-183Micro Systèmes numéro 33 jui/aoû 1983 Page 184-185Micro Systèmes numéro 33 jui/aoû 1983 Page 186-187Micro Systèmes numéro 33 jui/aoû 1983 Page 188-189Micro Systèmes numéro 33 jui/aoû 1983 Page 190-191Micro Systèmes numéro 33 jui/aoû 1983 Page 192-193Micro Systèmes numéro 33 jui/aoû 1983 Page 194-195Micro Systèmes numéro 33 jui/aoû 1983 Page 196-197Micro Systèmes numéro 33 jui/aoû 1983 Page 198