Pourquoi NN + MCTS & AB + eval manuscrite dominent les échecs moteur?

Si je comprends bien, les moteurs peuvent être divisés en quatre groupes en ce moment: ceux qui utilisent Alpha-beta (AB) + ceux qui utilisent Monte Carlo Tree Search (MCTS) pour la recherche, et ceux qui utilisent des fonctions manuscrites + ceux qui utilisent des réseaux de neurones pour eval. Les deux moteurs les plus puissants sont Leela et Stockfish. Leela utilise MCTS + NN, tandis que Stockfish utilise AB + manuscrite.

Pourquoi ces deux combinaisons? Pourquoi pas NN + AB ou MCTS + manuscrite? Si les SCTM sont meilleurs qu'AB, pourquoi les SCTM de Komodo ne sont-ils pas plus forts que Komodo AB? Si AB est meilleur que MCTS, pourquoi Leela n'utilise-t-il pas AB à la place?

La vitesse

Les réseaux de neurones fonctionnent beaucoup plus lentement que les fonctions d'évaluation artisanales. Dans la Superfinale TCEC , Leela Chess Zero, fonctionnant sur deux GPU chacun avec des cœurs de tenseurs dédiés, est capable de rechercher environ 60 000 positions par seconde. En revanche, Stockfish, sur un seul cœur de mon PC, recherche plus de 2 millions de positions par seconde.

Alors que les moteurs modernes ont une vaste sélection de techniques pour couper les branches inutiles , la recherche d'arbre alpha-bêta est toujours une technique de force brute, nécessitant un grand nombre de positions à rechercher pour déterminer les bons mouvements.

Les SCTM, en revanche, sont beaucoup plus sélectifs et n'élargissent leur arbre de recherche qu'aux mouvements les plus prometteurs, ce qui leur permet de tirer le meilleur parti du nombre plus limité de nœuds pouvant être recherchés.

Comportement dans le pire des cas

L'une des principales exigences de la fonction d'évaluation d'un moteur basé sur la recherche alpha-bêta est qu'il doit avoir un bon comportement dans le pire des cas . En effet, toute erreur importante dans l'évaluation, aussi rare soit-elle, peut facilement se propager à la racine et conduire à un coup horriblement incorrect.

De par leur complexité, les réseaux de neurones sont sujets au surapprentissage et ne peuvent être aussi bons que les données utilisées pour les former. Par exemple, dans le match 80 de la Superfinale de la saison 14 de TCEC , le mouvement 47 Lc0 n'a apparemment pas été dérangé par la reine supplémentaire de Stockfish, évaluant la position comme un cool +0.77, tandis que Stockfish (et la plupart des autres moteurs) arborait une évaluation de +8.31. Une explication populaire à cela est que Lc0 n'a peut-être pas eu un nombre important de jeux avec plusieurs reines sur le plateau dans son ensemble d'entraînement.

Les réseaux de neurones ont donc un mauvais comportement dans le pire des cas et sont donc susceptibles de mal fonctionner avec la recherche alpha bêta. Les SCTM, en revanche, permettent de compenser un score incorrect attribué à un poste en le faisant la moyenne avec des scores raisonnables attribués à des positions proches dans la recherche.

Tranquillité

Tous les moteurs alpha-bêta puissants utilisent une technique appelée recherche de repos , une forme restreinte de recherche alpha-bêta appliquée aux nœuds foliaires, en reconnaissant que leurs fonctions d'évaluation artisanales ne fonctionnent bien que dans des positions "silencieuses", où il n'y a aucune capture ou vérification en attente .

Par exemple, immédiatement après la première moitié d'un échange de reine, une fonction d'évaluation artisanale pourrait vous dire que le côté qui vient de faire prendre sa reine est complètement perdu, tandis qu'un réseau de neurones peut comprendre que la reine sera bientôt recapturée.

Cela rend les fonctions d'évaluation artisanales tout aussi inappropriées pour les SCTM en raison de l'absence de recherche de repos, ce qui fait que les fonctions artisanales fonctionnent mal la plupart du temps (bien que Komodo 12 MCTS contourne cette restriction en utilisant de toute façon de courtes recherches alpha-bêta , pour obtenir des positions de repos et permettre ainsi à son évaluation artisanale de retourner un score raisonnable)

AB et MCTS ne sont pas nécessairement meilleurs les uns que les autres sur leurs mérites propres. C'est juste que ce sont des algorithmes de recherche différents qui fonctionnent mieux avec des fondations différentes. Pour le NN, les SCTM fonctionnent bien car ils permettent au moteur d'explorer les branches qui se portent mieux. Cela donne au moteur plus de liberté pour regarder ce qu'il "veut".

Pendant ce temps avec AB, toutes les branches doivent en principe être examinées. En effet, même avec l'approfondissement itératif, le moteur ne regarde jusqu'à présent que sur chaque branche à chaque itération. Il ne sait donc pas si une branche gagne réellement pour un côté, même si elle semble perdre à une profondeur limitée.