au cours de la dernière année de développement de mon moteur d'Échecs (www.chessbin.com), une grande partie du temps a été consacrée à l'optimisation de mon code pour permettre une meilleure et plus rapide recherche de mouvements. Pendant ce temps, j'ai appris quelques trucs que je voudrais partager avec vous.

Mesure Du Rendement

Essentiellement, vous pouvez améliorer votre performance de deux façons:

• EVALUEZ vos noeuds plus vite
• rechercher moins de noeuds à venir avec la même réponse

votre premier problème dans l'optimisation du code sera la mesure. Comment savez-vous que vous avez vraiment fait une différence? Afin de vous aider avec ce problème, vous devez vous assurer que vous pouvez enregistrer de statistiques lors de votre déménagement de recherche. Ceux que je capture dans mon moteur d'échecs sont:

• Temps qu'il a fallu pour que la recherche compléter.
• nombre de noeuds recherchés

Cela vous permettra de évaluez et testez vos changements. La meilleure façon d'aborder le test est de créer plusieurs jeux de sauvegarde à partir de la position d'ouverture, le jeu du milieu et le jeu de fin. Noter l'heure et le nombre de noeuds recherchés en noir et blanc. Après avoir fait n'importe quels changements j'effectue habituellement des tests contre les jeux de sauvegarde mentionnés ci-dessus pour voir si j'ai fait des améliorations dans les deux matrices ci-dessus: le nombre de noeuds recherchés ou la vitesse.

pour compliquer encore plus les choses, après avoir fait un changement de code, vous pourriez exécuter votre moteur 3 fois et obtenir 3 résultats différents à chaque fois. Disons que votre moteur d'Échecs a trouvé le meilleur mouvement en 9, 10 et 11 secondes. C'est un écart d'environ 20%. Donc, avez-vous améliorer votre moteur de 10%, -20% ou était-ce juste variées charger sur votre pc. Comment savez-vous? Pour lutter contre cela, j'ai ajouté des méthodes qui permettront à mon moteur de jouer contre lui-même, il fera des mouvements pour les blancs et les noirs. De cette façon, vous pouvez tester non seulement le temps de la variance sur un mouvement, mais une série de 50 se déplace sur le cours du jeu. Si la dernière fois le jeu a pris 10 minutes et maintenant il faut 9, Vous avez probablement amélioré votre moteur de 10%. Le fait de recommencer le test devrait le confirmer.

Trouver Des Gains De Performance

maintenant que nous savons comment mesurer les gains de rendement, discutons de la façon d'identifier les gains de rendement potentiels.

si vous êtes dans un environnement.net, alors le profileur. net sera votre ami. Si vous avez un studio visuel pour Developers edition il est intégré gratuitement, mais il existe d'autres outils tiers que vous pouvez utiliser. Cet outil m'a permis d'économiser des heures de travail car il vous indiquera où votre moteur passe la plupart de son temps et vous permettra de vous concentrer sur vos points chauds. Si vous n'avez pas d'outil profileur, vous devrez peut-être enregistrer les horodatages au fur et à mesure que votre moteur passe par différentes étapes. Je ne le suggèrent. Dans ce cas, un bon profileur vaut son pesant d'or. Red Gate Ants Profiler is cher mais le meilleur que j'ai jamais essayé. Si vous n'en avez pas les moyens, utilisez-le au moins pour leur procès de 14 jours.

Votre profileur seront hargneux identifier des choses pour vous, cependant voici quelques petites leçons que j'ai apprises en travaillant avec C#:

• Faire tout privé
• Tout ce que vous ne pouvez pas faire Privé, faire il a scellé
• Faire autant de méthodes statiques possible.
• ne faites pas vos méthodes bavard, un la méthode longue est meilleure de 4 petites .
• échiquier stocké sous forme de Tableau [8][8] est plus lent alors un tableau de [64]
• remplacer int par byte dans la mesure du possible.
• Retour de vos méthodes dès possible.
• Meules sont mieux que les listes
• les matrices sont meilleures que les piles et liste.
• Si vous pouvez définir la taille de la liste avant de le remplir.
• Casting, de boxe, de l'onu-la boxe est mal.

Autres Gains De Performance:

je trouve déplacer de la génération et la commande est extrêmement important. Cependant, voici le problème tel que je le vois. Si vous évaluez le score de chaque mouvement avant de trier et d'exécuter Alpha Beta, vous serez en mesure d'optimiser votre ordre de mouvement de sorte que vous obtiendrez des coupures Alpha Beta extrêmement rapides. C'est parce que vous serez en mesure de la plupart du temps essayer le meilleur mouvement d'abord. Cependant, le temps que vous avez passé à évaluer chaque déménagement sera gaspillé. Par exemple, vous avez pu évaluer le score sur 20 mouvements, trier vos mouvements essayer les 2 premiers et a reçu un coup-off sur le numéro de mouvement 2. En théorie, le temps passé sur les 18 autres mouvements a été gaspillé.

d'un autre côté si vous faites une évaluation plus légère et beaucoup plus rapide dites captures, votre sort ne sera pas si bon et vous devrez rechercher plus de noeuds (jusqu'à 60% de plus). D'un autre côté, vous ne feriez pas une évaluation lourde sur tous les mouvements possibles. En tant que toute cette approche est généralement plus rapide.

trouver cet équilibre parfait entre avoir assez d'informations pour une bonne sorte et ne pas faire de travail supplémentaire sur les mouvements que vous n'utiliserez pas, vous permettra de trouver des gains énormes dans votre algorithme de recherche. En outre, si vous choisissez l'approche de tri plus pauvre, vous voudrez d'abord à une recherche moins profonde dire à ply 3, trier votre mouvement avant d'aller dans la recherche plus profonde (ce est souvent appelé itérative approfondissement). Ceci augmentera de manière significative améliorer vos tri et vous permettent de rechercher beaucoup moins de mouvements.

Répondre à une vieille question.

en supposant que vous avez déjà une table de transposition de travail.

Réduction Des Déménagements Tardifs. Cela a donné à mon programme environ 100 points elo et il est très simple à mettre en œuvre.

d'après mon expérience, à moins que votre implémentation ne soit très inefficace, alors la représentation réelle du tableau (0x88, bitboard,etc.) n'est pas si important que cela.

bien que vous pouvez criquer votre moteur d'échecs avec de mauvaises performances, un coup rapide et éclair générateur en lui-même ne va pas faire un programme en bonne.

les astuces de recherche utilisées et la fonction d'évaluation sont les facteurs prépondérants qui déterminent la force globale.

et les parties les plus importantes, de loin, de l'évaluation sont le matériel, les pions passés, la sécurité du Roi et la Structure du pion.

les parties les plus importantes de la recherche sont: L'élagage Null Move, Vérifiez L'Extension et la réduction tardive Move.

votre programme peut venir de très, très loin, ces techniques simples seules!

Bonne déplacer la commande!

une vieille question, mais les mêmes techniques s'appliquent maintenant qu'il y a 5 ans. Ne sommes-nous pas tous en train d'écrire nos propres moteurs d'Échecs, j'ai le mien appelé "Norwegian Gambit" que j'espère éventuellement rivaliser avec D'autres moteurs Java sur le CCRL. I comme beaucoup d'autres utilisent Stockfish pour des idées car il est si bien écrit et ouvert. Leur test cadre Fishtest et sa communauté donne également une tonne de bons conseils. Il est intéressant de comparer vos résultats d'évaluation avec ce que Stockfish obtient depuis comment évaluer est probablement le plus grand inconnu dans la programmation d'Échecs encore et Stockfish a disparu de nombreuses evals traditionnels qui sont devenus des légendes urbaines (comme le double bishop bonus). La plus grande différence cependant a été après que j'ai mis en œuvre les mêmes techniques que vous mentionnez, Negascout, TT, LMR, j'ai commencé à utiliser Stockfish pour la comparaison et j'ai remarqué comment pour la même profondeur Stockfish avait beaucoup moins de mouvements recherchés que j'ai obtenu (en raison du mouvement commander.)

Déplacer la commande de essentials

la seule chose qui est facilement oubliée est un bon ordre de mouvement. Pour que la coupure Alpha Beta soit efficace, il est essentiel d'obtenir les meilleurs coups en premier. D'autre part, il peut prendre beaucoup de temps, il est donc essentiel de le faire seulement si nécessaire.

1. tableau de Transposition
2. trier les promotions et les bonnes captures par leur gain
3. Killer moves
4. mouvements qui se soldent par un échec sur adversaire
5. l'Histoire de l'heuristique
6. Silence se déplace - trier par PSQT valeur

le tri doit être fait selon les besoins, Habituellement il suffit de trier les captures, et par la suite vous pouvez exécuter le tri plus coûteux des contrôles et des PSQT seulement si nécessaire.

à Propos de Java/C# vs C/C++/Assemblée

les techniques de programmation sont les mêmes pour Java que dans l'excellente réponse D'Adam Berent qui a utilisé C#. En plus de sa liste je voudrais mention evitant les tableaux D'objets, utilise plutôt de nombreux tableaux de primitives, mais contrairement à sa suggestion d'utiliser des octets, je trouve qu'avec un java 64 bits il y a peu de choses à sauvegarder en utilisant byte et int au lieu de 64bit long. Je suis aussi passé à la réécriture de C/C++/Assembly et je n'ai aucun gain de performance. J'ai utilisé le code d'assemblage pour les instructions bitscan comme LZCNT et POPCNT, mais plus tard J'ai découvert que Java 8 utilise aussi ces méthodes à la place des méthodes sur L'objet Long. À mon surprise Java est plus rapide, La machine virtuelle Java 8 semble faire un meilleur travail d'optimisation qu'un compilateur C.

je sais qu'une amélioration dont on a parlé aux cours D'AI à l'université où il y avait une énorme base de données de mouvements de finition. Donc avoir une base de données précalculée pour les jeux avec seulement un petit nombre de chiffres à gauche. De sorte que si vous frappez un positionnement près de la fin de votre recherche vous arrêtez la recherche et prendre une valeur prédéfinie qui améliore vos résultats de recherche comme l'approfondissement supplémentaire que vous pouvez faire pour les mouvements importants/critique sans beaucoup de temps de calcul. Je pense que ça vient aussi avec un changement heuristique dans un État de jeu tardif mais je ne suis pas un joueur d'Échecs donc je ne connais pas la dynamique de la fin de jeu.

soyez averti, obtenir la recherche de jeu droit dans un environnement fileté peut être une douleur royale (j'ai essayé