Comment les moteurs d'échecs «pensent»?

Ce que je veux savoir, c'est comment les moteurs sont programmés pour trouver des mouvements. Je suis sûr qu'ils calculent d'abord les lignes les plus contraignantes telles que les captures et les vérifications. Mais qu'en est-il des mouvements de position subtils et profonds? Ils semblent aussi les trouver très rapidement (de manière générale. Bien sûr, de tels mouvements leur manquent de temps en temps). Comme dans, comment sont-ils programmés pour rechercher des mouvements calmes / des idées de position? Ils ne peuvent pas simplement forcer brutalement chaque mouvement, car cela prendrait trop de temps, donc il devrait y avoir un moyen intelligent pour arriver aux meilleurs mouvements très rapidement. Je suis intéressé à le savoir parce que je pense que cela aiderait également les joueurs à réfléchir sur le tableau dans le monde réel.

D'une manière générale, les moteurs d'échecs utilisent un arbre de décision. La racine de l'arbre est la position actuelle et a un nœud enfant pour chaque position qui peut être effectuée en effectuant un mouvement légal. Chacun de ces nœuds à son tour a un nœud enfant pour les positions qui peuvent être atteintes en effectuant un mouvement légal à partir d'eux. Le moteur pousse l'arbre à une profondeur définie par ses capacités et le temps qu'il lui est permis de "penser". Les positions qui peuvent être atteintes de plusieurs manières sont simplement référencées de manière à ne pas devoir être prises en compte plus d'une fois. Une fois l'arbre créé, l'ordinateur utilise un ensemble de règles pondérées pour analyser les positions finales dans l'arbre et commence à supprimer celles qui ne sont pas souhaitables ou que l'adversaire peut l'empêcher d'atteindre. L'arbre est coupé de cette façon jusqu'à ce qu'il ne reste qu'un mouvement et que l'ordinateur fasse ce mouvement.

http://www.chess.com/blog/zaifrun propose des séries ou des articles sur la création d'un moteur d'échecs si vous souhaitez un examen plus approfondi de leur fonctionnement.

Vous posez une question assez complexe, mais il est bon de revenir à l'essentiel. Il y a quelques concepts à considérer:

Évaluation

Si un (vrai) joueur est montré une position et a demandé "qui gagne ce jeu?", Comment vont-ils décider? Très probablement, ils vérifieront quelques éléments de base, tels que: les différences matérielles, le degré auquel les pièces ont été développées ou sont bien positionnées, les pions doublés / isolés / connectés / passés, les fichiers ouverts (contrôlés), la distance jusqu'à le conseil d'administration les pions sont.

Maintenant, si vous le deviez, vous pourriez trouver un moyen systématique de calculer un score de position sur la base de ce qui précède. Vous pouvez décider, par exemple, qu'un pion vaut 1 point et qu'un pion passé vaut 0,3 point de plus. Les pions isolés ou doublés peuvent valoir un peu moins, etc. Si vous additionnez tout, vous obtenez une valeur estimée pour la position immédiate à portée de main.

Ceci est connu sous le nom d' évaluation , et, fondamentalement, tous les programmes d'échecs ont un moyen d'évaluer les positions (en ignorant les nouveaux moteurs d'échecs AI qui sont généralement très faibles).

Mais qu'en est-il des mouvements de position subtils et profonds?

Eh bien, nous avons à peine effleuré la surface de l'évaluation de position. La mise en œuvre réelle d'une fonction d'évaluation pourrait être simpliste, pour permettre d'évaluer plus de postes par seconde (quoique de manière approximative), ou plus complexe, conduisant à moins de postes évalués, mais avec un degré de confiance plus élevé. Il n'est pas rare que la fonction d'évaluation prenne en compte des centaines, voire des milliers d'informations distinctes.

Chercher

J'ai spécifiquement omis quelque chose de ce qui précède, auquel la plupart des vrais joueurs penseront immédiatement - existe-t-il un moyen de gagner immédiatement le jeu pour chaque camp? Y a-t-il des copains ou des pièces "suspendues" visibles? Bien qu'il soit facile de banaliser cela, c'est tout sauf trivial.

Qu'est-ce que cela signifie pour un joueur d'avoir pleinement confiance dans une combinaison? En fin de compte, cela revient à avoir calculé toutes les options. Les vrais joueurs ne le feront généralement pas (sauf pour les partenaires triviaux ou très forcés), la plupart du temps nous n'envisagerons qu'une poignée d'options et en exclurons d'autres qui semblent être "non constructives" ou conduisant évidemment à une perte . Nous faisons souvent des erreurs lors de ce calcul, par exemple, nous pouvons réaliser qu'un changement dans les ordres de déplacement fait évaporer les menaces, etc. Le fait est que pour être complètement sûr d'une combinaison, vous devez réellement calculer jusqu'à sa conclusion, en supposant que chaque le joueur ne fera que le meilleur coup possible à sa disposition (c'est ce qu'on appelle "min / max").

Maintenant, étant donné que les échecs ont un espace de recherche beaucoup plus grand (c'est à cela que se réfèrent "tous les mouvements possibles dans le futur") que ce qui est possible pour un ordinateur à calculer, des compromis doivent être faits. Tout comme les humains, les ordinateurs peuvent décider d'ignorer des lignes de pensée entières en fonction de certains critères. C'est ce qu'on appelle l' heuristique . Il convient de noter que si vous ne pouvez être vraiment sûr d'une combinaison que si vous la forcez brutalement, une fonction d'évaluation complexe peut souvent détecter la présence de menaces (par exemple, nous pourrions compter les fourchettes, les opportunités de brochettes, etc.) pour guider une recherche dans cette direction. ).

Au final, bien que les ordinateurs soient extrêmement rapides, ce sont les heuristiques qui leur permettent de calculer si profondément. Cela dit, vous serez peut-être surpris de la façon dont les moteurs modernes profonds calculent entièrement, généralement au-delà de 3 mouvements, même dans les jeux rapides.

Conclusion / tout combiner

Donc, pour résumer - les fonctions d'évaluation ont beaucoup d'intelligence (c'est-à-dire qu'elles prennent en compte plus de choses que votre joueur humain moyen), l'heuristique permet à l'ordinateur d'abattre des pistes de pensée qu'il décide probablement ne va pas bien se terminer, et les ordinateurs sont extrêmement, extrêmement rapides. Additionnez-les et ils sont assez difficiles à battre.

Je suis d'accord avec les réponses.

Je me souviens que GM Roman Dzindzichashvili en parlait, dans l'une des vidéos des laboratoires de Roman , je ne me souviens pas de quelle vidéo il s'agissait (si quelqu'un connaît les détails, veuillez modifier ma réponse).

Roman a dit que le développeur du moteur Fritz était son ami. Donc, Roman a testé Fritz pour voir à quel point c'était bon, et le développeur a dit à Roman que pour que Fritz prenne des décisions complexes (sacrifier des matériaux en échange d'un avantage positionnel par exemple), il devait changer la valeur des pièces, comme dire au programme qu'un mauvais évêque vaut 1 point, un évêque sur une diagonale ouverte vaut 7 points, les chevaliers valent 5 points en position rapprochée ...

Je ne connais pas les nombres exacts pour chaque pièce mais c'est comme ça que ça marche, et maintenant votre moteur n'aura aucun problème à sacrifier un mauvais évêque ou quoi que ce soit si vous pouvez lui dire la valeur de chaque pièce dans chaque position.

MODIFIER

Voir aussi le wiki de programmation des échecs .

Il est tout simplement impossible pour les ordinateurs de regarder suffisamment en profondeur (25 plis et plus) et de vérifier chaque mouvement possible.

Ce qui rend possible, c'est la technique appelée élagage alpha-bêta qui signifie que les ordinateurs, similaires aux humains (mais bien mieux) ne suivent que les suites prometteuses.

Ils évaluent constamment les positions (sur la base de certaines règles précodées, évaluant le matériel, la sécurité des rois, l'activité, les structures de pions, etc.) et examinent les variations qui semblent les conduire vers la meilleure position.

Il est encore proche de la magie de savoir comment ils parviennent à le faire assez efficacement pour évaluer des millions de ces postes en une seconde.

Donc, pour résumer, vous avez raison, ils ne peuvent pas regarder tous les mouvements s'ils jouent aux échecs stratégiques, mais ils peuvent très rapidement regarder les mouvements décents. Le problème est toujours avec les plans et l'horizon à très long terme sur lesquels ils peuvent voir, mais cela est en cours d'élaboration (Rybka analyse beaucoup plus lentement, mais joue beaucoup plus aux échecs positionnels, tandis que Houdini est romantique dans son `` cœur mécanique '' calculant plus de mouvements et jouer plus agressivement). Même les ordinateurs ont leurs propres styles!

L'élagage alpha-bêta signifie simplement que si vous trouvez une ligne qui tourne mal pour vous, vous arrêtez de regarder ce mouvement candidat et essayez plutôt d'autres. Il s'agit d'un type d'élagage arrière, ce qui signifie que vous ne manquerez jamais un bon coup. L'élagage avant, en revanche, repose davantage sur des suppositions. L'élagage de futilité, les réductions de mouvements tardifs et le rasage sont des types d'élagage vers l'avant, et tous dépendent du sentiment du programmeur quant au type de mouvements à prendre en compte. Un programme qui fait beaucoup d'élagage vers l'avant peut passer à côté de sacrifices surprenants qui conduisent à s'accoupler, mais d'un autre côté, il élimine beaucoup de mouvements vraiment mauvais, et peut donc aller plus loin dans l'examen des mouvements qu'il favorise.

La plupart des moteurs recherchent les premiers mouvements en profondeur en examinant toutes les possibilités. Si aucun mouvement échoue haut (c'est-à-dire semble clairement pire qu'un mouvement que vous avez déjà envisagé), vous étendez un peu plus la recherche. En général, vous continuez à explorer chaque ligne jusqu'à ce que vous atteigniez une position de repos (sans contrôles, captures, menaces d'accouplement, etc.), puis effectuez votre évaluation. Les mouvements silencieux peuvent ne pas être pris en compte lorsqu'ils sont au plus profond de l'arbre de recherche, mais une fois que vous atteignez cette position réelle dans le jeu, le moteur regarde tous les mouvements, silencieux et précis. Vous pouvez parfois voir cela dans la sortie du moteur, lorsqu'un moteur favorise soudainement un mouvement qu'il n'avait pas envisagé de reculer quelques fois.

Les moteurs calculent si rapidement qu'il n'est pas si important pour eux de considérer quel mouvement regarder en premier, mais pour les humains, c'est une question clé. Jonathan Tisdall essaie de répondre à cela dans son livre, Améliorez vos échecs maintenant. Lorsque vous êtes sur l'attaque, il vous suggère de regarder d'abord les mouvements les plus violents. Lorsque vous défendez, vous regardez d'abord les lignes les plus difficiles. Il cite également des règles de base positionnelles (par exemple, la centralisation, la coordination) pour décider quels mouvements regarder en premier.

D'autres livres qui peuvent être pertinents sont Invisible Chess Moves d'Emmanuel Neimann et Forcing Chess Moves de Charles Hertan, qui plaident tous deux pour l'importance d'envisager des mouvements improbables ou surprenants dans des positions nettes. Hertan parle même de développer des «yeux d'ordinateur» pour de telles tactiques.