Jouer aux échecs avec un algorithme d'apprentissage automatique - Sébastien Delsad PDF

Preview

Summary

Jouer aux échecs avec un algorithme d’apprentissage automatique Sébastien Delsad Expert : Quentin de Laroussilhe Figure 1 – Le robot permettant de jouer aux échecs. Travail du Concours national de Science et jeunesse Collège Calvin, Genève 2019 Table des matières Introduction 1 1 L’environnement 3 1...

Description

Jouer aux échecs avec un algorithme d’apprentissage automatique Sébastien Delsad Expert : Quentin de Laroussilhe

Figure 1 – Le robot permettant de jouer aux échecs.

Travail du Concours national de Science et jeunesse Collège Calvin, Genève 2019

Table des matières Introduction 1 L’environnement 1.1 Les règles des échecs . . . . . . . . . . . . . . 1.2 Le langage de programmation le plus adapté 1.3 Représentation de l’échiquier . . . . . . . . . 1.4 Déplacement des pièces . . . . . . . . . . . . 1.4.1 Fonctionnement général . . . . . . . 1.4.2 Le pion, le cavalier et le roi . . . . . . 1.4.3 Les autres pièces . . . . . . . . . . . . 1.5 Coups spéciaux . . . . . . . . . . . . . . . . . 1.6 Créer une bibliothèque Python en C++ . . . 1.7 Quelques fonctions importantes . . . . . . . 1.8 Analyse des performances . . . . . . . . . . .

1

. . . . . . . . . . .

3 3 4 5 7 7 9 10 11 12 12 16

2 Le cerveau 2.1 Définition du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Introduction au machine learning ou apprentissage automatique . . . . . . . . 2.2.1 Les réseaux de neurones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Algorithme d’optimisation d’un réseau de neurones . . . . . . . . . . . . 2.2.3 Le deep learning ou apprentissage profond . . . . . . . . . . . . . . . . . . 2.3 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Algorithmes basés sur des connaissances humaines . . . . . . . . . . . . 2.3.2 Algorithmes basés sur un réseau de neurones à apprentissage supervisé 2.3.3 AlphaGo zero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Programmation du cerveau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Programmation de Minimax . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Programmation d’AlphaGo Zero . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Problèmes majeurs rencontrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Analyse des performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19 19 19 20 23 28 28 28 31 31 35 36 38 40 41

3 Le corps 3.1 Reconnaître les pièces sur l’échiquier . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Déplacement d’une pièce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43 43 44

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

i

Table des matières 3.2.1 Mécanisme physique . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Fonctionnement théorique du logiciel . . . . . . . . . . . . . . . . 3.3 Circuit électrique de l’échiquier . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Le circuit dédié à l’électroaimant . . . . . . . . . . . . . . . . . . . . 3.3.2 Le circuit pour faire fonctionner les moteurs pas à pas . . . . . . . 3.3.3 Le circuit des interrupteurs et des capteurs . . . . . . . . . . . . . . 3.4 Matériel de construction de l’échiquier . . . . . . . . . . . . . . . . . . . . 3.4.1 Intérieur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Extérieur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Explication du code de fonctions importantes liant le corps et le cerveau 3.5.1 La fonction get move . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.2 La fonction move nb magnet . . . . . . . . . . . . . . . . . . . . . . 3.5.3 La fonction Astar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.4 La connexion réseau liant le corps et le cerveau . . . . . . . . . . . 3.5.5 Problèmes rencontrés . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Améliorations 4.1 Les différentes améliorations possibles . . . . . . . . . . . . . . . . . . . 4.1.1 Ajout d’un mode IA versus IA . . . . . . . . . . . . . . . . . . . . . 4.1.2 Prototype d’AlphaGo Zero . . . . . . . . . . . . . . . . . . . . . . . 4.1.3 Amélioration de la fonction heuristique avec du ML . . . . . . . 4.2 Amélioration de la partie physique . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Augmentation de la vitesse de déplacement de l’électro-aimant 4.2.2 Anticipation du départ du prochain déplacement . . . . . . . . . 4.3 Démarches d’amélioration du cerveau . . . . . . . . . . . . . . . . . . . 4.3.1 Première méthode pour la génération d’un dataset . . . . . . . . 4.3.2 Deuxième méthode pour la génération d’un dataset . . . . . . . 4.3.3 Troisième méthode pour la génération d’un dataset . . . . . . . 4.3.4 Format d’enregistrement dans le fichier . . . . . . . . . . . . . . . 4.3.5 Création du réseau de neurones . . . . . . . . . . . . . . . . . . . 4.3.6 Amélioration du réseau de neurones . . . . . . . . . . . . . . . . 4.3.7 Utilisation du réseau de neurones en C++ . . . . . . . . . . . . . 4.4 Tentatives d’amélioration de la fonction heuristique . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

44 46 47 48 50 51 53 53 54 56 56 57 58 60 61

. . . . . . . . . . . . . . . .

63 63 64 64 64 64 64 65 66 67 69 70 70 72 77 79 80

5 Estimation des coûts

83

Conclusion

85

Remerciements

87

A Illustrations du projet A.1 Vu externe du plateau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Démonstration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Diagramme général du programme . . . . . . . . . . . . . . . . . . . . . . . . . .

89 89 89 91

ii

Table des matières Bibliographie

99

iii

Introduction En décembre 2017, un algorithme de machine learning ou d’apprentissage automatique développé par DeepMind, une entreprise de Google, a appris après trois jours à battre au jeu de Go les meilleurs joueurs humains et les quelques algorithmes existants. La particularité de cet algorithme est qu’il n’utilise aucune connaissance humaine et qu’il a surpassé tout être humain en très peu de temps sachant que le nombre estimé de positions différentes dans le jeu de Go est d’E+174 [99]. A savoir que les algorithmes des années précédentes ne battaient pas « le niveau de débutant en club » comme le montre un article paru en avril 2002 : « Le meilleur programme de Go a seulement le niveau de débutant en club » [5]. Depuis dix ans, les ordinateurs battent les humains aux échecs, jeu moins complexe que le jeu de Go. Mais la progression des ordinateurs est très intéressante. Au cours des trente premières années, l’évolution des algorithmes est linéaire bien que la capacité et la puissance des ordinateurs augmentent exponentiellement selon la loi de Moore [92]. Cependant, nous observons qu’un ordinateur surpasse les autres vers 1996 : Deep Blue. C’est en réalité un superordinateur (un ordinateur extrêmement rapide). Mais celui-ci utilise un l’algorithme de machine learning (Minimax), se basant sur des connaissances humaines. Ainsi, il ne peut pas encore battre à tous les coups le meilleur joueur humain. Quelques années plus tard en 2008, de nouveaux algorithmes apparaissent inspirés par Deep Blue. A partir de ce moment, le classement des ordinateurs dépasse les humains. Cette période est couronnée par Stockfish qui demeura pendant quelques années le meilleur joueur d’échec. Cependant cet algorithme se base encore sur des connaissances humaines. En octobre 2017, un algorithme, AlphaGo Zero, révolutionne le machine learning en apprenant strictement par lui-même et c’est ainsi que les meilleurs joueurs de Go ont pu être vaincus. Quelques mois plus tard, Alpha Zero (une généralisation d’AlphaGo Zero) sort. Il est capable de jouer au jeu de Go, aux échecs et au shogi (version japonaise des échecs) et bat de loin n’importe quel être humain et ordinateur après seulement trois jours d’apprentissage. Alpha Zero est classé autour des 3750 points Elo [42], alors que Stockfish est classé autour des 3400 points et les meilleurs humains 2800 points. Un joueur qui est classé 100 points Elo au-dessus d’un autre a 64% de chance de gagner [90]. Les ordinateurs surpassent donc aujourd’hui les humains au jeu d’échec. Le but de ce travail de recherche est de comprendre dans les détails comment fonctionnent les meilleurs algorithmes de machine learning, y compris AlphaGo Zero, pour pouvoir ensuite en faire une version qui joue aux échecs. Cela en sachant qu’il n’y a aucun espoir que l’algorithme 1

Introduction créé soit compétitif face aux meilleurs joueurs d’échecs même si ce jeu a une complexité de trillions de trillions de fois inférieure à celle du jeu de Go (E+54 fois moins). En effet, même en m’inspirant des meilleurs algorithmes existants, DeepMind est une entreprise avec des centaines de programmeurs qui ont travaillé pendant plusieurs années en investissant plusieurs millions de dollars. Finalement, une interface utilisateur physique sera créée, c’està-dire un échiquier avec lequel un être humain peut directement jouer contre l’algorithme. Comment implémenter les règles des échecs de manière optimale? Comment fonctionne AlphaGo Zero, l’algorithme de DeepMind ? Comment implémenter un algorithme de machine learning basé sur AlphaGo Zero ou sur un autre algorithme efficace ? Comment faire une interface utilisateur captivante ? Le travail est divisé en trois grandes parties : l’environnement, le cerveau et le corps. Ces sections traitent respectivement des règles des échecs et de la génération de coups permis à partir d’une certaine position, de l’algorithme qui décide du meilleur coup à jouer selon son environnement (l’état de l’échiquier) pour gagner et finalement de l’interface utilisateur physique. C’est une analogie à l’être humain.

2

1 L’environnement

1.1 Les règles des échecs Les échecs sont un jeu de stratégie opposant deux joueurs autour d’un échiquier composé de 8x8 cases. Un joueur possède des pièces noires et l’autre des pièces blanches. Ce dernier commence toujours. Chacun des opposants possède 16 pièces : un roi, une reine, 8 pions, 2 tours, 2 chevaux et 2 fous. La partie commence avec les pièces disposées tel que la figure 1.1 le montre. Les pions peuvent avancer d’une seule case, sauf s’il y a une pièce sur leur case de destination. Si le pion se trouve à sa position initiale il peut aussi avancer de deux cases en avant. Par ailleurs, il peut manger une pièce adverse en se déplaçant d’une case sur la diagonale. Un pion peut se transformer en toute autre pièce, en dehors du roi, (au choix du joueur qui détient le pion en question) lorsque ce pion atteint le bout de l’échiquier et qu’il ne peut plus avancer.

Figure 1.1 – Position initiale des pièces sur un échiquier (tirée de [24]).

Si un pion P se trouve sur la cinquième rangée et qu’un pion adverse avance de deux cases pour se retrouver une case à gauche ou à droite du pion P, celui-ci peut avancer d’une case sur la diagonale du côté du pion adverse et en même temps le manger. Cette prise s’appelle le « coup en passant ». Les cavaliers sont les seules pièces à pouvoir sauter par-dessus d’autres pièces. Ils se déplacent de deux cases sur un axe horizontal et trois cases sur un axe vertical ou inversement. Les tours se déplacent sur un axe horizontal et un axe vertical. Contrairement aux fous qui ne se déplacent que sur des axes diagonaux. La reine peut se déplacer dans toutes les directions sans sauter de pièce. Le roi peut bouger 3

Partie 1. L’environnement d’une seule case dans toutes les directions, temps qu’il n’est pas attaqué sur sa case de destination. Si le roi d’un joueur se fait attaquer et que celui-ci ne peut se dégager de l’attaque, le joueur en question a perdu. Si c’est au tour d’un joueur, mais que celui-ci ne peut jouer aucun coup légal et que son roi n’est pas attaqué il y a pat (partie nulle). De plus, si aucun joueur n’a mangé de pièce adverse ou fait de transformation de pion en 50 coups ou encore que trois coups identiques sont enchainés, il n’y a ni gagnant ni perdant. Finalement, si le roi et une des tours d’un joueur n’ont pas encore été déplacés, il peut y avoir un roque. C’est un déplacement du roi de deux cases vers une des deux tours. La tour se retrouve dans ce cas toujours sur la case à côté du roi, mais de l’autre côté de celui-ci. Il faut aussi qu’il n’y ait aucune pièce entre le roi et la tour en question et qu’aucune des 4 ou 5 cases où le roque se joue ne soit attaquée. Les règles officielles du jeu d’échecs peuvent se trouver sur le site de la fédération française des échecs [22].

1.2 Le langage de programmation le plus adapté Le choix du langage de programmation pour l’environnement est très sensible, car il faut que ce langage soit facilement compatible avec celui utilisé dans la création de l’algorithme qui décide du meilleur coup. Par ailleurs, l’optimisation est la difficulté majeure de la création de l’environnement. En effet, plus l’algorithme qui permet de déterminer les coups possibles à partir d’une certaine position est rapide, plus l’ordinateur pourra générer de jeux rapidement et donc être plus rapidement efficace. Par ailleurs, sachant que les échecs sont d’une complexité extrêmement élevée, la mémoire demandée par le programme évolue à une vitesse exponentielle. Parmi les langages de programmation que je maîtrise (C, C++, Python, javascript, assembleur et Java), j’ai choisi le C++. En effet, si l’environnement devait primordialement être lié à une application web, javascript aurait été une bonne solution, mais la priorité est l’optimisation. L’assembleur est extrêmement rapide, mais il est très complexe, peu documenté et très difficile à écrire à cause de son manque de clarté. Java, à l’inverse, est très haut niveau c’est-à-dire qu’il y a beaucoup de transformation entre le code écrit par le programmeur et le code exécuté par la machine. Cela permet de faciliter l’écriture du programme au détriment de la performance qui s’en trouve ralentie. Python semble être une très bonne solution. En effet, il est riche en bibliothèques disponibles (du code déjà écrit qui facilite considérablement le développement d’un programme en évitant au programmeur de devoir « réinventer la roue ») c’est d’ailleurs pour cette raison que j’utiliserai ce langage pour la création du réseau de neurones plus tard. De plus, le lien entre les langages de programmation de l’environnement et du cerveau devrait être faisable, car la plupart des bibliothèques Python sont développées en C++. J’ai donc commencé par évaluer la vitesse de génération des coups légaux de la bibliothèque « python-chess » [23], 4

1.3. Représentation de l’échiquier une bibliothèque qui permet de jouer aux échecs en python (génération de coups légaux, représentation graphique de l’échiquier, etc.). Mais cette bibliothèque me paraissait trop lente. Je me suis donc tourné vers le C++, un langage très utilisé (notamment grâce à sa lisibilité) dans la création d’applications optimisées, même s’il reste plus haut niveau (donc plus lent) que le C. Par ailleurs, le lien entre le C++ et Python se fait très facilement et efficacement à l’aide de bibliothèques. J’ai alors développé ma propre bibliothèque pour python en C++ et l’ai comparé avec « python-chess ». Le résultat est médiocre : mon programme est à peine plus rapide (-2%) et beaucoup moins facile d’utilisation. Je décide alors de changer certains éléments cruciaux à la base de mon code et en même temps d’écrire une autre version du programme en C pour la comparer à l’algorithme écrit en C++. La fonction en C met 0,01 seconde pour être exécutée lorsque la même fonction en C++ prend 0,10 seconde. Cette différence d’un facteur dix n’est pas négligeable. Ainsi, je décide de sacrifier du temps et de la clarté pour augmenter de 10 fois la vitesse. Par ailleurs, le lien entre le C et le C++ est très facile à mettre en place (le C++ ayant les mêmes bases que le C), par conséquent je peux lier le C au Python. C’est ainsi que je me suis lancé dans ce projet avec le langage C. La version finale fonctionne correctement, bien que le code soit peu lisible et assez instable. En effet, le programme ne marche qu’en utilisant un compilateur très précis (gcc). En essayant de le compiler avec Visual Studio, un compilateur produit par Microsoft et utilisé par des milliers de développeurs qui apprécient son ergonomie et ses outils, le programme compile mais ne me donne pas les résultats recherchés. Ne comprenant pas pourquoi, j’ai continué d’utiliser gcc. J’ai même commencé la programmation du cerveau en C. Entre temps, j’effectue une mise à jour du compilateur qui n’avait pas été faite. C’est alors que le programme ne compile plus. Je décide alors de réécrire tout le projet de manière beaucoup plus lisible et cohérente avec Visual Studio pour me permettre de trouver les erreurs dans le programme plus facilement. Aussi, je le réécris en C++ et me rends compte que l’option du compilateur (-O2) qui permet d’optimiser le code n’avait pas été utilisée. En comparant le code C optimisé et le code C++ optimisé, la différence de performance est négligeable comparée au facteur 10 trouvé plus tôt. C’est donc pour ces raisons que je choisis finalement le C++. Dans la plupart des projets, choisir un langage de programmation est très rapidement fait. Cependant, pour un projet très large et devant être ultra optimisé, le choix du langage peut s’avérer compliqué et surtout déterminant quant à l’issue du travail.

1.3 Représentation de l’échiquier Une des premières questions que nous pouvons nous poser si nous voulons créer un programme qui sait déterminer les coups légaux à partir d’un échiquier est comment représenter un échiquier pour l’ordinateur. Nous pouvons aisément manier des nombres, des chiffres, 5

Partie 1. L’environnement des lettres et des listes de valeurs avec un langage de programmation. Ainsi, la première solution qui m’est venue à l’esprit est de faire une liste de liste de lettres. Nous obtenons donc un tableau en deux dimensions (de la même taille qu’un échiquier) qui contient des lettres. Ces lettres représentent les pièces, par exemple « p » pour un pion noir et « P » pour un pion blanc. Ce modèle est très pratique pour déboguer le programme, car il est facile de modifier n’importe quelle case du tableau. Il est aussi très facile d’afficher l’échiquier sur un écran en faisant une boucle dans une boucle, chacune traversant une des deux listes. Par ailleurs, cette structure de données est très intuitive pour la suite de la programmation de l’algorithme. En effet, pour déplacer un fou par exemple, il suffit plus ou moins de se déplacer dans chacune des dimensions de +- 1, 2, 3 etc. et de placer une lettre dans la case d’arrivée. Ce modèle m’a permis d’avoir une bibliothèque pour jouer aux échecs après environ un mois de travail. Cependant, lors de la comparaison avec la bibliothèque en python « python-chess » comme mentionné précédemment, les performances de mon programme n’ont pas été assez satisfaisantes. En parlant plus tard avec un ami, j’apprends qu’il existe d’autres moyens de représenter un échiquier. Je me documente alors sur Internet et découvre plusieurs méthodes dont la notation Forsyth-Edwards (FEN) [91] et le bitboard. La notation FEN...