chess_engine_using_python
1.0.0
Ce référentiel contient l'implémentation d'un moteur d'échecs utilisant l'algorithme de recherche Minimax , Alpha-Beta et Quiescence . Le notebook Jupyter à l’intérieur d’un conteneur Docker est utilisé pour le codage. Tous les Jupyter Notebook sont également disponibles sous forme d’image Docker.
Consultez le document de projet pour voir une analyse détaillée.
docker pull codewithnk/chess-engine-using-python:latestdocker run -p 8888:8888 -v $( pwd ) codewithnk/chess-engine-using-python:latest Le cœur des échecs en jouant aux échecs en minmax. Minmax associe généralement la pièce noire à MAX et la pièce blanche à MIN, et évalue toujours du point de vue blanc.
L'algorithme Minmax est un algorithme de recherche contradictoire en théorie des jeux. Il utilise l'arbre de jeu et comprend deux joueurs MIN et MAX. Les deux joueurs tentent d'annuler l'action des autres. Max essaie de maximiser le résultat tandis que MIN essaie de minimiser le résultat. Les deux joueurs jouent alternativement, en supposant qu’ils jouent tous les deux de manière optimale. Un jeu optimal signifie que les deux joueurs jouent selon la règle, c'est-à-dire que MIN minimise le résultat et MAX maximise le résultat.
L'algorithme minmax utilise l'approche Depth First Search pour trouver le résultat. De plus, il utilise également le retour en arrière et la récursivité. L'algorithme traversera jusqu'au nœud terminal, puis reviendra en arrière tout en comparant toutes les valeurs enfants. Il sélectionnera la valeur minimale ou maximale, en fonction de qui c'est le tour. Il propagera ensuite la valeur à son parent. Il utilise une fonction d'évaluation statique pour déterminer la valeur à chaque nœud feuille. Il profite du jeu à somme nulle.
Moteur d'échecs utilisant Minmax
Minmax utilise Depth First Search (DFS) sur Game Tree, donc la complexité temporelle de l'algorithme minmax est O(b**m) , où b est le facteur de branchement de l'arbre de jeu et m est la profondeur maximale de l'arbre.
La complexité spatiale de l'algorithme minmax est également similaire à DFS qui est O(bm) , où b est le facteur de branchement de l'arbre de jeu et m est la profondeur maximale de l'arbre.
L'algorithme Minmax est terminé. Il trouvera certainement une solution, si elle existe, dans l'arbre de recherche fini.
L'algorithme Minmax est optimal si les deux adversaires jouent de manière optimale.
L'algorithme minmax peut être optimisé en élaguant quelques branches. Les branches taillées sont celles qui n’affecteront pas le résultat. Cela améliorera la complexité temporelle. Cette version minmax est connue sous le nom de minmax avec élagage alpha-bêta. Il est également appelé algorithme alpha-bêta.
Dans Alpha-Beta Pruning, il existe deux valeurs, Alpha et Beta. Voici les quelques points à considérer concernant l’alpha et la bêta :
Lors du retour en arrière, seule la valeur du nœud est transmise au parent, pas les valeurs alpha et bêta.
La condition pour l’élagage alpha-bêta :
α >= β
L'efficacité de l'algorithme alpha-bêta dépend fortement de l'ordre de parcours. Il joue un rôle crucial dans la complexité temporelle et spatiale.
Dans certains cas, aucun nœud ou sous-arbre n’est supprimé de Game Tree. Dans ce cas, le meilleur mouvement se produit dans le sous-arbre droit de l'arbre du jeu. Cela entraînera une complexité temporelle accrue.
Dans ce cas, le nombre maximum de nœuds et de sous-arbres est élagué. Les meilleurs mouvements se produisent dans le sous-arbre gauche. Cela réduira la complexité temporelle et spatiale.
Moteur d'échecs utilisant l'élagage alpha-bêta
L'algorithme Alpha Beta utilise également la recherche en profondeur (DFS) sur Game Tree.
L'algorithme Alpha-Beta est terminé. Il trouvera certainement une solution, si elle existe, dans l'arbre de recherche fini.
L'algorithme Alpha-Beta est optimal si les deux adversaires jouent de manière optimale.
La recherche de quiescence est une modification en plus de l'élagage alpha-bêta avec min-max. Quiescence signifie calme. Cette recherche n'évalue que les mouvements silencieux. En d’autres termes, après une certaine profondeur, il utilise uniquement les mouvements de capture pour calculer les prochains mouvements. Une recherche de quiescence peut éviter l'effet d'horizon.
L'effet d'horizon se produit lorsque nous cherchons uniquement à une certaine profondeur, mais il peut arriver que si nous regardons un niveau de plus en profondeur, le déplacement rapporte moins de points. Une recherche de quiescence utilise uniquement des mouvements de capture pour éviter cela. La recherche de quiescence réduit également le facteur de branchement à différents niveaux, ce qui donne lieu à un algorithme rapide.
L'algorithme de recherche de quiescence utilise également la recherche en profondeur d'abord (DFS) sur Game Tree.
L'algorithme de recherche de quiescence est terminé. Il trouvera certainement une solution, si elle existe, dans l'arbre de recherche fini.
L'algorithme de recherche de quiescence est optimal si les deux adversaires jouent de manière optimale.
