Heuristique à mouvement nul
Pour les programmes d'échecs, l'heuristique à mouvement nul est une technique heuristique utilisée pour améliorer la vitesse de l'algorithme d'élagage alpha-bêta. Développée par Beal en 1989, puis Goetsch et Campbell en 1990, c'est Christian Donninger - impliqué dans le projet Hydra - qui a rendu cette technique accessible aux amateurs de programmation échiquéenne en publiant ses commentaires[1].
Principe
modifierLa technique d'élagage alpha-bêta est une optimisation de l'algorithme MinMax qui consiste en l'identification de « coupures » - soient les nœuds de l'arbre de décision qui sont tellement forts pour le joueur ayant l'initiative que le meilleur coup précédent de son adversaire aurait évité de le rendre possible. Puisque ce type de position n'est pas le résultat du meilleur coup possible de l'adversaire, toutes les branches de l'arbre de décision qui découlent de ces nœuds sont ignorées. Plus le logiciel génère de « coupures », plus la recherche du meilleur coup est rapide. L'heuristique à mouvement nul permet de deviner les nœuds de coupure en moins de tentatives, tout en gardant une précision raisonnable.
Le principe se base sur le fait que la majorité des coups aux échecs contribuent à améliorer la position de leur joueur. Donc si le joueur ayant l'initiative passait son tour (ce qui est contraire aux règles du jeu d'échecs) mais gardait quand même une position assez forte pour produire des coupures, alors la position courante engendrerait certainement aussi une coupure en jouant un coup (amélioration de la position grâce à ce nouveau coup).
En employant cette technique, le logiciel commence par faire passer le tour du joueur ayant le trait et ensuite lance un élagage alpha-bêta sur les positions résultantes mais à un niveau plus superficiel que sans utilisation du mouvement nul. Si cette recherche restreinte produit une coupure, alors on déduit qu'une recherche plus poussée - après avoir joué un coup - aurait aussi produit une coupure sur cette branche de l'arbre de décision. Ainsi la découverte de la coupure est plus rapide, accélérant le processus d'évaluation du logiciel. Si la recherche restreinte ne trouve aucune coupure, alors le logiciel procède à une recherche aussi approfondie que possible.
Cette approche repose sur deux prémisses. La première est qu'il faut que le désavantage de passer un tour soit plus fort que le désavantage de procéder à une recherche restreinte. Pourvu que cette recherche ne soit pas trop superficielle - en pratique celle-ci est moins profonde de deux ou trois demi-coups par rapport à une recherche classique - c'est généralement le cas. La deuxième est que cette recherche devra trouver suffisamment de coupures pour justifier le temps passé à utiliser cette technique (sinon on cumule les deux recherches). En pratique c'est souvent le cas.
Pourtant, certaines positions combinées à l'utilisation de cette méthode peuvent engendrer des erreurs grossières de tactique. Dans ces positions de zugzwang le joueur qui est au trait n'a que des mauvais coups comme choix et, par conséquent préférerait passer son tour plutôt que de jouer. Dans ces positions la recherche restreinte basée sur la « perte » du tour trouve une coupure alors que la recherche classique n'en aurait pas trouvé. La conséquence est que le logiciel évalue comme bonne une position pouvant être très mauvaise en réalité.
Il faut donc restreindre l'utilisation de cette technique d'optimisation et l'écarter dans les cas suivants :
- le joueur au trait est en échec,
- le joueur au trait n'a plus que son roi et des pions,
- le joueur au trait n'a que peu de pièces,
- le coup précédent dans l'arbre de décision était aussi de type heuristique à mouvement nul.
Une autre technique heuristique pour gérer les problèmes de zugzwang est déclinée par Omid David et Nathan Netanyahu[2]. Dans cette méthode, quand la fonction de recherche restreinte indique une rupture, plutôt que de couper la branche au nœud courant, la recherche est poursuivie à une profondeur réduite.
