Dédié à tous ceux qui regardent maintenant la célèbre série télévisée "The Queen's Gambit". Plus de termes d'échecs dans notre nouvelle traduction.
Dans cet article, nous allons essayer de comprendre le fonctionnement des moteurs d'échecs en portant le moteur d'échecs Sunfish sur Go. Sunfish est remarquable pour sa simplicité et sa petite taille, mais il peut toujours jouer à une partie d'échecs décente. Go, d'autre part, est connu comme un langage de programmation simple et lisible, j'espère donc qu'ensemble, ils forment une excellente paire.
Pour créer un moteur d'échecs, vous devez d'abord décider de trois points importants:
- Comment représenter l'échiquier (cellules, pièces, coups autorisés)?
- Comment évaluez-vous le conseil (qui est le plus susceptible de gagner)?
- Comment trouver le coup optimal?
Les extraits de code de cet article sont simplifiés et ne contiennent que les parties les plus importantes. Vous pouvez trouver le code moteur complet sur github.com/zserge/carnatus ( carnatus est le nom latin du bar, espèce Sebastes carnatus).
Cellules et formes
Il est important de trouver une représentation pratique de la carte qui ne prend pas beaucoup de place, car des milliers de variations de la carte seront stockées en mémoire tout en recherchant le mouvement optimal.
Habituellement, un tableau est un ensemble de cellules. Nous ajouterons un rembourrage autour du plateau standard 8x8 afin que les mouvements de pièces invalides tombent dans cette zone. Cela nous permettra d'éviter la vérification des limites et de simplifier grandement le code.
Nous utiliserons un tableau linéaire. La plus longue distance qu'une pièce d'échecs peut parcourir est le mouvement d'un chevalier de 2 cases. Bien sûr, d'autres pièces coulissantes peuvent se déplacer sur de longues distances, mais ces mouvements seront évalués séquentiellement au fur et à mesure que chaque carré est traversé, ce qui signifie que les limites de la planche seront détectées avant que la pièce ne puisse les dépasser.
Ainsi, nous avons besoin d'un espace à deux cellules le long des bords de la carte. Nous pourrions créer un tableau 12x12, mais puisque nous le représentons comme un tableau de lignes, nous avons besoin d'un tableau 12x10 car le carré de retrait le plus à droite sur la ligne précédente peut être utilisé comme carré de retrait le plus à gauche sur la ligne suivante (× = retrait):
×××××××××× ×××××××××× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×××××××××× ××××××××××
Dans notre notation, «a1» ressemblerait à 9 × 10 + 1 = 91, et «a8» ressemblerait à «2 × 10 + 1» = 21.
Chaque cellule du tableau représenterait une pièce d'échecs, un carré vide ou une zone d'indentation. aurait pu utiliser des constantes numériques pour ces valeurs, mais pour simplifier le débogage, nous utilisons des caractères lisibles par l'homme.
| | RNBQKBNR | PPPPPPPP | ........ | ........ | ........ | <- ........ | ........ | ........ | pppppppp | rnbkqbnr | | |
Décodage des abréviations
R — rook —
N — knight —
B — bishop —
Q — queen —
K — king —
N — knight —
B — bishop —
Q — queen —
K — king —
Enfin, nous pouvons commencer à écrire du code:
type Piece byte
func (p Piece) Value() int { ... }
func (p Piece) Ours() bool { ... }
func (p Piece) Flip() Piece { ... }
type Board [120]piece
func (b Board) Flip() Board { ... }
type Square int
func (s Square) Flip() Square { ... }
Les formes ont une certaine valeur. Ces valeurs sont nécessaires pour évaluer les positions au tableau et comprendre qui gagne. Habituellement, un pion = 100, un chevalier = 280, un évêque = 320, une tour = 479, une reine = 929 et un roi est si précieux qu'il bat 8 reines (pions transformés en reines) en conjonction avec des paires de chevaliers, d'évêques et de tours. Si nous avons toute cette richesse, mais que nous perdons le roi, le comptage montrera toujours que nous perdrons.
Chaque type a une méthode Flip () qui renvoie la même valeur après avoir retourné le plateau avant que l'adversaire ne bouge. Pour les formes, cela change la casse du symbole de forme. Aux cases, il renvoie 119 cases (en comptant à partir de l'autre extrémité du plateau). Quant au plateau, il copie toutes les pièces des cases dans l'ordre inverse, en changeant leur cas.
Générateur de course
Donc, nous avons déjà les éléments de base pour le moteur, et maintenant nous pouvons penser aux positions de jeu. La position est un plateau avec des pièces et des états supplémentaires dans le jeu, comme une case de passage, une case errante et des possibilités de roque. Si nous voulions simplifier le jeu, nous pourrions réutiliser le type de plateau, mais nous créerons un type de position distinct pour les mouvements et l'évaluation du plateau.
Qu'est-ce qu'un déménagement? Il s'agit d'une combinaison de deux cellules - la cellule où se trouvait la pièce avant le déplacement et la cellule où la pièce se déplaçait. La position est un échiquier avec le score, les règles du roque pour chaque joueur et les cases de passage / errance. Les deux types ont également une méthode Flip () pour les mouvements de l'adversaire.
type Move struct {
from Square
to Square
}
func (m Move) Flip() Move { ... }
type Position struct {
board Board //
score int // — ,
wc [2]bool //
bc [2]bool //
ep Square // ,
kp Square // ,
}
func (p Position) Flip() Position { ... }
Maintenant, nous pouvons écrire la première grande méthode - le générateur de mouvements autorisés. Nous ne nous soucions que des pièces blanches, car pour jouer au noir, nous retournerons le plateau et déplacerons à nouveau le blanc.
Pour générer tous les coups valides, nous avons besoin de:
- faire une liste de tous les mouvements d'une étape dans chaque direction pour chaque pièce;
- faites de même pour toutes les cellules, en ignorant les pièces non blanches;
- désigner un mouvement dans toutes les directions possibles pour chaque pièce blanche;
- si la longueur du mouvement d'une pièce n'est pas limitée (tour, fou, reine), continuez à la déplacer jusqu'à ce qu'elle rencontre un obstacle sur son chemin: une pièce de l'adversaire ou un espace derrière le bord du plateau.
Il s'agit d'un code simplifié qui ne prend pas en compte la capture et le roque. Vous pouvez trouver l'implémentation complète sur Github , ce n'est pas très différent.
Pour rendre l'arithmétique de direction plus lisible, nous utiliserons les constantes de direction N / E / S / W:
const N, E, S, W = -10, 1, 10, -1
var directions = map[Piece][]Square{
'P': {N, N + N, N + W, N + E},
'N': {N + N + E, E + N + E, E + S + E, S + S + E, S + S + W, W + S + W, W + N + W, N + N + W},
'B': {N + E, S + E, S + W, N + W},
'R': {N, E, S, W},
'Q': {N, E, S, W, N + E, S + E, S + W, N + W},
'K': {N, E, S, W, N + E, S + E, S + W, N + W},
}
func (pos Position) Moves() (moves []Move) {
for index, p := range pos.board {
if !p.ours() {
continue
}
i := Square(index)
for _, d := range directions[p] {
for j := i + d; ; j = j + d {
q := pos.board[j]
if q == ' ' || (q != '.' && q.ours()) {
break
}
if p == 'P' {
if (d == N || d == N+N) && q != '.' {
break
}
if d == N+N && (i < A1+N || pos.board[i+N] != '.') {
break
}
}
moves = append(moves, Move{from: i, to: j})
if p == 'P' || p == 'N' || p == 'K' || (q != ' ' && q != '.' && !q.ours()) {
break
}
}
}
}
return moves
}
Ce sont toutes les règles du jeu d'échecs que nous devons prendre en compte pour effectuer des mouvements valides. L'étape suivante consiste à appliquer un mouvement à la position pour créer une nouvelle position de jeu. Sans prendre en compte la capture en route, la promotion des pions et le roque, la méthode ressemblerait à ceci:
func (pos Position) Move(m Move) (np Position) {
np = pos
np.board[m.to] = pos.board[m.from]
np.board[m.from] = '.'
return np.Flip()
}
Il déplace simplement la pièce, marque la cellule sur laquelle elle était auparavant vide et retourne le plateau. L'implémentation complète de la méthode peut être trouvée sur Github , elle gère correctement tous les mouvements spéciaux de pion et de roi.
A ce stade, vous pouvez jouer aux échecs "homme contre homme", en contrôlant le processus et en ne faisant que des coups légaux. Ou vous pouvez créer un moteur d'échecs primitif qui effectue des mouvements aléatoires jusqu'à ce qu'il perde.
Mais comment comprendre que nous perdons?
Évaluation du conseil
Des points sont attribués pour chaque poste au tableau. Au départ, le score est nul, puisque les deux joueurs commencent sur un pied d'égalité. Après avoir terminé un mouvement, le score change en fonction des pièces capturées et de la façon dont les pièces ont changé de position sur le plateau.
Dans le cas le plus simple, nous pouvons compter les pièces sur le plateau et additionner leur valeur (moins les pièces de l'adversaire). Un tel calcul montrera si le roi est déclaré échec et échec et mat. Mais c'est un système d'évaluation très faible.
Une approche beaucoup plus précise et étonnamment simple est les tableaux de rapport forme-carré ( PST- Tables pièces carrées). Pour chaque pièce, une table est créée de la même taille qu'un échiquier, où une valeur correspondante est attribuée à chaque case. Ces valeurs sont empiriques, je les ai donc simplement extraites du moteur Sunfish.
En fait, les moteurs d'échecs plus avancés mettent à jour les PST pendant le jeu parce que la valeur des pièces change (c'est-à-dire que les pions deviennent plus précieux vers la fin de la partie). Mais nous aurons un moteur simple.
Pour évaluer la position après le déménagement, nous avons besoin de:
- déterminer la cote de la position actuelle,
- soustraire la valeur de la pièce déplacée,
- ajouter une nouvelle valeur de chiffre selon la table PTS,
- ajoutez la valeur de la pièce capturée, le cas échéant.
De plus, nous devons ajuster dans le tableau PST la valeur de la tour pendant le roque et la valeur du pion pendant la promotion ou la capture sur la passe. Mais ici, nous ne considérerons pas ceci:
var pst = map[Piece][120]int{
'P': { ... },
'N': { ... },
'B': { ... },
'R': { ... },
'Q': { ... },
'K': { .... },
}
func (pos Position) value(m Move) int {
i, j := m.from, m.to
p, q := Piece(pos.board[i]), Piece(pos.board[j])
// PST-
score := pst[p][j] - pst[p][i]
if q != '.' && q != ' ' && !q.ours() {
// PST-
score += pst[q.Flip()][j.Flip()]
}
return score
}
Nous pouvons maintenant créer un moteur légèrement plus avancé qui choisira le meilleur mouvement possible, plutôt que l'un des plus valides.
Mais les vrais moteurs d'échecs effectuent une analyse plus approfondie et parcourent les branches des mouvements possibles de chaque côté pour trouver le meilleur coup possible à long terme.
Algorithme de recherche
L'algorithme de recherche le plus courant dans les moteurs d'échecs est plus simple: la recherche en profondeur d'abord, qui commence à la racine et descend jusqu'à une limite de profondeur donnée, en répétant tous les mouvements possibles avant de revenir. Pour chaque valeur de position de trait est calculée en utilisant un algorithme minimax (minimax) c élagage alpha-beta (élagage alpha-beta ).
Minimax est une règle utilisée pour minimiser les pertes possibles dans le pire des cas: le joueur considère tous les meilleurs coups de l'adversaire et choisit un tel coup pour que la meilleure stratégie de l'adversaire rapporte le plus de points possible.
Un simple algorithme minimax serait trop lent pour les échecs et nécessiterait de répéter trop de coups pour en trouver un bon.
L'élagage alpha-bêta est utilisé pour accélérer l'algorithme minimax en supprimant les nœuds qui ne valent pas la peine d'être pris en compte. L'écrêtage alpha-bêta est basé sur la logique suivante: imaginez que vous jouez aux échecs et découvrez un très bon coup A. Vous continuez à regarder le tableau et trouvez un coup encore meilleur B.Mais ensuite vous analysez la situation plus en profondeur et comprenez que si vous choisissez au coup B, l'ennemi vous déclarera check et checkmate en quelques coups. Vous allez maintenant rejeter B et ne pas perdre de temps à analyser d'autres combinaisons possibles après B.
Le découpage minimax et alpha-bêta est important pour comprendre le fonctionnement du moteur d'échecs. Le moteur Sunfish utilise un algorithme de recherche avancé MDF (f) , qui est également une variante de l'algorithme minimax combiné avec le clipping.
Dans notre moteur, nous allons progressivement augmenter la profondeur de recherche et appeler l'algorithme MDF (f) pour trouver les limites inférieure et supérieure du résultat optimal. L'algorithme MDF (f) utilisera une itération d'écrêtage alpha-bêta avec un cache de transposition.
L'argent de transposition est un cache où pour chaque position sur le plateau nous mémorisons la profondeur, le décompte et le déplacement qui nous ont conduits à cette position. Ensuite, lors de l'examen d'une nouvelle position, elle est d'abord vérifiée par rapport à la table de transposition.
Je ne publierai pas le code de l'algorithme de recherche ici, car il ne s'agit que de quelques lignes de recherche récursive, mais vous pouvez toujours trouver le code source complet du moteur d'échecs sur GitHub .
Et après?
Si vous êtes intéressé par des moteurs d'échecs simples, je vous recommande fortement de jouer avec Sunfish. À propos, Sunfish est basé sur le moteur Micromax et est livré avec une excellente documentation de l'auteur, qui vaut vraiment la peine d'être lue.
Pour notre moteur en Go, j'ai ajouté une petite implémentation du protocole UCI afin qu'il puisse être utilisé avec l'interface utilisateur PyChess. Très probablement, il y a encore beaucoup de bugs et beaucoup de potentiel d'amélioration, mais c'était une voie intéressante: de l'idée de développer un moteur d'échecs à un programme d'échecs informatique prêt à l'emploi.
Oui, il est faible, mais il joue à de vrais jeux d'échecs!
J'espère que vous avez apprécié cet article. Vous pouvez me suivre sur Github , Twitter ou abonnez-vous via rss .