Analyse & Programmation

Ordonnancement des coups

Si vous avez bien étudiez l'algorithme de recherche alpha-bêta, vous aurez sûrement compris qu'il est avantageux d'avoir les meilleurs coups au début de la recherche car ils vont générer plus de coupes plus rapidement. Si vous naviguez un peu dans le monde des programmeurs de moteur d'échecs vous entendrez souvent parler d'ordonnancement des coups.

Avec un bon ordonnancement des coups, les coupes peuvent augmenter exponentiellement. C'est une des raisons pourquoi nous avons parlé de deux fonctions séparés pour générer les coups. En jouant les coups de capture avant les coups normaux, vous augmentez les chances d'avoir un coup qui a un meilleur score au début de la recherche générant plus de coupes et réduisant le nombre de noeud à explorer.

Alpha-bêta par itération

La technique de recherche alpha-bêta par itération permet deux choses.

1. Un meilleur ordonnancement des coups;
2. Mieux contrôler la durée de recherche du moteur.

Nous savons qu'il faut un bon ordonnancement des coups pour que l'alpha-bêta soit efficace. De faire des recherches de plus en plus profonde est ce qui permet de bien ordonnancer les coups. Chaque itération utilise l'évaluation de la précédente pour réordonner ces coups ce qui permet à la recherche de toujours être optimal à chaque itération.

Si vous commencez la recherche du moteur avec un profondeur de 8 par exemple, vous n'avez aucun contrôle sur la durée de recherche. Et si vous interrompez la recherche à n'importe quel moment, le résultat sera hasardeux car vous ne saurez pas s'il y avait un coup meilleur plus loin dans la liste.

En y allant par itération, vous pouvez toujours utilisez le résultat de l'itération précédente qui est complète.

Au départ, pour tester votre algorithme vous allez probablement y avec une profondeur fixe et vous aurez déjà un moteur capable de bien évaluer le jeu, mais ça vous semblera long même pour une profondeur très courte.

<< Préc - Suivant >>