Que se passe-t-il lorsque nous appliquons des technologies modernes de pointe au jeu d’échecs séculaire? Et que se passe-t-il lorsqu’un geek ennuyé avec un surplus de puissance de calcul mène ses propres expériences à domicile étranges sur le jeu?
Cette année, un ingénieur logiciel de Pennsylvanie qui se fait appeler Tom Murphy VII a décidé de créer des algorithmes de jeu d’échecs ridiculement mauvais en utilisant tout, de l’apprentissage automatique et des réseaux de neurones à une quantité gratuite de cycles CPU – puis a opposé les mauvais algorithmes les uns aux autres pour créer un « tournoi des imbéciles. »
« C’est mon idée de m’amuser… », dit Murphy dans une vidéo humoristique décrivant les expériences.
Premiers mouvements
Murphy a le cerveau pour le réussir. Il nous raconte qu’en 2007 il a soutenu son doctorat en informatique. à Carnegie Mellon – qui était la même année, les étudiants ont commencé à tenir la conférence annuelle de SIGBOVIK le jour du poisson d’avril. Parrainé par l » Association for Computational Heresy, »c »était une sorte de groupe d »intérêt spécial satirique consacré à un chercheur fictif nommé « Harry Quizmaster Bovik, » et comprenant un appel à des articles loufoques sur des sujets comme « stupidité artificielle. »
Au cours des 11 dernières années, Murphy a été ingénieur logiciel chez Google (dans ses bureaux de Pittsburgh). Mais cette année, il a décidé de revenir pour la conférence du Poisson d’avril — et encore une fois, a contribué à ses propres recherches humoristiques.
Murphy se vante fièrement que certaines de ses présentations passées là-bas impliquaient des enquêtes ridicules qui étaient « indiscernables de la « vraie » recherche (par exemple, le premier niveau de Super Mario Bros. est facile avec des commandes lexicographiques et le voyage dans le temps a quelque 20 citations dans la « vraie » recherche académique).
Mais c’est l’année où Murphy se tourna vers les échecs.
Que les parties commencent
Dans le jeu initial de Murphy, les joueurs humains ont les yeux bandés, les forçant à se souvenir où se trouvent les pièces. Mais quel est l’équivalent pour un ordinateur? Lui dire où se trouvent les pièces mais pas quelles pièces elles sont (ou même de quelle couleur)…
Bien sûr, l’ordinateur ne serait pas non plus fourni avec les mouvements menant à une position. Il ne saurait même pas à qui c’était le tour. Oui, il est possible que le roi de l’ordinateur soit en échec — à quel point à peu près chaque mouvement est illégal, sauf un mouvement qui conduit votre roi à la sécurité. Mais pour contourner cela, Tom a créé un programme qui génère une liste de mouvements possibles, classés par ordre de préférence — à partir de laquelle le premier mouvement légal sera choisi.
« J’aime jouer contre, parce que ce n’est pas très bon », dit Murphy dans la vidéo. « Mais la question naturelle est de savoir à quel point n’est-ce pas-très-bon? »Le tester contre des programmes de jeu d’échecs prouve que oui, il perd avec une grande régularité — comme dans »à chaque fois. »
Puis il a entrepris de construire d’autres mauvais algorithmes de jeu d’échecs, afin de pouvoir comparer leurs performances relatives
On avait une préférence pour placer ses pièces sur les carrés blancs quand il joue en blanc, et sur les carrés noirs quand il joue en noir. (Son adversaire ? Un algorithme qui préférait placer ses pièces sur des carrés de couleur opposée.) À la fin, ils ont tous les deux assez mal joué. « Ils ont une préférence, mais cela n’a pas vraiment à voir avec la victoire. »En fait, ils sont tous les deux un peu pires que l’algorithme qui choisit ses mouvements au hasard.
Si vous trouvez ma vidéo complexe de 42 minutes sur 30 algorithmes d’échecs étranges en compétition dans un tournoi d’imbéciles afin d’évaluer mon programme qui joue aux échecs sans savoir quelles pièces sont sur le plateau pour être ennuyeux, c’est parce que vous ne comprenez pas l’art:https://t.co/DkaEBGrwAf
— Tom 7 (@tom7) Juillet 15, 2019
Il y avait aussi deux algorithmes qu’il a nommés « Huddle » et « Swarm » — dans lesquels un joueur automatisé recherche des mouvements en gardant ses pièces près de son propre roi, tandis que l’autre recherche des mouvements en plaçant ses pièces près du roi de son adversaire. Cela conduit parfois le roi de Huddle à être obligé de suivre ses propres pions à travers le tableau, dans au moins quelques cas, son pion est ensuite accidentellement promu en pièces plus puissantes et a par inadvertance contrôlé le roi adverse.
Mais le plus souvent, cela fonctionne dans l’autre sens. « Si vous avez une préférence pour attaquer l’adversaire, vous allez parfois l’échouer accidentellement. »Dans la vidéo, Murphy révèle que parmi les mauvais algorithmes d’échecs, celui-ci n’est étonnamment pas aussi mauvais. « ‘Essaim’ est en fait beaucoup mieux que ‘Mouvement aléatoire.' »
Et une autre stratégie réussie est un algorithme qui donne la priorité à quatre types de mouvements spécifiques (dans cet ordre): mater, contrôler, capturer une pièce ou pousser dans le territoire de son adversaire.
Mais il y a d’autres idées terribles — comme un algorithme qui cherche à refléter les pièces de son adversaire, ou à déplacer toutes ses pièces de l’autre côté du plateau. Un algorithme choisit simplement le mouvement qui vient en premier dans l’ordre alphabétique.
Et il y a un autre algorithme où chaque coup est choisi dans une liste de coups possibles — avec les choix dictés arbitrairement par les chiffres de pi
Survie en Chessland
Mais finalement son algorithme le plus élaboré a commencé par une question: quelle pièce d’échecs est la plus susceptible de « survivre » — de rester sur le plateau jusqu’à la fin de la partie et de sortir victorieuse avec toutes ses autres pièces d’échecs? Enquêtant consciencieusement sur la réponse, Murphy a visité le site d’échecs gratuit / libre LiChess.org (qui voit maintenant plus d’un million de jeux par jour). Il propose également des jeux à télécharger — Murphy en a donc téléchargé 506 000 416.
Il a résumé les résultats dans un article intitulé « Survival in Chessland », qui explique sa méthodologie. Murphy a téléchargé tous les jeux complets qu’il avait jusqu’en novembre 2018 — bien que 200 millions supplémentaires soient apparemment devenus disponibles au cours des huit mois qui ont suivi. Même son transport de novembre représentait un énorme 875 Go de jeux d’échecs, « donc le traitement de ceux-ci a pris soin de l’efficacité et du parallélisme », explique Murphy dans la vidéo.
« Heureusement, j’ai un ordinateur avec juste un nombre obscène de cœurs et une RAM vraiment excessive, donc vous devez l’utiliser pour quelque chose. »
Euh, comment obscène? Dans un e-mail, il décrit son système domestique « gratuit », un AMD ThreadRipper 2990WX à 32 cœurs. L’exécution des programmes C++ multi-threads pendant quelques heures suffisait à parcourir l’ensemble des données. « Je pense que les gens sous-estiment ce que vous pouvez faire efficacement avec une seule machine! »
» Le travail impliqué est assez simple: J’analyse le PGN (qui décrit le jeu), puis exécute les mouvements dans le jeu, en gardant une trace du sort de chaque pièce, puis additionne les comptes pour chaque destin… «
« J’ai essentiellement écrit tout le code à partir de zéro, parce que c’est plus amusant que de faire fonctionner le code des autres. 🙂 »
L’analyse de « survivabilité » de Murphy a créé de très belles visualisations des données, montrant la probabilité de survie pour chaque pièce d’échecs sur chacune des 64 cases (avec des couleurs indiquant leur probabilité d’être sur cette case à la fin de la partie.)
Et puis cela a conduit à plus de mauvais algorithmes de jeu d’échecs. Premièrement, il y a celui qui déplace simplement les pièces vers les cases où elles sont statistiquement plus susceptibles de survivre. Ou tout simplement aux places où ils sont les plus susceptibles d’être à la fin d’une partie. Et d’autres algorithmes font exactement le contraire— déplacer des pièces vers des carrés où elles ont le moins de chances de survivre (ou de se retrouver). Deux algorithmes calculent quel carré a le taux de survie le plus élevé (par rapport au taux de capture) pour une pièce sur chaque carré, un algorithme recherchant le rapport le plus élevé favorisant la survie — et l’algorithme « fataliste » recherchant le rapport le plus bas.
« Bizarrement, il a les meilleures chances de gagner de ces stratégies. »
Et finalement, il a décidé de les comparer tous au moteur d’échecs Stockfish à plusieurs niveaux (y compris un algorithme spécial où il est obligé de jouer son coup le moins prometteur). « En regardant les résultats, sans surprise, c’est la pire stratégie globale, et elle parvient à perdre pour presque tout le monde. »
Mais rappelez-vous l’algorithme original de Tom « les yeux bandés », qui ne savait pas quelle pièce occupait un carré (ou même sa couleur)? Il a décidé de l’augmenter avec un réseau de neurones, qui effectuait l’apprentissage automatique — en utilisant les milliards de positions disponibles dans les jeux de LiChess.org. Il était maintenant capable de prédire correctement les pièces réelles à chaque position avec une précision de 100% – environ un cinquième du temps. Et même quand c’est faux, on devine à tort une moyenne de 3, 22 pièces pour chaque position.
Et cela devient un point de départ pour des calculs encore plus sauvages. À un moment donné, il en déduit que tous les jeux de leur base de données passent finalement par 21 553 382 902 positions uniques. Avec 204 Go, vous pouvez tous les stocker — avec le prochain mouvement – mais il y a une autre statistique intéressante. Un énorme 76% des positions se sont produites exactement une fois. « Donc, ceux-ci prennent beaucoup de place, et ils ne sont pas très utiles pour jouer, car il est très peu probable que je les revoie un jour. »En jetant ces positions uniques, toutes les autres positions de jeu possibles peuvent être stockées avec environ 500 Mo de mémoire. Cela peut être facilement converti en un algorithme qui joue le coup le plus populaire pour n’importe quelle position qu’il rencontre (tout en échangeant un coup aléatoire s’il se trouve piégé dans une position unique).
Mais il y a un truc facile pour le battre. « Dès que je fais un mouvement un peu bizarre, ça commence à jouer au hasard. Et puis c’est très facile à battre. »
Une expérience finale implique diverses « dilutions » du moteur Stockfish — dans lesquelles son mouvement préféré est remplacé par un mouvement choisi au hasard x pour cent du temps. »
« Nous pouvons réellement évaluer à quel point un joueur est maintenant bon en le comparant directement à une dilution spécifique de Stockfish… »
Après que tous les algorithmes élaborés de jeu d’échecs de Murphy ont été minutieusement testés, il a résumé les résultats dans un tableau massif, et a conclu triomphalement sa vidéo en annonçant qu’il était enfin prêt à poursuivre d’autres intérêts.
« Maintenant, c’est au prochain projet, qui enseigne à ce chien comment jouer aux échecs. »
- Que se passe-t-il lorsque l’apprentissage automatique amène l’humanité à des réponses que nous ne comprenons pas?
- Rencontrez Sophie, le robot de fabrication de nouilles.
- Après 15 ans, les chercheurs dévoilent un bras artificiel capable de sentir.