Comment les moteurs se sont-ils améliorés depuis Deep Blue?

Les moteurs d'échecs informatiques se sont améliorés depuis que Deep Blue a battu Kasparov en 1997.

Les algorithmes se sont-ils améliorés ou les améliorations sont-elles principalement dues aux mêmes algorithmes fonctionnant plus rapidement grâce à un matériel plus rapide, etc.?

Dans le premier cas, ces améliorations algorithmiques sont-elles publiques?

Et si oui, quelles ont été les améliorations? Où puis-je les lire?

Vous pouvez peut-être jeter un œil à TalkChess , un forum dédié aux échecs informatiques. J'ai trouvé un fil récent qui pourrait vous intéresser: Progrès en 30 ans par quatre intervalles de 7 à 8 ans

Quelques matchs entre les (anciens) meilleurs moteurs sont joués sur le même matériel . Le test suggère que ces dernières années (2002-2017), le gain est principalement dû aux améliorations logicielles. Dans le test, Stockfish (2017) a marqué un impressionnant 94/100 contre RobboLito (2009), tandis que RobboLito, à son tour, a écrasé Shredder (2002) avec 92/100.

Remarque importante: le calcul parallèle n'étant pas implémenté dans les moteurs plus anciens, le test a été réalisé sur un seul cœur. Par conséquent, le gain matériel des machines parallèles n'est pas mesuré. D'un autre côté, vous pourriez faire valoir que le calcul parallèle est également un gain logiciel: il n'est pas facile de concevoir et de mettre en œuvre une parallélisation efficace et bien adaptée à l'algorithme de recherche.

Le moteur Stockfish est open source, donc les améliorations algorithmiques sont publiques. Beaucoup de documentation peut être trouvée sur https://chessprogramming.wikispaces.com

Je ne peux pas parler de l'algorithme utilisé pour Deep Blue, mais je vais essayer d'expliquer les améliorations de la programmation des échecs. La vitesse est la plus grande amélioration. Deep Blue utilisait des ordinateurs dédiés multiprocesseurs, donc une comparaison n'est pas vraiment possible.

https://chessprogramming.wikispaces.com/ est une excellente source, mais il est difficile de s'y retrouver.

Il y a 3 fonctions principales qui sont modifiées pour améliorer un moteur d'échecs: les fonctions d'évaluation, de génération de mouvement et de recherche.

L'évaluation est la plus difficile à programmer, car il existe de nombreuses exceptions aux règles. L'espace sur le disque dur devenant moins cher, la fonction eval permet d'évaluer plus d'exceptions.

La génération de mouvements, ainsi que la réalisation et l'annulation d'un mouvement, consomme beaucoup de mémoire car elle doit être préformée tant de fois. Les fonctions de génération les plus courantes sont la boîte aux lettres, le bitboard, 0x88, 8x8, les cartes étendues (10x10, 10x12) et un tableau / tableau de déplacement prédéterminé (* J'utilise une table de déplacement indexée). L'opinion actuelle est que les bitboards sont les plus rapides, et l'utilisation de bitboards magiques accélère cela jusqu'à 30%. Le Dr Robert Hyatt, professeur et créateur du moteur d'échecs cratfy, ne prétend aucune augmentation significative de la vitesse.

La fonction de recherche précoce était les fonctions primitives min-max. Fondamentalement, vous essayez de maximiser le score du côté à déplacer et de minimiser le score de l'adversaire. Alpha-Beta a été la première amélioration. Ils ont réduit le nombre de mouvements recherchés par la table de transposition, les valeurs de coupure, les fenêtres d'aspiration et l'heuristique historique. Ce sont des recherches approfondies. Il y a aussi la recherche d'approfondissement itérative interne qui essaie de rechercher le (s) "meilleur (s)" mouvement (s) le plus profond en espérant que la recherche d'autres mouvements s'avérera infructueuse.

REMARQUE: ma table d'index. GNUChess et Jester utilisent tous deux un tableau d'index pour générer leurs déplacements. Ils initialisent le moteur en remplissant le tableau de mouvements possibles. Prenez les six pièces et calculez les mouvements légaux disponibles sur chaque case. Ainsi, chaque pièce avait un tableau [64] [8]. J'ai pris cette idée et l'ai compressée en deux index et une table. Le tableau contient une valeur qui indique si les 16 mouvements sont possibles, un index contient le décalage du mouvement et l'autre contient le masque.

décalage [] = {-8, -1, 1, 8, -9, -7, 7, 9, -17, -15, -10, -6, 6, 10, 15, 17};

mask [] = {1, 2, 4, 8, 16, 32, 64, 128, 256, ...};

Ensuite, la génération d'un mouvement coulissant est aussi simple que de rechercher la validité de son masque dans ses décalages autorisés par rapport à la table de mouvement.

Les algorithmes se sont-ils améliorés?

Évidemment, oui un peu.

ou les améliorations étaient-elles principalement dues aux mêmes algorithmes fonctionnant plus rapidement grâce à un matériel et des logiciels plus rapides?

Nit mineur: Si les algorithmes se sont améliorés, c'est que le logiciel s'améliore donc il n'y a pas de "ou".

La loi de Moore nous dit que la vitesse du processeur doublera tous les 18 mois environ. Cela signifie qu'il a doublé environ 13 fois en 20 ans. Cela rend les processeurs modernes quelque part dans la région 8 000 fois plus rapides. Donc, de loin, la plus grande amélioration des performances du moteur est due à un matériel plus rapide.

Dans le premier cas, ces améliorations algorithmiques sont-elles publiques?

Et si oui, quelles ont été les améliorations? Où puis-je les lire?

Eh bien, ce n'était pas le premier, c'était le dernier. Néanmoins, les améliorations sont principalement open source et librement visibles en téléchargeant les sources pour des moteurs comme Stockfish . Peut-être vaut-il également la peine de donner le lien de téléchargement général de Stockfish, car le lien de code source spécifique expirera probablement lorsque la version 9 sortira.

Tout tourne autour des algorithmes.

Affronter un joueur d'échecs humain a pris l'un des ordinateurs les plus puissants du monde à l'époque. Cette approche de calcul par force brute a permis à Deep Blue de regarder autour de six à huit mouvements à venir. Dans un combat serré, la machine a finalement battu Kasparov par 3 1/2 matchs à 2 1/2.

Six ans plus tard, Kasparov a participé à un autre concours de l'homme contre la machine. Cette fois, il a joué contre le successeur de Deep Blue, Deep Junior. Le résultat a été une série tirée en trois matchs. La plus grande différence était que Deep Junior fonctionnait sur une machine avec environ 1% de la puissance de calcul de Deep Blue. Les algorithmes de jeu d'échecs s'étaient améliorés au point d'atteindre pratiquement le même résultat avec une puissance de calcul cent fois inférieure.

Avertissement: pas un expert.

Les algorithmes se sont améliorés et les meilleurs moteurs actuels fonctionnant en 1995 (rappelez-vous que Deep Blue était en 1999) battront Kasparov. Si je comprends bien, il existe deux aspects des algorithmes:

Cherchez . Si, par exemple, je prends votre reine avec ma reine, un adversaire humain cherchera automatiquement en premier à la recapturer. Cependant, pour un ordinateur, il évaluera toutes les réponses possibles à QxQ. Presque tout le temps, c'est une perte de puissance de traitement. Un bon algorithme de recherche supprime toutes ces "branches" car elles ne sont de toute façon pas pertinentes.

L'algorithme de recherche standard est l' élagage alpha-bêta , et il a été utilisé dans les premiers ordinateurs d'échecs. Je ne sais pas si Deep Blue a utilisé l'élagage alpha-bêta, mais pas les moteurs modernes. En conséquence, leurs recherches sont «dangereuses» - ils peuvent manquer, par exemple, que certains mouvements autres que la reconquête de la reine auraient gagné le match. Cependant, il est rare que cela se produise, et en retour, ils poussent leurs profondeurs très haut. ("Profondeur" est un terme technique désignant la profondeur de recherche du moteur, par exemple, un moteur qui recherche à la profondeur 30 est susceptible de battre celui qui ne recherche qu'à la profondeur 20, toutes choses étant égales par ailleurs).

Évaluation . C'est l'autre volet du code moteur. Étant donné une position particulière, est-il préférable pour le blanc, le noir ou l'équivalent? Cela peut impliquer toutes sortes de fonctions, par exemple

• Si un côté a du matériel / espace supplémentaire, donnez-lui un bonus à évaluer.
• Si le blanc a un chevalier avancé soutenu par un pion, donnez au blanc un bonus à l'évaluation.
• Si le roi des noirs est bloqué, donnez aux blancs un bonus à l'évaluation.
• Si les blancs ont une tour au 7e rang, donnez aux blancs un bonus à l'évaluation.
• Si c'est une fin de partie (et qu'il existe des algorithmes pour décider si la position est une fin de partie) et que les deux côtés ont des évêques de couleurs opposées, imposez une pénalité à eval (c.-à-d. Poussez-la vers 0,00).

Les moteurs d'aujourd'hui évaluent les positions bien mieux que Deep Blue.

Quant à savoir si les algorithmes sont publics, Stockfish est actuellement le moteur le plus puissant du monde et il est open source. Vous pouvez télécharger le code vous-même depuis Github .