Mathématiques | informatique
Sébastien Delsad, 2002 | Cologny, GE
Ce travail consiste en la création d’un échiquier physique. Au travers de cet échiquier, une personne peut jouer contre un algorithme basé sur une intelligence artificielle faible.
Problématique
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? Comment, dans le cadre du concours science et jeunesse et avec l’aide d’un expert, faire évoluer le projet à l’aide d’algorithmes de machine learning? Le travail est divisé en trois 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.
Méthodologie
J’ai débuté mon travail en programmant un algorithme permettant de jouer aux échecs. La grande difficulté de cette partie est d’optimiser un maximum la vitesse d’exécution de l’algorithme. Le programme a été écrit de manière générale en C++. Seul le noyau a été écrit en C. Le langage Python aurait pu sembler plus simple à utiliser, mais celui-ci et ses bibliothèques sont trop lentes. Pour représenter l’échiquier en mémoire, différentes structures de données ont été testées. Au départ, j’ai tenté une représentation sous forme d’un tableau à deux dimensions. Cependant, j’ai dû me tourner vers l’utilisation de bitboards. Ce changement a permis d’augmenter de 8’000 fois la vitesse du programme. Par la suite, il s’est avéré impossible de créer un algorithme qui joue correctement aux échecs sans utiliser une intelligence artificielle faible. En effet, il y a trop de possibilités pour faire un algorithme basé sur des conditions. J’ai donc dû faire un travail de recherche dont le but a été de comprendre le fonctionnement détaillé des structures communes des réseaux de neurones et de certains algorithmes d’apprentissage. Au départ, j’ai étudié le fonctionnement d’AlphaGo Zero. Ensuite, j’ai essayé d’implémenter un prototype de cet algorithme. Cependant, une expérience a montré que mon algorithme simplifié est 2640 fois plus lent. Donc il faudrait au minimum 970 jours d’entraînement pour obtenir de bonnes performances. Pour cette raison, je me suis tourné vers l’algorithme Minimax et une fonction heuristique. Pour le corps, c’est-à-dire la partie physique, la meilleure solution trouvée pour reconnaître les pièces sur l’échiquier consiste à utiliser des détecteurs d’aimants. Ensuite, pour déplacer une pièce, deux moteurs steppeurs déplacent un électroaimant sur un axe à deux dimensions. Le tout est contrôlé par un Raspberry Pi, connecté par internet à un serveur qui fait les calculs complexes. La majeure partie des pièces ont été créées à l’aide d’une imprimante 3D.
Résultats
Avec l’aide de l’expert, j’ai diminué le temps de déplacement des pièces sur l’échiquier de 56%. Ensuite, différents types de réseaux de neurones ont été étudiés. Le meilleur a permis une augmentation de 6.8% de la justesse des prédictions par rapport à la fonction heuristique. Ainsi, l’échiquier permet de joueur aux échecs en un temps moyen inférieur à huit secondes et l’algorithme est compétitif face à un joueur d’échecs moyen.
Discussion
Dans l’ensemble, les différentes problématiques ont été étudiées en détails et l’intégration des différentes parties du projet est opérationnelle. Cependant, les graphiques montrent que le réseau de neurones créé dans le but de remplacer la fonction heuristique peut encore être largement amélioré. Par ailleurs, l’échiquier est un peu trop petit et il arrive parfois que des pièces interagissent entre elles à cause de l’aimant qu’elles contiennent. Il existe pour y remédier un système pour revenir en arrière. Cependant, le fait de résoudre ce problème apporterait une très bonne amélioration au travail. En outre, l’environnement fonctionne correctement et il serait très complexe d’optimiser significativement ses performances.
Conclusions
L’objectif initial a été largement atteint. Il subsiste tout de même plusieurs possibilités d’amélioration. Nous pourrions même imaginer la création d’un mode dans lequel l’utilisateur pourrait jouer physiquement contre un adversaire en ligne. Par ailleurs, le projet m’a permis d’acquérir un nombre considérable de connaissances que ce soit dans le domaine des réseaux, du machine learning ou de l’hardware.
Appréciation de l’expert
Quentin de Laroussilhe
Le travail réalisé est impressionnant de par son étendue technique, alliant des connaissances en électronique, assemblage, informatique, intelligence artificielle et algorithmique. Sébastien a effectué un travail sérieux et de qualité à la fois pendant la phase autonome où il a construit un Turc mécanique dans son ensemble mais aussi dans la période d’amélioration du projet où il a décidé de mener des travaux en apprentissage automatique.
Mention:
excellent
Prix spécial «Escher» de l’ETH Zurich
Collège Calvin, Genève 3
Enseignant: Eric von Aarburg