Hikaru Nakamura, qui a récemment contesté un ordinateur.

Un ordinateur a longtemps battu un homme aux échecs, maintenant les joueurs d'échecs les plus forts ne peuvent même plus battre un vieux portable. Désormais, les moteurs d'échecs sont utilisés pour analyser les jeux, rechercher de nouvelles options et jouer par correspondance.

Si vous êtes intéressé par la disposition des moteurs d'échecs, bienvenue à cat.

Présentation

- , ( , ), . -, - .

, , . . , , , 3 ( — , — ) 120 . , 14 , .

, , gagner le match contre le champion du monde est toujours à la portée des meilleurs. Ce n'est pas vrai non plus.

Lors d'un récent mini-match homme-machine, Hikaru Nakamura , l'un des joueurs d'échecs les plus forts du monde, a joué avec Komodo , l'un des (deux) programmes d'échecs les plus puissants du monde. Le programme a été lancé sur un Xeon à 24 cœurs. Comme les gens ne peuvent plus rivaliser sur un pied d'égalité avec un ordinateur, le grand maître a pris une longueur d'avance dans chacun des 4 jeux:

• Dans le premier jeu - un pion et un coup: l'ordinateur a joué en noir et sans pion f7
• Dans le second - seulement un pion: l'ordinateur jouait blanc sans pion f2
• Dans la troisième - qualité (la différence entre une tour et une pièce légère est estimée à environ 2 pions): un ordinateur blanc sans tour a1, un homme sans chevalier b8 et une tour a8 à sa place.
• Dans le quatrième - quatre coups: une personne joue en blanc et au lieu du premier coup, elle fait 4 coups sans traverser le milieu du plateau.

Il y a eu certains différends concernant le handicap - par exemple, l'absence du pion f affaiblit quelque peu le roi, mais après le roque donne une ligne ouverte à la tour. L'absence d'un pion central donne probablement un plus grand avantage. 4 coups donnent un bon avantage positionnel, mais si vous jouez un début fermé comme la défense Old Indian, cet avantage n'est pas si difficile à annuler.

De plus, les matchs ont été joués avec un contrôle de 45 '+15', soit 45 minutes par match et 15 secondes d' ajoutchaque mouvement. Habituellement, des commandes plus courtes donnent un avantage supplémentaire à l'ordinateur, tandis que des commandes plus longues augmentent légèrement les chances d'une personne. Même en une fraction de seconde, l'ordinateur parvient à balayer ouvertement les mouvements perdants, tandis qu'en raison de la croissance exponentielle de l'arbre des variantes, chaque amélioration ultérieure de l'analyse prend plus de temps.

Néanmoins, il y avait un handicap et la personne a perdu dans le match 2,5-1,5, ayant tiré les 3 premiers matchs et perdu le quatrième. Dans le même temps, le faible grand maître a gagné en toute confianceHandicap à 2 pions. Par conséquent, l'avantage des meilleurs programmes sur les meilleures personnes en ce moment se situe entre 1 et 2 pions du handicap. Bien sûr, cette évaluation est très approximative, mais pour une évaluation précise, il est nécessaire de jouer plusieurs milliers de jeux entre les personnes et les programmes, et il est peu probable que quelqu'un le fasse. Veuillez noter que la cote ELO, souvent indiquée pour les programmes, n'a rien à voir avec la cote des personnes.

Qu'est-ce qu'un moteur d'échecs?

Pour qu'une personne puisse jouer aux échecs avec un ordinateur, en plus de rechercher le meilleur coup, vous avez besoin d'une interface graphique. Heureusement, une interface universelle a été inventée (même deux, Winboard et UCI , mais la plupart des moteurs utilisent UCI) pour la communication entre l'interface graphique et le programme d'échecs lui-même (moteur). Ainsi, les programmeurs peuvent se concentrer sur l'algorithme du jeu d'échecs, sans penser à l'interface. Le revers de la médaille est que la création d'une interface graphique est beaucoup plus ennuyeuse que l'écriture d'un moteur, alors les interfaces graphiques gratuites perdent sensiblement sur celles payantes. Contrairement aux moteurs, où Stockfish gratuit se bat en toute confiance pour la première ligne du classement avec Komodo payant.

Comment jouent-ils encore?

Alors, comment fonctionne un moteur d'échecs moderne?

Présentation du conseil

La base de tout moteur est la représentation d'un échiquier. Tout d'abord, il faut «expliquer» à l'ordinateur toutes les règles des échecs et lui donner la possibilité de garder la position des échecs. Sans cela, il est impossible d'évaluer la position et de faire des mouvements.

Il existe deux façons principales de stocker une représentation d'une planche - par formes ou par cellules . Dans le premier cas, nous stockons pour chaque pièce sa place sur la planche, dans le second - au contraire, pour chaque cellule nous stockons ce qui s'y trouve. Chaque méthode a ses avantages et ses inconvénients, mais pour le moment, tous les meilleurs moteurs utilisent la même représentation de la carte - les bitboards.

Bitboards

Heureusement, il y a 64 cellules sur l'échiquier. Donc, si nous utilisons un bit pour chaque cellule, nous pouvons stocker la carte entière dans un entier 64 bits.
Dans une variable, nous stockerons toutes les pièces blanches, dans une autre - toutes noires et dans 6 autres - chaque type de chiffres séparément (une autre option est de 12 bitboards pour chaque couleur et type de chiffres séparément).

Quel est l'avantage de cette option?
Le premier est la mémoire. Comme nous l'apprendrons plus tard, au cours de l'analyse, la représentation de la carte est copiée plusieurs fois et, en conséquence, la RAM ronge. Les bitboards sont l'une des représentations d'échiquier les plus compactes.
Deuxièmement, la vitesse. De nombreux calculs, par exemple, le calcul de mouvements possibles, se résument à plusieurs opérations de bits. Pour cette raison, par exemple, l'utilisation de l'instruction POPCNT donne une accélération de ~ 15% aux moteurs modernes. De plus, pendant l'existence des bitboards, de nombreux algorithmes et optimisations ont été inventés, comme par exemple les bitboards «magiques» .

Chercher

Minimax

Au cœur de la plupart des moteurs d'échecs se trouve l'algorithme de recherche minimax ou sa modification de non-hamax. En bref, nous descendons l'arbre, évaluons les feuilles, puis montons, chaque fois en choisissant le mouvement optimal pour le joueur actuel, en minimisant le score pour un (noir) et en maximisant pour le second (blanc). D'où le nom. Une fois à la racine, nous obtenons une séquence de mouvements optimale pour les deux joueurs. La différence entre minimax et non-hamax est que dans le premier cas, nous choisissons à tour de rôle les mouvements avec les cotes maximales et minimales, et dans le second, à la place, changeons le signe pour toutes les cotes et choisissons toujours le maximum (nous avons compris d'où ils venaient). Plus de détails ici et ici .

Alpha beta

La première optimisation est alpha beta . L'idée de l'alpha-bêta est simple - si j'ai déjà un bon coup, alors vous pouvez couper les coups, qui sont évidemment pires. Prenons l'exemple de l'image effrayante de gauche. Supposons que le joueur A ait 2 coups possibles - a3 et b3. Après avoir analysé le cours de a3, le programme a reçu un score de +1,75. Commençant à évaluer le coup b3, le programme a vu que le joueur B avait deux coups - a6 et a5. Évaluation du cours a6 +0.5. Puisque le joueur B choisit un coup avec un score minimum, il ne choisira pas un coup avec un score supérieur à 0,5, ce qui signifie que l'estimation du coup b3 est inférieure à 0,5, et il n'y a aucun intérêt à le considérer. Ainsi, le sous-arbre restant de b3 est coupé.

Pour l'écrêtage, nous stockons les limites supérieure et inférieure - alpha et bêta. Si au cours de l'analyse, un coup obtient un score supérieur à la version bêta, le nœud actuel est coupé. Si le score est supérieur à alpha, alors alpha est mis à jour.

Les nœuds en alpha bêta sont divisés en 3 catégories:

1. PV-Nodes - nœuds dont l'évaluation est tombée dans la fenêtre (entre alpha et bêta). La racine et le nœud le plus à gauche sont toujours des nœuds de ce type.
2. Cut-Nodes (ou fail-high node ) - nœuds dans lesquels une coupure bêta s'est produite.
3. Tous les nœuds (ou nœuds à faible échec ) - nœuds dans lesquels aucun mouvement n'a dépassé l'alpha selon l'évaluation.

Tri des mouvements

Lorsque vous utilisez l'alpha bêta, l'ordre des mouvements devient important. Si nous pouvons mettre le meilleur coup en premier, alors les coups restants seront analysés beaucoup plus rapidement en raison des coupures bêta.

En plus d'utiliser le hachage et le meilleur mouvement de l'itération précédente, il existe plusieurs techniques pour trier les mouvements.

Pour les captures, par exemple, une simple heuristique MVV-LVA (Most Valuable Victim - Least Valuable Aggressor) peut être utilisée . Nous trions toutes les captures par ordre décroissant de la valeur de la «victime», et à l'intérieur nous trions à nouveau par ordre croissant de la valeur de «l'agresseur». De toute évidence, il est généralement plus rentable de ramasser la reine par pion que vice versa.

Pour les mouvements «silencieux», la méthode des mouvements «tueurs» est utilisée - mouvements qui ont provoqué la coupure bêta. Ces mouvements sont généralement vérifiés immédiatement après les mouvements du hachage et des captures.

Tables de hachage ou tables de permutation

Malgré la taille énorme de l'arbre, de nombreux nœuds sont identiques. Afin de ne pas analyser deux fois la même position, l'ordinateur stocke les résultats de l'analyse dans un tableau et vérifie à chaque fois s'il existe déjà une analyse prête de cette position. En règle générale, une telle table stocke le hachage réel de la position, de la note, du meilleur mouvement et de l'âge de la note. L'âge est requis pour remplacer les anciennes positions lors du remplissage du tableau.

Recherche itérative

Comme vous le savez, si nous ne pouvons pas analyser complètement l'arbre entier, minimax a besoin d'une fonction d'évaluation. Après avoir atteint une certaine profondeur, nous arrêtons la recherche, évaluons la position et commençons à grimper à l'arbre. Mais une telle méthode nécessite une profondeur prédéterminée et ne fournit pas de résultats intermédiaires de haute qualité.

La recherche itérative résout ces problèmes. D'abord, nous analysons à une profondeur de 1, puis à une profondeur de 2, etc. Ainsi, à chaque fois on descend un peu plus profondément que la dernière fois, jusqu'à l'arrêt de l'analyse. Pour réduire la taille de l'arborescence de recherche, les résultats de la dernière itération sont généralement utilisés pour couper délibérément les mauvais mouvements sur l'actuel. Cette méthode est appelée «fenêtre d'aspiration» et est utilisée universellement.

Recherche de repos

Cette méthode est conçue pour lutter contre «l'effet d'horizon». Arrêter la recherche à la bonne profondeur peut être très dangereux. Imaginez que nous nous arrêtions au milieu d'échanger des reines - le blanc a pris la reine noire, et le prochain mouvement le noir devrait choisir le blanc. Mais pour le moment sur le tableau - Blanc a une reine supplémentaire et une évaluation statique sera fondamentalement erronée.

Pour ce faire, avant de faire une évaluation statique, nous vérifions toutes les captures (parfois même les dames) et descendons l'arborescence jusqu'à une position dans laquelle il n'y a pas de captures et de vérificateurs possibles. Naturellement, si toutes les captures aggravent l'estimation, alors nous renvoyons l'estimation de la position actuelle.

Recherche sélective

L'idée d'une recherche sélective est de prendre plus de temps pour considérer des mouvements «intéressants» et moins pour considérer comme inintéressants. Pour cela, des extensions sont utilisées qui augmentent la profondeur de la recherche dans certaines positions, et des abréviations qui réduisent la profondeur de la recherche.

La profondeur est augmentée dans le cas de captures, de dames, si le mouvement est unique ou bien meilleur que les alternatives ou en présence d'un pion qui passe.

Couper et couper

Avec les coupes et les coupes, tout est beaucoup plus intéressant. Ils peuvent réduire considérablement la taille de l'arbre.

En bref sur l'écrêtage:

• - — , . , , . , , , , .
• — , -. , , . (1-2).
• — , , . . PV . .
• Multi-Cut — M(, 6) C(, 3) Cut-node, .
• null- — null- ( ) , . , , , , .

Les abréviations sont utilisées lorsque nous ne sommes pas sûrs que le mouvement est mauvais, et donc ne le coupez pas, mais réduisez simplement la profondeur. Par exemple, le rasage est une abréviation à condition que l'estimation statique de la position actuelle soit inférieure à alpha.

En raison du tri de haute qualité des mouvements et des coupures, les moteurs modernes parviennent à atteindre un coefficient de ramification inférieur à 2 . Pour cette raison, malheureusement, ils ne remarquent parfois pas de victimes et de combinaisons non standard.

NegaScout et PVS

, , PV-node ( ), , , . , +1, . , - , , .

— , , .

- — . , — Parallel Alpha-Beta Search on Shared Memory Multiprocessors. , Cut-nodes , ( ), , .

Lazy SMP

Un algorithme très simple. Nous commençons simplement tous les threads en même temps avec la même recherche. La communication passe par une table de hachage. Lazy SMP s'est avéré être d'une efficacité inattendue, à tel point que le Stockfish haut de gamme y est passé avec YBW. Certes, certains pensent que l'amélioration est due à une mauvaise mise en œuvre de YBWC et à un écrêtage trop agressif, et non à l'avantage de Lazy SMP.

Concept d'attente des jeunes frères (YBWC)

Le premier nœud (frère aîné) doit être entièrement analysé, après quoi une analyse parallèle des nœuds restants (frères plus jeunes) est lancée. L'idée est la même, le premier mouvement améliorera considérablement l'alpha, ou même vous permettra de couper tous les autres nœuds.

Fractionnement dynamique des arbres (DTS)

Algorithme rapide et complexe. Un peu de vitesse: la vitesse de recherche est mesurée par ttd (time to depth), c'est-à-dire le temps pendant lequel la recherche atteint une certaine profondeur. Cet indicateur peut généralement être utilisé pour comparer le travail de différentes versions d'un moteur ou d'un moteur fonctionnant sur un nombre différent de cœurs (bien que Komodo, par exemple, augmente la largeur de l'arbre avec plus de cœurs disponibles). De plus, pendant le fonctionnement, le moteur affiche la vitesse de recherche en nps (nœuds par seconde). Cette métrique est beaucoup plus populaire, mais elle ne permet même pas au moteur de se comparer à lui-même. Le SMP paresseux, dans lequel il n'y a pas de synchronisation, augmente presque nps de façon linéaire, mais en raison de la grande quantité de travail inutile, son ttd n'est pas si impressionnant. Alors que pour DTS, nps et ttd changent presque de la même manière .

Pour être honnête, je ne pouvais toujours pas comprendre pleinement cet algorithme qui, malgré sa haute efficacité, est utilisé littéralement dans une paire de moteurs. Pour qui c'est très intéressant, suivez le lien ci-dessus.

Évaluation

Nous avons donc atteint la profondeur nécessaire, recherché le calme et, enfin, nous devons évaluer la position statique.

L'ordinateur évalue la position en pions: +1,0 signifie que les blancs ont un avantage égal à 1 pion, -0,5 signifie que les noirs ont un avantage d'un demi-pion. Le mat est estimé à 300 pions et la position dans laquelle le nombre de mouvements vers le tapis x est connu est à (300-0,01x) pions. +299,85 signifie que les Blancs s'accouplent en 15 coups. Dans ce cas, le programme lui-même fonctionne généralement avec des estimations entières en centipes (1/100 pions).

Quels paramètres l'ordinateur prend-il en compte lors de l'évaluation d'une position?

Matériel et mobilité

La chose la plus simple. La reine a 9-12 pions, la tour 5-6, le chevalier et l'évêque 2.5-4 et le pion, respectivement, un pion. En général, un matériau est une bonne heuristique pour évaluer une position et tout avantage positionnel se transforme généralement à la fin en un matériau.

La mobilité est considérée comme simple - le nombre de mouvements possibles dans la position actuelle. Plus ils sont nombreux, plus l'armée du joueur est mobile.

Tableaux de position des formes

Le chevalier dans le coin du plateau est généralement mauvais, les pions plus proches de l'arrière ennemi gagnent en valeur et ainsi de suite. Pour chaque figure, un tableau des bonus et pénalités est établi en fonction de sa position au tableau.

Structure de pion

• Pions doubles - deux pions sur la même verticale. Souvent, il est difficile de les défendre avec d'autres pions, considérés comme une faiblesse.
• — , . , .
• — , . ,
• — , . , .

- , . , , .

. — , — .

- — , , , ..

?

Conflit traditionnel: qui est plus efficace, évalue avec précision la position ou atteint une plus grande profondeur de recherche. L'expérience a montré que les fonctions d'évaluation trop "lourdes" sont inefficaces. D'un autre côté, une évaluation plus détaillée, prenant en compte plus de facteurs, conduit généralement à un jeu plus «beau» et «agressif».

Livres de début et tableaux de fin de partie

Livres de début

A l'aube des échecs informatiques, les programmes ont très faiblement fait leurs débuts. Les débuts nécessitent souvent des décisions stratégiques qui affecteront l'ensemble du jeu. D'un autre côté, la théorie de l'ouverture était bien développée chez les gens, l'ouverture a été analysée à plusieurs reprises et jouée de mémoire. Une "mémoire" similaire a donc été créée pour les ordinateurs. À partir de la position initiale, un arbre de mouvements a été construit et chaque mouvement a été évalué. Pendant le jeu, le moteur a simplement choisi l'un des «bons» coups avec une certaine probabilité.

Depuis lors, les premiers livres ont augmenté, de nombreux débuts sont analysés à l'aide d'ordinateurs jusqu'à la fin du jeu. Il n'y a pas besoin d'eux, des moteurs puissants ont appris à jouer les débuts, mais ils quittent les lignes principales assez rapidement.

Tables de fin de partie

Retour à l'introduction. N'oubliez pas l'idée de stocker de nombreuses positions en mémoire et de choisir la bonne. Elle est là. Pour un petit nombre (jusqu'à 7) de chiffres, toutes les positions existantes sont calculées. Autrement dit, dans ces positions, l'ordinateur commence à jouer parfaitement, gagnant dans le nombre minimum de coups. Moins est la taille et le temps de génération. La création de ces tables a aidé à l'étude des finales.

Génération de table

Nous générons toutes les positions possibles (en tenant compte de la symétrie) avec un certain ensemble de formes. Parmi eux, nous trouvons et désignons toutes les positions où se trouve le tapis. À la prochaine passe, nous désignons toutes les positions dans lesquelles vous pouvez entrer dans des positions avec un tapis - dans ces positions, un tapis est mis en 1 tour. On retrouve ainsi toutes les positions avec un mate 2,3,4, 549 coups. Dans toutes les positions non marquées - un match nul.

Tables Nalimov

Les premiers tableaux de fin de jeu ont été publiés en 1998. Pour chaque position, le résultat du jeu et le nombre de mouvements vers le tapis avec un jeu idéal sont stockés. La taille de toutes les terminaisons à six chiffres est de 1,2 téraoctets.

Tables Lomonosov

En 2012, toutes les terminaisons à sept chiffres (sauf 6 contre 1) ont été comptées sur le supercalculateur Lomonosov de l'Université d'État de Moscou . Ces bases sont disponibles uniquement pour de l'argent et ce sont les seules tables de fin de jeu complètes à sept chiffres existantes.

Syzygy

La norme de facto. Ces bases sont beaucoup plus compactes que les bases Nalimov. Ils se composent de deux parties - WDL (Win Draw Lose) et DTZ (Distance to zeroing). Les bases de données WDL sont destinées à être utilisées pendant la recherche. Une fois que le nœud d'arbre est trouvé dans le tableau, nous avons le résultat exact du jeu dans cette position. Les DTZ sont destinés à être utilisés dans la racine - ils stockent le nombre de mouvements vers un compteur d' annulation des mouvements (déplacement par pion ou capture). Ainsi, les bases WDL sont suffisantes pour l'analyse, et les bases DTZ peuvent être utiles pour analyser les jeux de fin. Syzygy est beaucoup plus petit - 68 gigaoctets pour WDL à six chiffres et 83 pour DTZ. Il n'y a pas de bases à sept chiffres, car leur génération nécessite environ téraoctets de RAM.

Utiliser

Les tables de fin de partie sont utilisées principalement pour l'analyse, l'augmentation de la force des moteurs de jeu est faible - ELO de 20 à 30 points . Néanmoins, étant donné que la profondeur de recherche des moteurs modernes peut être très importante, les requêtes vers les bases de fin de jeu à partir de l'arborescence de recherche se produisent toujours au début.

Autre intéressant

La girafe ou les réseaux de neurones jouent aux échecs

Certains d'entre vous ont peut-être entendu parler d'un moteur d'échecs sur les réseaux de neurones qui a atteint le niveau de messagerie instantanée (ce qui, comme nous l'avons compris dans l'introduction, n'est pas si cool pour le moteur). Il a été écrit et publié sur Bitbucket par Matthew Lai, qui a malheureusement cessé de travailler dessus parce qu'il a commencé à travailler sur Google DeepMind .

Paramètres de réglage

Ajouter une nouvelle fonctionnalité au moteur n'est pas difficile, mais comment puis-je vérifier qu'elle a donné une amplification? L'option la plus simple est de jouer à plusieurs jeux entre l'ancienne et la nouvelle version et de voir qui gagne. Mais si l'amélioration est faible, et cela se produit généralement après l'ajout de toutes les fonctionnalités principales, il devrait y avoir plusieurs milliers de jeux, sinon il n'y aura pas de fiabilité.

Stockfish

Il y a beaucoup de gens qui travaillent sur ce moteur, et chacune de leurs idées doit être vérifiée. Avec la puissance actuelle du moteur, chaque amélioration donne une augmentation de quelques points de notation, mais au final, une augmentation régulière de plusieurs dizaines de points est obtenue chaque année.

Leur solution est typique de l'open source - les bénévoles fournissent leur pouvoir pour piloter des centaines de milliers de jeux sur eux.

CLOP

, , . — : ( ) , .

Texel's tuning

. ( 9 64000 , 8 200000), ( 1, 0.5, 0). , . , .

Stockfish tuning

. x, ( ) x-sigma x+sigma. , , — , .

TCEC. , . 100 2 x Intel Xeon E5-2690v3 256 RAM 180'+30". , 11 .

Donc, brièvement dans ce long article, j'ai parlé de la structure des moteurs d'échecs. Beaucoup de détails n'ont pas été dévoilés, je ne savais tout simplement pas quelque chose ou j'ai oublié de dire. Si vous avez des questions, écrivez-les dans les commentaires. De plus, je vous conseillerai deux ressources que vous avez probablement remarquées si vous avez soigneusement ouvert tous les liens disséminés dans l'article:

• Wiki de programmation d'échecs
• Forum Talkchess
• Et un autre, non mentionné plus tôt - coin programmeur