Ensuite, je me suis assis là et j'ai admiré AlphaZero contre Stockfish . Et maintenant, je suis revenu sur le sujet en rapport avec la tâche d'optimisation des réseaux de neurones, qui doit parfois être effectuée au travail (hélas, moins que ce que nous voudrions). Il me semble que ces tâches peuvent être étroitement liées, j'ai donc voulu en quelque sorte systématiser mes idées.
Les échecs sont un jeu avec des informations complètes, basé sur une énumération d'options (ainsi que des dames, go, etc.).
Le problème, cependant, est que l'arbre de variation aux échecs croît assez rapidement (bien que significativement plus lent que dans Go). Par exemple, avec une planche complète de pièces dans une position calme, chaque côté a environ 10 suites raisonnables. Ainsi, en seulement 3 coups de noir et blanc (6 demi-coups), nous pouvons obtenir un million de positions de celui-ci. Aussi, prenons en compte le fait que le jeu moyen entre les personnes dure 40 à 50 coups (entre les ordinateurs - 80 à 100). Ainsi, nous arriverons à la conclusion qu'une erreur de calcul complète de l'arbre des variantes est impossible pour la plupart des positions, ce qui signifie que nous devons nous concentrer sur le découpage partiel de l'arbre de recherche, tant en largeur qu'en profondeur. Voyons maintenant comment les humains et les machines ont géré ce problème. Je vais commencer par un petit aperçu historique.
"Échecs de protéine".
Les échecs sont connus depuis environ 1400 ans, mais les premiers grands tournois ont commencé à se tenir au milieu du 19e siècle. C'était une période de batailles ouvertes et romantiques. Les adversaires ont essayé d'introduire rapidement des pièces dans la bataille, d'ouvrir la position et de lancer une attaque sur le roi. Personne n'a particulièrement envisagé les concessions matérielles et positionnelles. Mais étonnamment, l'antagoniste des échecs romantiques, Wilhelm Steinitz, est devenu le premier champion du monde officiel .
Il a jeté les bases du jeu positionnel . En grande partie grâce à Steinitz, nous avons commencé à fonctionner avec des concepts tels que «structure de pion», «carrés forts et faibles», «bonnes et mauvaises pièces». C'est ce qui a introduit aux échecs l'élément de stratégie basé sur des avantages à long terme. Steinitz a développé une approche positionnelle et puni sans relâche ses adversaires pour les sacrifices matériels et les défauts de position. Emmanuel Lasker , qui lui succéda sur le trône d'échecs, parlait très bien du premier champion : « Le talent de Steinitz en tant que joueur pratique était inférieur au talent de Blackburn ou de Zukertort, qu'il a néanmoins vaincu, car c'était un grand penseur, mais ils ne l'étaient pas .Steinitz a formulé les principes de base de l'évaluation de la position et les plans de jeu qui en résultent dans une langue de haut niveau (dans ce cas, l'allemand).
En conséquence, il les a rendus disponibles pour étude par d'autres personnes . Cela a façonné ce que nous appelons l'approche humaine des échecs. Nous prenons très au sérieux l'élagage de l'arbre des variations aux échecs sur la base de principes de position. Certains mouvements sont annulés car ils conduisent à une mauvaise position sur l'horizon calculé. Certains parce qu'ils conduisent à des concessions à long terme, d'autres parce qu'ils sont sans but. En conséquence, nous calculons une très petite partie des options possibles.
Une meilleure compréhension des échecs était essentiellement le développement des idées posées par le premier champion. Des concepts tels que blocus, prévention, domination sont apparus. Les joueurs d'échecs ont commencé à étudier les principes de jeu des positions typiques découlant de diverses ouvertures (chaînes fermées, un pion isolé, etc.). D'une manière ou d'une autre, des positions proches du bilan matière ont été étudiées. Mais il y avait aussi des exceptions - par exemple, le jeune Mikhail Tal jouait dans un style différent. Il a créé des positions déséquilibrées nettes avec une violation du rapport matériel (plus tard, Garry Kasparov a également démontré un jeu similaire). Peu habitués à un tel jeu, les adversaires se sont succédés. Tal est devenu champion du monde en 1960, mais a perdu le match revanche un an plus tard. Dans la seconde moitié du XXe siècle, l'objectif de l'étude s'est déplacé vers le début du jeu - l'ouverture. Avec la main légère de Mikhail Botvinnik (6e champion du monde) et Garry Kasparov (13e), les joueurs d'échecs ont commencé à consacrer la part du lion de leur temps à l'élaboration de variantes d'ouverture spécifiques. En utilisant de plus en plus d'ordinateurs dans ce processus. En conséquence, de nombreuses variantes d'ouvertures populaires sont développées jusqu'à des positions où le résultat du jeu est prédéterminé. Cela conduit à une certaine émasculation des échecs, ainsi qu'à la nécessité de mémoriser un grand nombre de variations pour ne pas être vaincu dès l'ouverture. Sans surprise, le pendule a basculé dans la direction opposée ces derniers temps. Le champion du monde actuelMagnus Carlsen s'efforce plutôt d'obtenir non pas un avantage à la fin de l'ouverture, mais une position de jeu qui n'est pas «usée» par les moteurs informatiques. La sévérité de la lutte est reportée aux étapes ultérieures du jeu (middlegame, endgame).
"Échecs en silicone".
Comme l'a bien dit Aleksandr Kronrod , les échecs sont la «mouche des fruits» de l'intelligence artificielle. Leur étude a commencé avec l'avènement des premiers ordinateurs et a attiré des pionniers tels qu'Alan Turing et Claude Shannon.... C'est Shannon qui a proposé la première estimation de la valeur des pièces d'échecs "King = 200, Queen = 9, Rook = 5, Bishop = 3, Knight = 3, Pion = 1". Curieusement, c'est cette simple évaluation qui a déterminé le développement de la programmation d'échecs pour les 70 prochaines années. Shannon a également prédit la division des programmes d'échecs en «rapide» (force brute) et «intelligent» (intelligent). Les programmes «rapides» passent en revue toutes les options possibles jusqu'à une certaine profondeur, évaluent la position à l'aide d'une simple fonction d'évaluation (comme le rapport de matière) et sélectionnent le meilleur mouvement en utilisant le principe minimax... Les programmes «intelligents» utilisent des algorithmes plus complexes et varient la profondeur de recherche de la même manière qu'un humain. Le 6ème champion du monde Mikhail Botvinnik a été impliqué dans la création d'un tel algorithme dans les dernières années de sa vie. Cependant, sans grand succès, comme beaucoup d'autres créateurs de programmes «intelligents». Car dans sa troisième prédiction, Shannon avait tort - les programmes "intelligents" échouaient constamment dans la lutte contre les "rapides". La raison en est que la force brute est très bien parallélisée et optimisée. Et l'estimation simple de Shannon s'est avérée assez stable et robuste. Car, comme le savent les joueurs d'échecs, tout avantage de position sera tôt ou tard transformé en un avantage matériel. Alors que les principes de l'évaluation de la position se prêtent bien pire à la formalisation.
Ils nécessitent des calculs séquentiels encombrants et sont mal optimisés. En conséquence, à mesure que les performances de l'ordinateur augmentaient, les programmes «rapides» ont commencé à dominer. C'est ainsi que s'est formé le courant principal des échecs informatiques, qui est remarquablement différent des échecs humains - le busting à une certaine profondeur en utilisant le découpage alpha-bêta (et quelques autres heuristiques) et l'estimation de position selon Shannon. En outre, les programmes ont commencé à développer activement et à utiliser les bases d'ouverture (lorsque le jeu n'est pas encore loin de la position de départ) et de fin de partie (lorsque le nombre de pièces est petit et que l'arbre des variantes peut être entièrement calculé). Et les performances des ordinateurs augmentaient tout le temps, et les programmeurs ne restaient pas inactifs, optimisant constamment les moteurs. Le 11 mai 1997, un événement marquant s'est produitDeep Blue Computer a battu le champion du monde Garry Kasparov dans un match de 6 matchs.
Immédiatement après cela, IBM a arrêté ce projet jamais bon marché. Des puces qui accélèrent les calculs d'échecs ont été créées spécialement pour Deep Blue ! Cependant, même sans eux, la supériorité d'un ordinateur sur une personne était déjà évidente. Deep Fritz , Deep Junior , Rybka , Komodo , Stockfish ont commencé à écraser sans pitié les grands maîtres, leur donnant même du matériel devant eux ... Entre eux, cependant, ils ont joué avec des succès variables - les résultats des championnats du monde parmi les programmes peuvent être trouvés ici .
Tout a changé lorsque les créateurs d'AlphaZero, après avoir battu le champion du monde dans le jeu de Li Sedol , se sont finalement mis aux échecs. Le résultat était phénoménal - après 4 heures de jeu avec moi-mêmeAlphaZero a battu StockFish en remportant 28 parties et en en tirant 72. Après un an, DeepMind a fait une expérience plus propre , permettant à Stockfish d'utiliser les livres d'ouverture et de fin de partie. Pourtant, le résultat +155 -6 = 839 ne laisse aucun doute sur qui est actuellement le joueur le plus fort du monde.
Comprenons comment s'est arrangé ce nouveau miracle. (Il existe déjà tout un livre pour ceux qui veulent approfondir les scripts python ). L'algorithme principal est la recherche arborescente de Monte Carlo... C'est, bien sûr, excessif, ce qui rend AlphaZero similaire à d'autres programmes d'échecs. Mais le mot Monte Carlo ne doit pas être trompeur - la recherche est contrôlée par un réseau de neurones (pour Go, c'était 80 couches, je ne sais pas laquelle ici) et est étroitement ciblée. AlphaZero tronque l'arbre de force brute pour des considérations de position, tout comme le fait un humain! Comparé à Stockfish, Alphazero utilise presque 1000 fois moins d'options... Elle pelle beaucoup moins de «déchets», mais calcule plus profondément et avec plus de précision les options les plus fortes les plus probables. Par conséquent, il gagne même avec moins de temps ou sur un matériel plus faible. Et le plus important est qu'AlphaZero "étudie" les échecs exclusivement sur "sa propre expérience". Elle n'avait aucune information a priori. Sa «compréhension» n'est pas entachée par «l'évaluation de Shannon». Elle a sa propre compréhension unique de la vision des échecs et du style de jeu, ignorant souvent l'équilibre matériel (comme le jeune Tal!).
Quelles conclusions pouvons-nous tirer de cette merveilleuse expérience?
- Il réfute de manière décisive toutes les considérations sur l'émasculation des échecs. L'apparence même d'un joueur qui joue dans un style jamais vu auparavant et démontre une supériorité totale sur ses concurrents indique que les possibilités du jeu sont loin d'être épuisées.
- . 4 (« ») ! – ( -) . . . AlphaZero () .
- – ? – , , .. , . AlphaZero – – –. ? , , . , . . . . SkyNet deviendra un peu moins lointain et un peu plus sinistre ... En attendant, je serais reconnaissant pour des liens, des articles et des idées sur la façon d'aborder ce problème.
PS. Mais vous regarderez les matchs . J'ai eu un plaisir incomparable.