gambit
Un moteur d'échecs en Scala 3. Génération de coups, évaluation de positions et recherche - un cerveau complet pour jouer aux échecs, construit avec scala-cli.
Un moteur d'échecs en Scala 3. Trois choses difficiles à la fois : une génération de coups sans faute, une évaluation de position sensée et une recherche qui choisit un bon coup en un temps raisonnable. Un cerveau complet pour jouer.
Introduction
Un moteur d'échecs n'a que l'air d'un seul projet. Ce sont trois sous-systèmes, dont chacun peut ruiner l'ensemble à sa manière, et ce n'est qu'ensemble qu'ils produisent quelque chose qui joue sensément. gambit consiste à faire s'accorder ces trois parties assez bien pour que le résultat commence à ressembler à un vrai adversaire, et non à un générateur de coups aléatoires.
Scala 3 offre ici un langage expressif pour modéliser l'échiquier, les coups et l'arbre des variantes. Mais le vrai défi n'est pas syntaxique, il est algorithmique : un générateur sans faute, une évaluation juste et une recherche qui ne calcule pas indéfiniment.
Trois problèmes qui doivent s'accorder
Un générateur de coups qui laisse passer un coup illégal par million de positions fera jouer au moteur quelque chose d'impossible. Une évaluation qui pèse mal les pièces le conduira vers une défaite avec conviction. Une recherche sans élagage réfléchira des heures à un coup qui devrait tomber en une seconde.
tous les coups légaux dans toute position, y compris le roque, la prise en passant et la promotion.
un nombre exprimant qui est mieux placé tant que la partie continue.
alpha-beta, qui écarte les branches qui ne valent pas la peine d'être calculées.
Aucun de ces trois ne peut être négligé. Un moteur faible dans l'un d'eux perdra, et pour une raison précise et identifiable, pas par faiblesse générale.
Alpha-beta, l'art de ne pas calculer
La recherche naïve examine chaque continuation possible, et il y en a des milliards dès quelques coups de profondeur. L'élagage alpha-beta remarque que si une réponse de l'adversaire réfute déjà une ligne, le reste de ses réponses n'a pas besoin d'être calculé. Avec un bon ordre des coups, cela coupe l'espace si fort que le moteur va plus profond dans le même temps.
Nœuds à explorer à la même profondeur (indicatif, milliers)
Ce n'est pas une petite optimisation mais la différence entre un moteur qui voit trois coups à l'avance et un qui en voit six. Aux échecs, cette profondeur se traduit directement en force de jeu.
Perft, la preuve de la correction du générateur
La correction du générateur de coups se vérifie avec ce qu'on appelle le perft : vous comptez toutes les positions atteignables à une profondeur donnée et comparez à des nombres que toute la communauté des échecs connaît par cœur. Si votre nombre ne correspond pas, vous avez un bug quelque part, et cela montre exactement à quelle profondeur l'écart commence.
Perft depuis la position de départ
| Profondeur | Nombre de positions |
|---|---|
| 1 | 20 |
| 2 | 400 |
| 3 | 8902 |
| 4 | 197281 |
| 5 | 4865609 |
Le résultat est un moteur complet qui prend une position et rend un coup : le générateur expose toutes les continuations légales, l'évaluation dit laquelle mène vers un meilleur côté, et alpha-beta cherche aussi profond que le temps le permet. Trois sous-systèmes qui ne sont que des parties à eux seuls forment ensemble un adversaire qui sait jouer.
Le perft est l'exemple type d'un test qui peut vraiment échouer. Il ne vérifie pas que quelque chose fonctionne, il compare votre nombre à un nombre connu à l'avance, donc tout bug dans le générateur fausse aussitôt le résultat.
Plus de projets
D'autres réalisations de la même catégorie - découvrez comment nous abordons des défis similaires.
Vous avez un projet similaire ?
Contactez-nous - le devis est gratuit et arrive sous une heure.