Les jeux d’échecs et l’intelligence artificielle

Télécharger le fichier pdf d’un mémoire de fin d’études

La logique du jeu d’échecs

Connaissances sur le jeu :

Notion sur les jeux dee plateau :

Jeu de société qui se joue sur un plateau de jeu, eprésentant un paarcours ou une carte, sur lequel se déplacent des pions, selon des règlesou selon le hasard, qui peuvent parfois s’affronter ou accumuler dees points en collectant des ressources matérialisées par des marqueurs. Il s’agit généralement de jeux faisant ppela à nos capaccités de réflexion, d’observation ou de négociatiion, où l’on joue avecdes pions (qui représenttent les joueurs), des jetons et des figurines, et où l »on intègre une part de hasard par l’utilisationn de cartes et de dés qui influent sur le déroulemeent des parties. Dans ce type de jeu, l’action se déroule sur une surface délimitée, le plateau de jeu, comportant des étapes à franchir afin d’arriver à la victoire. Ainsi, le premier joueur à avoir accompli le parcours, ou le dernier à avoir encore des pions, ou celui qui a accum ulé le plus grand nombre de points, ou toute autre condition spécifique, est déclaré vainnqueur. Parmi les jeux ed plateau les plus connus, on trouve : Monopoly, Risk et Clue.

L’échiquier :

L’échiquier est le tablier ou plateau du jeu d’échecs. C’est une grille carrée de 8 cases de côté, soit 64 cases en tout, en alternance sombres (appelées «noires») et claires (appelées « blanches»). L’échiquier est posé sur une table. Avant de jouer, chaque joueur doit s’assurer d’avoir une case blanche sur sa droite dans le coin devant lui.
– Les huit files de cases allant d’un bord de l’échiquier à l’autre, perpendiculairement aux colonnes, s’appellent «rangées» ou «traverses».
– Les huit files de cases, allant du bord de l’échiquier le plus proche de l’un des joueurs à celui le plus proche de l’autre joueur, s’appellent«colonnes».
– Les files de cases de même couleur se touchant parles angles s’appellent «diagonales»
Chaque case de l’échiquier possède un nom qui est al combinaison de sa position, sur la colonne et de sa position sur la rangée, de la forme (lettre, chiffre). Afin de repérer facilement chaque case, un échiquier possède très ouvents un système de coordonnées.
Les lettres de a à h désignent les colonnes, les chiffres de 1 à 8 désignent les rangées.
Une case sera donc repérée par un couple (lettre, hiffre)c comme par exemple e4, a8, g7 etc. avec ce repérage, il sera facile de noter une partie. Les blancs partent donc toujours du « bas » de l’échiquier et « montent », tandis que les noirs « descendent ».
Le jeu d’échecs comporte 32 pièces dont 16 blancheset 16 noires. Chaque couleurs se composent de : 1 Roi, 1 Dame, 2 Tours, 2 Fous, 2 Cavaliers et de 8 pions.
Chaque pièce possède sa place sur l’échiquier :
Les pièces blanches (Roi, Dame, Tours, Cavaliers et Fous) sont placées sur la première ème ème rangée, les pions blancs sur la 2 rangée, tandis que les pièces noires sont sur la 8 rangée et les pions noirs sur la 7ème rangée.
Les Tours se retrouvent aux extrémités de l’échiquier, les Cavaliers viennent se placer à leurs côtés, suivis ensuite par les Fous et enfin le Roi et la Dame dans les 2 cases centrales de la rangée en notant que la Dame doit toujours se située sur la case de sa couleur.

Le déplacement des pièces :

Chaque pièce possède son propre déplacement. Une pièce ne peut jamais passer par-dessus une autre sauf le Cavalier
Le Roi : C’est la pièce centrale du jeu. La capture du Roi est en effet le but final de chaque partie. Il ne peut avancer que d’une case dans n’importe quelle direct ion, à condition que celle-ci ne soit pas menacée par une autre pièce. Le Roi n’est jamais battu, de sorte que sa mise en « échec et mat » signifie lafin de partie
Figure 4: Déplacement du Roi
La Dame : La Dame est la pièce la plus importante du jeu. Elle peut se déplacer tant comme la Tour que comme le Fou. Soit ; sans restrictions sur les rangées, les colonnes, et les diagonales. En fin departie, elle peut être une force déterminante pour l’obtention du mat.
Figure 5 : Déplacement de la Dame
Le Fou : Le Fou se déplace sur les 2 diagonales de la position qu’il occupe. Le Fou restant durant toute la partie sur la couleur de sa case de départ, il convient de préciser que chaque camp possède 2 Fous. Un sur lescases blanches et l’autre sur les cases noires.
Figure 6 : Déplacement du Fou
Le Cavalier : Le Cavalier est la pièce avec laquelle les débutants ont le plus de mal, tant il est compliqué de le déplacer sur l’échiquier. Son mouvement est particulier : 2 cases à la verticale ou à l’horizontale, puis une c ase en diagonale. Chaque camp possède 2 Cavaliers.
Figure 7 : Déplacement du Cavalier
La Tour : La tour est placée aux angles de l’échiquier. Cette pièce se déplace sur les ligneset les colonnes de la position qu’elle occupe au départ. Il est souvent délicat de les activer et elles restent souvent en fin de partie.
Figure 8 : Déplacement de la Tour
Le Pion : Dans les échecs modernes, le pion est la pièce de plus faible valeur. Mais il bénéficie de ropriétés que ne possède aucune autre pièce du jeu. Il ne peut revenir en arrière, ce qui fait que chacun de ces mouvements est irréversible. Depuis sa case, il peut se déplacer d’une ou de deux cases. Ensuite, il ne peut avancer que d’une case. Il prend les autres pièces uniquement en diagonales.
Figure 9 : Déplacement et prise du pion

Règles et but du jeu :

Le but du jeu d’échecs est de capturer le Roi de l’adversaire. Il est alors « échec et mat » et la partie est finie.
Quand le Roi est attaqué, on dit qu’il est en échecet on prévient son adversaire en lui disant « échec ».
Dans la position ci-dessous, je viens de jouer mon Fou en b5 et j’attaque le Roi noir.

L’échec :

S’il ne se défend pas, je le mangerais au prochain coup et la partie sera finie. Les Noirs sont OBLIGES de défendre leur Roi.
Figure 10 : Représentation de l’échec
Pour cela, il y a plusieurs solutions :
L’adversaire peut déplacer son Roi
Figure 11 : Parer l’échec en déplaçant le Roi
• L’adversaire peut manger la pièce qui les attaque.
Figure 12 : Prendre l’adversaire pour parer l’échec
• L’adversaire peut déplacer une pièce entre le Fou et le Roi
Figure 13 : Déplacer une pièce entre le Roi et le Fou
Comme nous somme en début de partie, les Noirs ontbeaucoup de défenseurs. Mon échec avec le Fou ne va pas donc servir à grand-chose, j’aurais mieux fait de jouer un autre coup, j’ai perdu du temps avec cette attaque.

L’échec et mat:

Le Roi est en échec et mat si :
• Une pièce adverse l’attaque
• Ni lui, ni aucune autre des pièces de sa couleur ne peut manger la pièce qui attaque
• Il ne peut se déplacer sur aucune autre case sans se faire prendre
• Aucune pièce ne peut se faire bouclier entre lui et la pièce qui l’attaque
Figure 14 : Position du Roi en échec et mat

Le pat :

Les blancs viennent de jouer leur Roi en h7, en espérant faire bientôt échecs et mat au Roi noir. Et pourtant, c’est une catastrophe!
Dans la position suivante, le trait est aux Noirs, or :
• Ils n’ont plus que leur Roi à bouger
• Le Roi n’est pas attaqué
• Le Roi ne peut pas bouger
Figure 15 : Position du PAT
Comme il est interdit de mettre son Roi en danger, le Roi noir ne peut pas bouger. Il est donc PAT et c’est un match nul!!! Cela peut paraître bizarre ou injuste mais les Blancs ont encerclés leur adversaire sans le capturer. C’est rageant mais c’est la règle

Méthodes de réflexion :

Observation :

La position sur l’échiquier se doit d’être observéet analysée minutieusement ;

Questionnement :

La position des pièces va provoquer beaucoup de questions sur les coups à jouer, à prendre en compte, à anticiper, … ;

Formulation d’hypothèse :

Le joueur devra, selon la position sur l’échiquier, émettre des hypothèses d’attaque ou de défense (à la fois pour lui et pour son adversaire) et valider les hypothèses émises par le choix du coup le plus approprié ;

Argumentation :

Aux échecs, le joueur doit être capable de justifier et d’expliquer chacun de ses coups (il vaut mieux déplacer une pièce avec une idée, une intention, un plan, même mauvais, plutôt que de jouer sans but précis) ;

Modélisation :

La mémorisation de modèles, de schémas, de tableaux de mat permettra au joueur de tenter, dans ses parties, de recréer, de modéliserces situations mémorisées afin de lui permettre un gain de la partie plus aisé.

Les jeux d’échecs et l’intelligence artificielle

Donald Michie dit :
« La recherche sur le jeu d’échecs est le champ le plus important de la recherche cognitive. Les échecs seront pour nous ce que la drosophile a été pour les généticiens : un moyen simple et pratique de développer de nouvellestechniques. »
1. L’évolution de l’intelligence artificielle dans le jeu d’échecs :
•“The Turk” –Baron Wolfgang von Kempelen – Avant le 19ème siècle
•Premier realalgorithm – Turing (1947)
•1948 – le programme UNIVAC était supposé imbattable!
•1952 – Turing a posté que les ordinateurs pourraient éventuellement devenir plus puissant que les humains
•1958 – Première victoire d’une machine contre un h umain
•1966 – Un programme Russe bat un programme Américain
•1970 – First ever all-computer tournament
•1977 – ICCA création
•1977 – GM Michael Stean perd dans une partie blitz contre un ordinateur
•1981 – Cray Blitz gagne Mississippi state champion ship un score parfait de 5.0
•1988 – DEEPTHOUGHT partage top place dans le US Ch ess Championship
•1992 – Fritz 2 perd contre le champion du monde Ka sparov dans un jeu semi rapide
•Fev 1996 – Kasparov bat IBM Deep Blue (4 –2)
•Mai 1997 – Deep Blue gagne face à Kasparov (3.5 –2 .5)
•Oct 2002 – Deep Fritz fait nulle le champion du mo nde Kramnik 4-4 in “Brains in Bahrain” match
•Jan 2004 – ChessBrain joue son premier match contr e GM Nielsen

Analyse théorique :

Les échecs sont considérés comme le jeu des Roist esurtout le Roi des jeux. Dès le début de l’Intelligence artificielle (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 épiques que se sont livrés les meilleures équipes universitaires comme HITECH, mené par Hans Berliner, ou DEEP THOUGHT, mené par Feng-Hsiung Hsu, 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 répercussions que l’on pourrait qualifier néfastes : le plus grand défi que l’on s’était lancé (la victoire d’un programmesur un champion du monde humain dans le cadre de partie à cadence de tournoi et sur six pa rties) 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 reste réelle,le niveau des programmes disponibles pour micro-ordinateurs est maintenant tellement élevé qu’ils battent systématiquement 99% des joueurs. On accordera donc plus l’importance à la q ualité 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 Nikolaï 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’abo rd les résultats mise en évidence par De Groot( en 1965) et Kroguious(en 1986) sont très intéressantes car ils sont applicables à la plupart des raisonnement humain dans tous les domaines ; enfin, ces résultants 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 les techniques humaines pour faire résoudre des problèmes à des machines.

Les études des psychologues :

Nous allons ici évoquer les travaux effectuer par lepsychologue hollandais De Groot et ceux du psychologue et GMI soviétiqiue Krouguious.
De Groot put travailler avec un échantillon tout à fait remarquable de six GMI (dont un champion du monde, Max Euwe), quatre MI, deux champions des Pays Bas et 10 experts. De par l’exceptionnelle qualité de ces joueurs, l’étude de De Groot est incomparable.
De Groot et ses élèves analysèrent la façon dont esl joueurs d’échecs perçoivent une position. Pour ce faire, ils présentèrent à chaque joueur une position sur un échiquier pendant 5 secondes puis enlevèrent les pièces de l’échiquier et leur demandèrent de les replacer. Ils s’intéressèrent alors à 2 facteurs : le nombre de pièces replacées correctement et la façon de replacer les pièces. Ils remarquèrent un certain nombre de points intéressant :
– Les GMI parvenaient à replacer l’intégralité des pièces dans près de 40% des cas alors que les experts n’y sont jamais parvenus, tout en obtenant le score honorables
– L’ensemble des individus testés qui savaient jouer aux échecs replaçaient les pièces par groupe logique. Ainsi, on replaçait en même temps l’ensemble des pièces qui attaquaient le roque et celles qui le défendaient. Les individus qui ne savaient pas jouer aux échecs replaçaient les pièces de façon corrélée et obtenaient un score désastreux.
– Les grands maîtres avaient fait réaliser une mémorisation de la position qui était proche d’une analyse. Ils se la rappelaient comme un ensemble de lignes d’attaque et de défense, et non comme un ensemble de pièces.
– Les grands maîtres avaient reconstruisaient la position par référence à des positions de partie déjà connues qui ressemblaient à celle-ci . Ils étaient capables de dégager les grandes lignes du jeu qui avaient mené à la position considérée.
– Placés devant des positions aléatoires (non plus tirées de parties réelles, mais composées de pièces posées au hasard sur l’échiquier), tous les individus, joueurs, non joueurs et GMI obtenaient des scores comparables et très mauvais.
D’autres travaux furent menés pour étudier la façon dont les joueurs d’échecs « à l’aveugle » voient mentalement la position. Ainsi un article publié par Pina Morini en 1946 dans la revue italienne Minerva Medica estimait qu’il existait différents types de mémorisation de la position, visuelle pour certainset linguistique pour d’autres (qui relisent mentalement la liste des coups joués). En revanche,l’analyse d’une position se fait toujours par bloc logique et par analogie avec les positions connues.
De Groot s’intéressa ensuite à la façon de raison ner de chacun de ses cobayes. Il leur présenta des positions et leur demanda quel coup ils joueraient et pourquoi. Il en dégagea les enseignements suivants :
– La plupart des positions sont tout d’abord pensées par analogie avec des positions déjà rencontrées. Ces analogies permettent d’isolerles coups qui peuvent permettre un gain ou éviter une défaite, toujours en rapportavec des stratégies globales à long terme.
– La recherche du joueur est très sélective. L’aptitude principale des grands maîtres est leur capacité à identifier rapidement le ou les bons coups, à analyser sérieusement, précisément par analogie. Une fois ces coups identifiés, tous les autres coups sont ignorés après une analyse superficielle.
– La profondeur du raisonnement est faible. Aucun GMI n’examine une position à plus d’une dizaine de demi coups de profondeur (alors que les ordinateurs les plus puissants peuvent examiner jusqu’à quinze ou ving t demi coups).
– La fonction d’évaluation utilisée est floue ; ellecontient des concepts difficiles à identifier clairement, comme la notion de mobilité utile, la pression d’attaque, ou de position active… ces critères remplacent l’analy se en profondeur qu’un joueur humain ne peut effectuer en raison de la limitation de ses capacités mentales. Très
souvent l’évaluation est aussi effectuée par référence à des schémas connus, faciles à expliquer dans certains cas (position cen tralisée des Tours, Fous de la « bonne » couleur pour jouer la finale) mais parfois, plus indistincts, voire liés au joueur lui-même.
– Le joueur peut effectuer des changements de plan en fonction des analyses qu’il effectue. Ces changements de plan l’amènent alors à reconsidérer les coups à examiner en profondeur.
Les études de Kroguious sont lues et orientées versune analyse utilitaire de la psychologie du joueur d’échecs. Capitaine de plusieurs équipes soviétiques, il cherche à dégager quels sont les paramètres qui interviennentdans le jugement du joueur d’échecs et renforcent ou dégradent la qualité de son analyse. Il met en évidence l’existence d’images résiduelles, à la fois à long terme et à court term e. L’image résiduelle à long terme permet de reconnaitre dans une position courante une référenc à la position déjà vue, et d’appliquer ainsi immédiatement le même type de plan.
Les études de De Groot et de Kroguious sur les joueurs d’échecs sont donc particulièrement intéressantes car elles recouvrent en fait les techniques de raisonnement des humains face à la plupart des problèmes qui leur sont posés : la base de connaissances est fondamentale et l’essentiel de la résolution se fait par référence à des exemples déjà rencontrés.
Ceci est rendu possible par la formidable capacitédu cerveau humain à stocker et trier les informations, et à retrouver instantanément (ou presque) l’ensemble des informations relatives à un objet donné, pourvu que l’on fournisse un identificateur suffisamment clair de l’objet.
Ce qu’il y a parfois de plus remarquable encore c’est que nombre d’informations peuvent disparaitre, mais certaines associations apparemment sans valeur subsistent. Il faut d’ailleurs noter la fantastique quantité d’informations que le cerveau emmagasine tout au long d’une existence. Il faut également souligner que la capacité à mémoriser les informations, si elle est importante, n’est pas primordiale.
Ce qui est réellement important c’est la capacitéque l’on a à récupérer efficacement les informations quand on est confronté à certains indices. Tous les enseignants savent bien que faire comprendre quelque chose est important, mais qu’il existe certains élèves qui, bien ayant compris, restent incapables d’appliquer la méthode apprise dès que le problème est légèrement modifié dans sa présentation.

Table des matières

INTRODUCTION
Chapitre I : Histoires et origines du jeu d’échecs
Chapitre II : La logique du jeu d’échecs
1. Connaissances sur le jeu
1. 1 Notion sur les jeux de plateau
1. 2 L’échiquier
1. 3 Le déplacement des pièces
2. Règles et but du jeu
2. 1 L’échec
2. 2 L’échec et mat
2. 3 Le pat
3. Méthodes de réflexion
3. 1 Observation
3. 2 Questionnement
3. 3 Formulation d’hypothèse
3. 4 Argumentation
3. 5 Modélisation
Chapitre III : Les jeux d’échecs et l’intelligence artificielle
1. L’évolution de l’intelligence artificielle dans le jeu d’échecs
2. Analyse théorique
2.1 Les études des psychologues
3. La programmation des jeux
4. Programmation automatique ( génération de code)
5. La logique programmée
Chapitre IV : L’intelligence artificielle et les jeux
1. L’intelligence artificielle
2. Les 2 approches de l’ IA
3. Utilisations concrètes de l’IA
3.1 Les jeux vidéo
3.2 L’évolution du jeu d’échecs
3.3 Représentation du déroulement d’une partie
Chapitre V : Les algorithmes de recherches
1. Présentation de la théorie des jeux
1.1 Concept de la solution
1.2 Equilibre de Nash
2. Les méthodes algorithmiques de bases
2.1 Arbre de recherche
2.2 Algorithme Min-Max
2.3 Alpha-Beta
2.4 La fonction d’évaluation
2.5 Bilan
2.6 Pathfinding
2.7 Algorithme de Dijkstra
2.8 L’algorithme A*
2.9 Autres solutions
2.10 Cas des jeux 3D
Chapitre VI : Les optimisations possibles
1. Optimisation de la fonction d’évaluation
1.1 Mobilité et territoire
1.2 Préservation des pièces dites importantes
1.3 Formation des pions
1.4 Réduction du nombre de possibilités à évaluer
2. Optimisation possibles
2.1 Approfondissement itératif
2.2 Le coup qui tue
2.3 La recherche aspirante
2.4 Alpha Beta trié
Chapitre VII : Les tables de transpositions
Chapitre VIII : Etat de l’art
Chapitre IX : Outils de développement du jeu
1. Choix du développement
1.1 Bibliothèque graphique
1.2 Spécificité de la SDL
1.3 Langage de programmation
1.4 L’environnement de développement (IDE = Integrated Development Environment)
2. Description de l’environnement
2.1 Description des fonctions à satisfaire
3. Schéma de l’interface
3.1 Explication du schéma
Chapitre X : Etape de programmation du jeu
1. Développement globale du jeu
2. Architecture du programme
2.1 Système d’intelligence artificielle
2.2 Arbre de jeu
2.3 Arbre de recherche
2.4 Algorithme de recherche pour la résolution de problème
2.5 La programmation des interfaces
2.6 La programmation du moteur (engine)
CHAPITRE XI : La simulation
CONCLUSION
ANNEXES
BIBLIOGRAPHIE
WEBOGRAPHIE

Télécharger le rapport complet