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 : 122 - 123  |  Aller à la page   OK
Pages suivantes >
122 123
ÉCHECS ET ORDINATEURS Dès ses balbutiements, l'intelligence artificielle s'est intéressée aux jeux de réflexion, et plus particulièrement au plus noble d'entre eux  : le jeu d'échecs. Pour cela, on a créé des techniques, développé des méthodes afin que les ordinateurs se montrent à la hauteur des joueurs humains. Mais derrière tous ces jeux que proposent les magasins, derrière ces équipiers qui clignotent dans les vitrines, que se passe-t-il ? Des démarches simples sont mises en oeuvre  : elles se nomment minimax, alpha-bêta, heuristiques... Un peu d'histoire Tout avait commencé au XVIIl'siècle, avec le « Turc », automate à figure humaine, qui présentait la particularité de jouer aux échecs et de gagner. Mais sa qualité d'automate se réduisait à son apparence. En réalité, un joueur expérimenté se tenait à l'intérieur, qui, par un ensemble astucieux de leviers et de manettes, parvenait à manipuler les pièces. Certains mathématiciens de génie, tel le Britannique Babbage (1864), s'étaient penchés à l'époque sur la possibilité de jouer mécaniquement aux échecs, mais les possibilités techniques étaient si réduites qu'il fallut attendre encore bien longtemps avant de voir apparaître les premiers traitements réellement automatiques de ces distractions. Dès l'origine pourtant, un consensus s'établit autour du jeu d'échecs. Rêve de mathématiciens, il propose une image de l'intelligence sans passion et sans hasard  : la rigueur pure au service du jeu. En 1890, Leonardo Torres y Quevedo imagina et créa le premier automate d'échecs digne de ce nom. On est encore bien loin de ces « Elite » et autres « Mephisto » qui font merveille actuellement. Jouer est d'ailleurs ici un grand mot puisqu'il s'agissait en réalité de la résolution d'un problème qui a parfois lieu en fin de partie, quand presque toutes les pièces ont été prises  : le mat par la tour et le roi. A l'aide de mécanismes électromagnétiques, ce dispositif amenait le roi dans un coin de l'échiquier, toujours le même, pour le faire mat. Mais ces automates firent long feu. Afin de parvenir à des niveaux de jeu plus conséquents, il fallut attendre l'avènement de ce fantastique processeur d'informations qu'est l'ordinateur. Ainsi, l'histoire de l'informa- Mis au point en 1769 par le baron autrichien Von Kempelen, ingénieur à la Cour impériale de Vienne, le pseudoautomate gagna une partie contre Napoléon en 1809. tique est liée à celle de l'automatisation du jeu d'échecs. Dès ses premiers balbutiements, les premiers programmes d'échecs firent leur apparition. Très simplifiés, restreints à des phases de jeu bien particulières, faute de capacité mémoire, ce n'est qu'en 1957 qu'apparut le premier programme digne de ce nom, (NSS) sous l'égide de Simon, Newell et Shaw. A partir de ce moment, les progrès dans ce domaine allèrent croissant. Certains à cette époque firent preuve d'un peu trop d'enthousiasme. Ils prédirent qu'avant dix ans, un programme d'échecs serait champion du monde toutes catégories. David Levy, un maître de l'échiquier releva le défi en affirmant qu'aucun programme ne le dominerait avant 1978, et gagna son pari. Un ordinateur ne dispose, à l'encontre des êtres humains, d'aucune connaissance à l'avance. Il faut tout lui spécifier. Impossible de laisser un détail de côté. La moindre omission, le moinde défaut dans la programmation et l'ordinateur se « plantera » lamentablement. Dans les jeux sur ordinateur, et plus particulièrement les jeux de stratégie, les problèmes auquels ont dû faire face les informaticiens ont été nombreux  : représentation de l'échiquier, analyse des coups joués par l'ordinateur ou par son adversaire, ainsi que les techniques de jeux et leurs multiples raffinements nécessaires pour rendre les programmes réellement efficaces. En 1944 Von Neumann, puis quelques années plus tard, Shannon, dégagèrent les règles et les principes du jeu automatique. Ils appliquèrent aux échecs la méthode dite du minimax qui avait été découverte durant l'étude de la théorie mathématique connue sous le nom de théorie des jeux, qui s'intéresse à la modélisation des situations conflictuelles de compétition ou de concurrence. Cette méthode repose sur le développement de l'ensemble des mouvements de pièces possibles et de l'évaluation des po- Juillet-Août 1983
sitions qui en résultent, pour un nombre arbitraire de coups. Von Neumannsupposait alors que, s'il était possible de voir suffisamment loin dans le déroulement de la partie, on pourrait déterminer une stratégie de mat à coup sûr, et de ce fait, remporter le match. Cette idée était séduisante, mais inacceptable. Pour chaque situation, il existe environ une trentaine de coups légaux. Sur une portée de dix coups, l'ensemble des situations à envisager est de l'ordre d'environ 6.1014 (six cent mille milliards). Pour une profondeur de vingt coups, le total est porté à plus de 300 milliards de milliards (3.1029). Un chiffre si astronomique que pour un ordinateur qui examinerait un million de positions par seconde (ce qui est déjà considérable !) , il faudrait encore des millénaires pour analyser une telle partie ! Devant ces nombres exorbitants, les chercheurs s'engagèrent dans une démarche moins optimum mais plus réaliste. Il ne s'agit plus de déterminer une stratégie qui marche à coup sûr, mais d'analyser tous les mouvements de la machine et les rispostes de l'adversaire sur une plus faible profondeur, de deux à dix coups. Passer d'une approche globale et stratégique à une conception locale et tactique. A l'aide du minimax, la « meilleure » séquence de coups sera sélectionnée et jouée par l'ordinateur. Pour appliquer le minimax, il faut en premier lieu « valuer » les positions, c'est-à-dire attribuer un nombre à une situation des pièces, afin de distinguer les bonnes des mauvaises positions. Cette fonction de valuation est caractéristique d'un programme. C'est elle qui lui donne sa personnalité, son expression. Trouver une fonction d'évaluation efficace n'est d'ailleurs pas une affaire aisée. Comment prendre en compte tout ce qui constitue les multiples aspects de la qualité d'une position par rapport à une autre ? La mesure du « poids » des pièces encore en jeu forme le noyau d'une telle fonction. Perdre un fou représente un handicap, prendre une reine une aubaine. A chaque pièce est associée une valeur. Par exemple, roi = 500, reine = 10, tour = 5, fou = 3, cavalier = 3 et pion = 1. POSITION INITIALE E ris. E à ALALli Eikitfeitàà8 *LA AAA A A Fig. I. - Schéma de l'arborescence des premiers coups légaux dune panic. Pour connaître le score d'une position, il suffit d'additionner l'ensemble des pièces de son propre camp et de soustraire les pièces du camp adverse. A cette fonction de base, d'autres critè- res sont associés  : mobilité des pièces, position plus ou moins centrale, etc. L'analyse d'une situation, c'est-à-dire la détermination de l'ensemble des coups possibles, peut être représentée sous la forme d'une arborescence (fig. 1). Les noeuds correspondent aux positions, les arcs aux déplacements des pièces. Le programme envisage Juillet-Août 1983 MICRO-SYSTEMES — 123



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