E-Checs

Résumé du document

Dans le cadre de l'unité d'enseignement professionnelle de l'École Centrale de Lyon, nous avons commencé début octobre 2008, le projet d'études n°115. Nous sommes arrivés à la fin de ce projet d'étude, et il est temps de dresser un bilan aussi bien de nos avancées dans la réalisation du projet, mais aussi des expériences que la gestion de ce projet nous a fournies.
Notre projet d'études s'intitule « E-Checs », et son but est la création d'un jeu d'échecs informatique permettant dans un premier temps à deux joueurs humains de s'affronter, et ensuite à un joueur humain d'affronter une intelligence artificielle (IA). De plus nous avons décidé de rendre cette IA évolutive.
Il y a donc plusieurs aspects dans ce projet d'études, pour commencer le codage du jeu d'échecs et de son interface graphique en Java, et ensuite l'élaboration d'une intelligence artificielle, avec en marge de cette dernière le processus d'évolution.
Nous avons chacun nos rôles dans ce projet d'études :
- Rafik : Codage du jeu
- Daniel : Mise en forme de l'interface graphique
- Romain et André : Intelligence artificielle
- Maël : Utilisation des réseaux de neurones
- Alexandre : Aide au codage du jeu et de l'interface graphique
Nous allons commencer par détailler la programmation du jeu ainsi que nos choix de programmation, et ensuite nous présenterons nos réalisations en matière d'intelligence artificielle.

L'origine du jeu d'échecs est difficile à déterminer. Il compte beaucoup de cousins et d'ancêtres comme le jeu de go, ou le chaturanga, jeu indien pratiqué au VIIè siècle, adopté plus tard par les Perses, qui est communément considéré comme étant à l'origine du jeu d'échecs tel que nous le connaissons, faute de référence plus ancienne. Bien entendu, le jeu a depuis subi des modifications avant de suivre les règles que nous connaissons, établies depuis le XVIIè siècle, et officialisées en 1929 par la Fédération Internationale Des Echecs.
L'âge et le succès de ce jeu expliquent certainement pourquoi, dès les débuts de l'informatique, la création de joueurs virtuels fut un défi très présent à l'esprit des informaticiens, à tel point qu'Alan Turing écrivit un programme permettant à une machine de jouer aux échecs avant même l'invention d'ordinateurs suffisamment puissants, en 1951 : il faisait à la main les calculs qu'il avait prévus pour la machine. Toutefois, permettre à une machine de jouer aux échecs requiert une grande puissance de calcul à cause de la quantité de développements possibles d'une partie à partir d'une position donnée. Ainsi, la première machine pouvant jouer aux échecs fut construite en 1957, mais il fallut attendre 1997
pour que Garry Kasparov, champion du monde d'échecs, perde au cours d'une partie se déroulant dans des conditions de temps normales face à Deep Blue, une machine capable d'évaluer 200.000.000 mouvements par seconde.
De nos jours, les ordinateurs ont fait des progrès époustouflants, et on ne compte plus les programmes d'échecs destinés au grand public, qu'ils soient gratuits ou payants, ni les fonctionnalités qu'ils proposent. On peut notamment citer Chessmaster, développé par Ubisoft, qui propose un didacticiel, des échiquiers personnalisables, 2D ou 3D, des parties mémorisées, une bibliothèque d'ouvertures qui se veut complète, des intelligences artificielles aux caractéristiques variées (offensive, défensive, etc.), problèmes, création de situation, etc. La plupart des jeux proposent également de jouer en ligne contre des joueurs du monde entier, dans des parties chronométrées ou non, avec éventuellement un classement au sein de la communauté de joueurs. Dans des parties contre l'IA, on peut choisir un niveau de difficulté, un temps imposé par coup :
le programme de jeu d'échecs est presque devenu une banalité, et la seule limite des fonctionnalités proposées est l'imagination des développeurs.

Extraits

[...] * * Remarque sur les méthodes copie : * * Dupliquer une instance d'une classe dont certains attributs sont des objets (par opposition aux types primitifs) * peut poser certains problèmes. En effet, comme les objets Java sont implicitement des pointeurs, les attributs * des deux clones risquent de pointer vers le même espace mémoire, donc modifier l'une des instaces modifierait * l'autre. Les méthodes copie sont là pour s'assurer que ce problème ne surviendra pas. * * @return Le nouveau roi. public Piece copie() { Piece clone = new Roi(getType()>0); clone.nbDeplacementPlus(nbDeplacements); return clone; } * Le getter de l'attribut {@link #nbDeplacements} * * @return L'attribut nbDeplacements. [...]

[...] Cela permet le jouer de comparer son mouvement avec l'IA. Figure 3 : Utilisation du bouton "Conseil IA" PE 115 E-checs Page 11 Action IA : Permet au joueur d'être aidé par l'IA, qui joue un coup quand le bouton est activé. Figure 4 : Utilisation du bouton "Action IA" II.4.f) Chargement et sauvegarde de partie Cette fonctionnalité offre la possibilité d'arrêter de jouer au milieu d'une partie et de la continuer plus tard. On a donc établi un système de sauvegarde et chargement en utilisant des fichiers d'extension .ech L'utilisation de ce système est très simple : Pour sauvegarder une partie : il suffit de sélectionner Sauvegarder partie au menu, et après choisir l'emplacement où l'on veut mettre le fichier. [...]

[...] * * @see Piece#casesAccAvecEchec(Echiquier, Case) * @see Echiquier#deplacement(Case, Case, int) PE 115 E-checs Page 111 public void mouseReleased( MouseEvent e ) { if(pieceEnMouvement) { pieceEnMouvement = false; case02.rangee = 8 - (y-yEchiquier+(taillePiece/2)) / tailleCase; case02.colonne = 1 + (x-xEchiquier+(taillePiece/2)) / tailleCase; if (case02.estDansEchiquier()) { //if(ech.pieceCase(case01).casesAccAvecEchec(ech, case01).contains(case02)) { //surtout pas ! if(estDans(case02,ech.pieceCase(case01).casesAccAvecEchec(ech.copie(), case01))) { int typePromotion = if(Math.abs(ech.typeCase(case01))==1 (case02.rangee==1 case02.rangee==8)) { /*System.out.print("\n\nType de promotion (2=tour, 3=cavalier, 4=fou, 5=dame) : Scanner input = new Scanner(System.in); typePromotion = input.nextInt(); if(case02.rangee==8) { /*fenetrePromotionBlancs.setVisible(true); try { fenetrePromotionBlancs.setSelected(true); } catch (java.beans.PropertyVetoException e1) /*suppressionFenetrePromotion fp = new FenetrePromotion(true, this); } else { /*fenetrePromotionNoirs.setVisible(true); try { fenetrePromotionNoirs.setSelected(true); } catch (java.beans.PropertyVetoException e2) /*suppressionFenetrePromotion fp = new FenetrePromotion(false, this); } /*suppressionFenetrePromotion desktop.add(fp); promotionEnCours = true; repaint(); return; suite des instructions sera effectuée dans internalFrameClosing } ech.deplacement(case01, case02, typePromotion); ech.afficher(); if(ech.copie().verifMat(ech.getBlancsAuTrait())) { arret = true; if(ech.getEchec()) System.out.print(" et mat else System.out.print("\n\nPat } } else { System.out.print("\n\nMouvement non légal."); } } PE 115 E-checs Page 112 System.out.print("\n"); System.out.print(case01.rangee); System.out.print(case01.colonne); System.out.print(case02.rangee); System.out.print(case02.colonne); } repaint(); e.consume(); } public void mouseMoved( MouseEvent e ) { } * Affiche à l'écran tout le contenu de la fenêtre de jeu. [...]

[...] On pouvait choisir de mémoriser chacun des échiquiers et les traiter tous ensemble à la fin ou bien n'en mémoriser qu'un seul et traiter chacun des nœuds explorés au fur et à mesure. Un échiquier contenant beaucoup d'informations (non seulement la position des pièces mais aussi la liste de tous les coups joués depuis le début de la partie), leur mémorisation est très couteuse en mémoire. C'est donc la deuxième solution qui a été adoptée. Pour la mise en œuvre de cet algorithme à un seul échiquier le parcours de l'arbre se fait en jouant les coups réellement dans le programme. [...]

[...] Ce mode devait permettre d'enregistrer de nouveaux problèmes de mat (qui seraient stockés sous forme de fichiers dans un dossier dédié) et surtout d'y jouer (face à une IA qui fera tout pour éviter d'être mise en échecs et mat au bout de la limite de temps). PE 115 E-checs Page 9 II.4) Interface graphique II.4.a) Pourquoi un Applet ? Les applets Java sont totalement indépendants de l'équipement, ils peuvent être exécutés sur un PC ou un Mac, quel que soit le système d'exploitation de ces machines (Windows ou Unix) et ils sont supportés par la plupart des navigateurs Internet. [...]