Quelle est une manière précise d'évaluer les positions d'échecs?

Je m'intéresse depuis un certain temps à un algorithme d'IA d'échecs informatiques (et j'ai eu la chance de travailler sur un à un moment donné) comme Minimax , et comme le composant central de ces algorithmes est la soi-disant fonction d'évaluation pour déterminer ce qu'est un bonne configuration de la carte, et ce qui est mauvais .

En d'autres termes, compte tenu de la configuration de votre échiquier, comment déterminez-vous qu'il est à votre avantage et avec quel degré de confiance?

Par exemple:

• Si vous êtes propriétaire du centre, c'est plutôt favorable.
• Si vous avez plus de pièces que votre adversaire, c'est plutôt favorable.
• Si vous avez perdu votre reine, ce n'est pas favorable.
• Si vous avez un pion qui est sur le point d'être promu, cela est favorable.
• ...

Je voudrais donc demander quelques conseils sur la façon de créer une bonne fonction d'évaluation, sur la base de certaines connaissances d'experts sur le jeu d'échecs en général. Et si possible, un degré de favorabilité (disons entre 1 étant très peu favorable, jusqu'à 100 étant extrêmement favorable).

L'idée au final est de pouvoir créer un algorithme qui va chercher dans l'arborescence des possibilités jusqu'à une certaine profondeur et évaluer quelle est la configuration la plus favorable pour le prochain coup (en tenant compte de plusieurs coups dans le futur) en fonction de quoi est favorable au joueur et non favorable à l'adversaire. Mais sans une bonne fonction d'évaluation, l'algorithme n'est rien.

Voici un bon point de départ. La comparaison des matériaux est essentielle (et facile), alors vous pouvez régler cela pour prendre en compte les aspects positionnels tels que les rangs / fichiers / diagonales ouverts, la structure des pions, etc.

https://www.chessprogramming.org/Evaluation

Pour compléter la réponse de @Eve Freeman, je suggère de rechercher comment le meilleur moteur informatique au monde, Stockfish, évalue une position donnée. Comme le code source est ouvert, vous pouvez le faire gratuitement. Je pense que le fichier avec la fonction d'évaluation que vous recherchez est celui-ci .

J'ai le sentiment que je suis un peu en retard sur cette réponse, mais - je suis également en train de fabriquer un moteur. Le code source est en Python (qui est assez facile à lire, même si vous ne le connaissez pas) et est disponible ici si vous souhaitez le lire. La liste des «heuristiques» actuellement actives (au moment de la publication):

• Les pièces plus développées (plus près du côté opposé) sont meilleures
• Les pions plus proches de la promotion sont bons
• Les rois sont notés séparément en fonction de la phase du jeu (ouverture, milieu de partie, fin de partie)
• Si le joueur a deux évêques, cela reçoit un bonus
• Si le joueur a roque, recevez un bonus
• Les pions isolés (pions sans rien autour d'eux) ne sont pas bons
• Les pions doublés (deux pions sur le même fichier sans espace) ne sont pas bons
• Avoir les 8 pions n'est pas nécessairement une bonne chose et est pénalisé (ils encombrent la planche et gênent)
• Jetez un oeil à cette grande fonction d'évaluation qui est également utilisée
• Les évêques avec plus de pions sur le même carré de couleur que l'évêque sont pénalisés (ils ne sont pas aussi bons dans les situations de surpeuplement)
• Pas encore implémenté, mais prévu: les chevaliers obtiennent un bonus dans des situations plus encombrées

Dans l'un de ces points, j'ai mentionné la «phase» du jeu (par exemple, ouverture, middlegame, endgame), et si vous souhaitez inclure cela dans votre moteur, vous rencontrerez probablement le même problème que moi: il n'y a pas ligne claire les séparant. Ma fonction qui décide de la phase du jeu utilise quelques éléments:

• Quantité de matériel sur le plateau (dès qu'une pièce est tuée, elle marque le jeu comme n'étant pas dans l'ouverture)
• Nombre de coups (moins de 6 coups complets est l'ouverture, quoi qu'il arrive)
• mouvement des reines (si les deux reines ont été déplacées, marquez le jeu comme milieu de partie)

Cette réponse a peut-être été longue, tardive et hors sujet, mais j'espère qu'elle a quand même été utile.

Étonnamment, il s'avère qu'un moteur Minimax jouera raisonnablement bien lorsque la fonction d'évaluation est aléatoire ; ceci est connu sous le nom d'effet Beale et résulte du principe que les positions qui vous donnent plus d'options et votre adversaire moins d'options sont généralement favorables. Une façon raisonnable de générer des évaluations aléatoires de manière cohérente et efficace consiste à générer un hachage Zobrist pour la position (en utilisant des coefficients choisis au hasard au début du jeu) et à dériver l'évaluation aléatoire directement à partir du hachage.

À l'autre extrémité de l'échelle, AlphaZero et Leela effectuent une évaluation extrêmement sophistiquée de chaque position recherchée, en utilisant un grand réseau de neurones . Il n'est pas pratique de décrire en termes humains quelles fonctions ce réseau met effectivement en œuvre, mais il est indéniablement plus efficace que la fonction d'évaluation de Stockfish. Le document de recherche AlphaZero indique que cette approche fonctionne mieux avec Monte-Carlo Tree Search plutôt qu'avec Minimax.

Si, d'autre part, vous souhaitez développer un moteur d'analyse pour aider les acteurs humains ou les commentateurs à comprendre les nuances d'une position, il peut être utile de mettre en œuvre une fonction d'évaluation conventionnelle en utilisant des valeurs matérielles établies et la théorie de la position . Un bon exemple est donné par Inside Rebel d'Ed Schröder , qui documente les principales caractéristiques de conception d'un moteur réputé utilisé dans plusieurs ordinateurs d'échecs de Mephisto. Vous souhaiterez peut-être utiliser un certain degré d'apprentissage automatique pour déterminer l'importance relative de chaque élément de votre fonction d'évaluation, et également décomposer ces éléments individuellement pour une présentation dans une interface graphique.

Je pense que les programmeurs d'échecs ont tendance à ne pas s'appuyer sur les connaissances des joueurs d'échecs forts lors de la conception de leurs fonctions d'évaluation, mais à la place à essayer différents éléments, puis à les tester dans des jeux contre d'autres moteurs, et à décider quoi garder. Larry Kaufman parle assez longuement de son point de vue sur la compréhension d'un être humain, mais il semble que Rajlich et Dailey étaient très orientés vers les résultats et n'ont pas adopté les idées de Kaufman en gros.

Un article que j'ai trouvé intéressant était Zach Wegner comparant les fonctions d'évaluation de Rybka et Fruit. L'un des domaines où Rybka a pu représenter un pas en avant a été l'incorporation de tableaux de déséquilibre des matériaux basés sur des combinaisons spécifiques de pièces. Kaufman a également écrit un article à ce sujet.

http://www.top-5000.nl/ZW_Rybka_Fruit.pdf http://danheisman.home.comcast.net/~danheisman/Articles/evaluation_of_material_imbalance.htm

Ce lien est le meilleur point de départ à mon humble avis. J'utilise ceci comme point de départ pour mon propre programme d'échecs et le trouve simple à comprendre et utile aussi.

https://chessprogramming.wikispaces.com/Simplified+evaluation+function

En résumé, l'approche standard pour régler les paramètres d'un moteur d'échecs consiste à:

1. Définissez les paramètres
2. Donner aux paramètres des valeurs nominales (de départ)
3. Exécutez le moteur pour voir comment il fonctionne
4. Ajustez les valeurs des paramètres pour essayer d'améliorer ses performances

Répétez ensuite les étapes 3 et 4 jusqu'à ce que vous ayez atteint votre objectif de performance.

L'approche habituelle consiste à mettre en place un laboratoire où les moteurs s'affrontent dans les tournois de moteurs. Plusieurs jeux sont utilisés dans lesquels le moteur joue les deux couleurs. Les principaux tournois d'intérêt impliquent de faire fonctionner un moteur avec le jeu de valeurs de paramètre A contre le même moteur avec le jeu de valeurs de paramètre B.

Comme vous pouvez probablement le deviner, les résultats de cette approche dépendent fortement de:

• Les paramètres choisis
• Comment les paramètres sont spécifiés
• Comment les valeurs des paramètres varient au cours du test
• Fonctionnement des moteurs (profondeur de pliage limitée, durée limitée, sensibilité, etc.)

Cette approche prend également beaucoup de temps.

Une approche plus récente (et innovante) a été développée en 2010 par des chercheurs utilisant des techniques d'algorithme génétique pour a) spécifier les paramètres et b) régler les valeurs des paramètres. Les enquêteurs ont d'abord exécuté un moteur avec un ensemble nominal de paramètres de départ contre un ensemble de jeux de grand maître pour voir s'il pouvait effectivement choisir le "meilleur coup". Le «meilleur coup» a été défini comme le coup que le grand maître a fait *. Partout où il a échoué, cela a été enregistré. Ensuite, un autre ensemble de valeurs de paramètres a été essayé et les performances relatives par rapport à l'exécution précédente ont été déterminées.

Ensuite, une approche programmatique pour combiner les valeurs des paramètres a été essayée, en utilisant le principe de survie de l'algorithme génétique du «plus apte». Ici, "le plus adapté" signifie celui qui génère la sortie qui correspond le mieux à l'idéal. (Il se trouve que c'est aussi un jeu de mots sur la technique statistique de régression par "ajustement des moindres carrés", une technique utilisée pour juger de la qualité de l'approximation.)

Ce n'est que lorsque les paramètres du moteur ont été trouvés qui peuvent raisonnablement imiter un GM que la phase de tournoi du moteur commence. Dans cette phase, différents ensembles de valeurs de paramètres sont à nouveau opposés les uns aux autres, cette fois directement . Des techniques d'amélioration de l'algorithme génétique sont appliquées pour générer successivement de meilleures générations de moteur.

Dans ce projet de recherche, 36 paramètres ont été utilisés, y compris toutes les valeurs matérielles des pièces, et bon nombre des critères d'évaluation stratégique les plus courants, tels que les pions en arrière, les carrés faibles, la paire d'évêque, etc. Cependant, les chercheurs ont ajouté de nouveaux paramètres, tels que les valeurs de "pression du roi", de "mobilité" pour chaque type de pièce, la tour sur un fichier adjacent au roi, la tour sur un fichier semi-ouvert, la tour attaquant le roi sur le a - / b- / g- / h-file, séparation entre un pion passé et le roi en défense, et plus encore.

Malheureusement, les chercheurs ne précisent pas comment ils ont trouvé cette suite de paramètres et quels paramètres alternatifs ils ont pu tester et rejeter. Il serait raisonnable de supposer qu'ils ont commencé avec un ensemble beaucoup plus large et ont déterminé (par essais et erreurs) ceux qui avaient le plus d'effet sur les performances et ceux qui étaient soit insignifiants soit dérivés, et pouvaient donc être supprimés.

Si cela vous semble utile, vous pouvez trouver la recherche ici .

* Une mise en garde sur une phase de l'approche que les chercheurs ont utilisée est de mise. Dans son Introduction to Understanding Chess Move by Move , John Nunn a choisi "... des jeux durs entre grands maîtres ..." pour illustrer ses thèmes. Il ajoute ensuite:

Les lecteurs peuvent être assez surpris de voir le nombre de points d'interrogation qui ornent les jeux dans ce livre. Vous pourriez sûrement penser qu'avec seulement trente jeux à sélectionner, il aurait dû être facile de trouver des jeux sonores. Cependant, je peux vous assurer que ce n'était pas le cas. ... il est possible de trouver à redire à pratiquement n'importe quel jeu complexe et disputé ... Je n'ai jamais senti que mon jeu était à peu près complètement précis, donc personnellement je ne trouve pas ces révélations pénibles. Cependant, certains peuvent avoir du mal à admettre que les échecs tels que joués par les êtres humains sont moins précis qu'on ne le pensait auparavant.

Le point soulevé par le Dr Nunn suggère que l'approche initiale des chercheurs pour définir les paramètres du moteur en les obligeant à imiter les mouvements du grand maître peut être erronée parce que le jeu humain est défectueux . En fait, il est bien établi que les moteurs jouent déjà mieux que les humains .

Par conséquent, une meilleure approche pour définir les paramètres initiaux serait peut-être de faire correspondre un nouveau moteur à un moteur existant supérieur .

Il y a un joli site Web à:

https://hxim.github.io/Stockfish-Evaluation-Guide/

Il vous donne une introduction sur le fonctionnement des fonctions Stockfish.