Comment choisir le meilleur algorithme pour un jeu de société comme les dames?

15

Comment choisir le meilleur algorithme pour un jeu de société comme les dames?

Jusqu'à présent, je n'ai considéré que trois algorithmes, à savoir le minimax, l'élagage alpha-bêta et la recherche d'arbre Monte Carlo (MCTS). Apparemment, la taille alpha-bêta et les SCTM sont des extensions de l'algorithme de base minimax.

Joey
la source

Réponses:

17

tl; dr:

  • Aucun de ces algorithmes n'est pratique pour le travail moderne, mais ce sont de bons endroits pour commencer pédagogiquement.

  • Vous devriez toujours préférer utiliser l'élagage Alpha-Beta plutôt que la recherche nue minimax.

  • Vous devriez préférer utiliser une forme de recherche guidée heuristique si vous pouvez trouver une heuristique utile. Venir avec une heuristique utile nécessite généralement beaucoup de connaissances dans le domaine.

  • Vous devriez préférer utiliser la recherche Monte Carlo Tree lorsque vous manquez d'une bonne heuristique, lorsque les ressources de calcul sont limitées et lorsque les erreurs n'ont pas des conséquences surdimensionnées dans le monde réel.

Plus de détails:

Dans la recherche minimax, nous n'essayons pas d'être très intelligents. Nous utilisons simplement une approche de programmation dynamique standard. Il est facile de comprendre la valeur des mouvements de différence si nous sommes proches de la fin du jeu (puisque le jeu se terminera au prochain coup, nous n'avons pas à regarder très loin). De même, si nous savons ce que fera notre adversaire lors du dernier coup du jeu, il est facile de comprendre ce que nous devons faire lors de l'avant-dernier coup. En fait, nous pouvons traiter l'avant-dernier coup comme le dernier coup d'une partie plus courte. Nous pouvons ensuite répéter ce processus. L'utilisation de cette approche est certaine de découvrir les meilleures stratégies dans un jeu de forme étendue standard, mais nous obligera à considérer chaque mouvement possible, ce qui est impossible pour tous, sauf les jeux les plus simples.

L'élagage Alpha-Beta est une amélioration stricte de la recherche Minimax. Il utilise le fait que certains mouvements sont évidemment pires que d'autres. Par exemple, aux échecs, je n'ai pas besoin d'envisager un mouvement qui vous donnerait la possibilité de me mettre en échec et mat, même si vous pouviez faire autre chose à partir de cette position. Une fois que je vois qu'un mouvement peut entraîner une perte, je ne vais pas me soucier de ce qui pourrait arriver d'autre à partir de ce moment. Je vais regarder d'autres choses. Cet algorithme est également certain de donner le résultat correct, et est plus rapide, mais doit toujours prendre en compte la plupart des mouvements dans la pratique.

Il existe deux façons courantes de contourner le coût informatique extrême de la résolution exacte de ces types de jeux:

  1. Utilisez une méthode heuristique (la recherche A * est l'algorithme habituel à des fins pédagogiques, mais la recherche de repos est une idée similaire dans les jeux à 2 joueurs). C'est juste une fonction qui donne une estimation de la valeur d'un état du jeu. Au lieu de considérer tous les mouvements dans un jeu, vous pouvez simplement considérer les mouvements à une distance finie, puis utiliser la valeur de l'heuristique pour juger de la valeur des états que vous avez atteints. Si votre heuristique est cohérente (essentiellement: si elle surestime toujours la qualité des états), alors cela donnera toujours la bonne réponse, mais avec d'énormes accélérations dans la pratique.

  2. Utilisez des déploiements (comme Monte Carlo Tree Search). Fondamentalement, au lieu de considérer chaque mouvement, exécutez quelques milliers de jeux simulés entre des joueurs agissant au hasard (c'est plus rapide que de considérer tous les mouvements possibles). Attribuez une valeur aux états égale au taux de gain moyen des jeux à partir de celui-ci. Cela peut ne pas donner la bonne réponse, mais dans certains types de jeux, il fonctionne de manière fiable. Il est souvent utilisé comme une extension de techniques plus précises, plutôt que d'être utilisé seul.

John Doucette
la source
Un * ne semble pas vraiment correspondre au contexte des jeux à deux joueurs comme le font les autres algorithmes? Remarque sur les SCTM: les implémentations typiques ne "prennent pas en compte tous les mouvements vers une certaine profondeur" et démarrent ensuite les déploiements; au lieu de cela, les implémentations typiques développent dynamiquement l'arborescence de recherche d'arborescence, la développant davantage dans les parties plus prometteuses (parties où de nombreux déploiements sont poussés vers la stratégie de sélection), la développant moins dans les parties moins prometteuses.
Dennis Soemers
1
@JohnDoucette pourquoi diriez-vous "Aucun de ces algorithmes n'est pratique pour le travail moderne, mais ce sont de bons endroits pour commencer pédagogiquement." Dans le cas des SCTM, il semble très approprié pour le travail moderne, même pour la recherche en solo, lorsque la transition vers le prochain état avec un état et une action est bien définie. Accepteriez-vous?
Miguel Saraiva
1
@MiguelSaraiva À lui seul, les SCTM ne sont pas quelque chose que vous utiliseriez habituellement pour une application moderne. Combiné avec quelque chose comme un DNN pour fournir une heuristique apprise, ce serait plutôt bien.
John Doucette
1
@JohnDoucette "Les SCTM ne sont pas quelque chose que vous utiliseriez habituellement pour une application moderne". Tout d'abord, la "modernité" à laquelle vous faites référence a fait sa grande percée en 2016 (SCTM + DNN) et il semble que vous sous-entendiez que tout ce qui précède est obsolète (évidemment faux). En fait, il pourrait même être plus plausible de dire que les SCTM ne sont normalement pas utilisés à cause du contraire: il est TROP avancé: Il y a des tas d'applications dans l'industrie qui sont vraiment obsolètes et pourraient être AMÉLIORÉES aux SCTM. Pour beaucoup de ces MCTS + DNN, ce n'est qu'un rêve lointain, car la pré-formation est à peu près inconcevable.
Johan
1
@Johan Cela me semble juste pour les applications industrielles , mais la question concerne "un jeu de société comme les dames". Pour ce genre de problèmes de jouets, je pense que les SCTM ne sont pas la bonne approche moderne. Il y a certainement beaucoup de problèmes du monde réel où ce serait une énorme amélioration par rapport aux systèmes déployés existants.
John Doucette
7

NB La raison pour laquelle je n'ai choisi que ces trois algorithmes est due au temps dont je dispose pour les comprendre. À partir d'une petite recherche, j'ai trouvé que ces algorithmes sont essentiellement imbriqués dans l'algorithme minimax. Donc, si je peux comprendre l'un, les deux autres se mettront en place.

Dans ce contexte, je recommanderais de commencer avec Minimax . Des trois algorithmes, Minimax est le plus facile à comprendre.

Alpha-Beta , comme d'autres l'ont mentionné dans d'autres réponses, est une amélioration stricte par rapport à Minimax. Minimax fait fondamentalement partie de la mise en œuvre d'Alpha-Beta, et une bonne compréhension d'Alpha-Beta nécessite de commencer par une bonne compréhension de Minimax de toute façon. S'il vous reste du temps après avoir compris et implémenté Minimax, je vous recommande de passer ensuite à Alpha-Beta et de le construire au-dessus de Minimax. Commencer avec Alpha-Beta si vous ne comprenez pas encore Minimax n'a pas vraiment de sens.

Monte-Carlo Tree Search est probablement un peu plus avancé et plus compliqué à comprendre vraiment et profondément. Au cours de la dernière décennie, les SCTM ont vraiment grandi pour devenir beaucoup plus populaires que les deux autres. Par conséquent, de ce point de vue, la compréhension des SCTM peut être plus "utile".

La connexion entre Minimax et MCTS est moins directe / évidente que la connexion entre Minimax et Alpha-Beta, mais il existe toujours une connexion au moins sur le plan conceptuel. Je dirais qu'avoir une bonne compréhension de Minimax est toujours bénéfique avant de plonger dans les SCTM ; en particulier, comprendre Minimax et ses défauts / points faibles peut fournir un contexte utile / vous aider à comprendre pourquoi les SCTM sont devenus «nécessaires» / populaires.


Pour conclure, à mon avis:

  • Alpha-Beta est strictement meilleur que Minimax, mais aussi fortement lié / construit au-dessus de Minimax; alors, commencez par Minimax, optez pour Alpha-Beta après si le temps le permet
  • Les SCTM ont des forces / faiblesses différentes, sont souvent meilleurs que l'Alpha-Beta dans les problèmes "modernes" (mais pas toujours), une bonne compréhension de Minimax sera probablement bénéfique avant de commencer à plonger dans les SCTM
Dennis Soemers
la source
Y a-t-il un autre algorithme que vous pourriez suggérer que je pourrais également utiliser? C'est comme un niveau d'élagage alpha beta
Joey
@Joey Hmm non pas vraiment. Minimax est un point de départ très naturel, je le recommande fortement si vous débutez. C'était fondamentalement le premier algorithme développé pour des jeux comme les échecs / les dames / tic tac toe / peu importe. Par la suite, des centaines, voire des milliers d'améliorations ont été développées en plus, dont beaucoup peuvent probablement être trouvées sur chessprogramming.wikispaces.com/Search . L'Alpha-Beta est l'amélioration la plus naturelle à rechercher au-dessus de Minimax.
Dennis Soemers
@Joey Monte-Carlo Tree Search est un peu différent (n'a pas nécessairement Minimax comme base), est intéressant, amusant, populaire et très pertinent dans l'IA "moderne". Pourtant, les fondations sont importantes, je ne recommanderais pas de commencer immédiatement avec les SCTM si vous ne comprenez pas encore Minimax + Alpha-Beta, même si cela est techniquement possible.
Dennis Soemers
Merci pour ce site. C'est une richesse de connaissances que je peux maintenant lire. Le plus difficile à apprendre de nouvelles choses est de trouver le bon matériel pour vous aider à comprendre. Merci encore pour le site
Joey
@Joey Je ne suis pas sûr à 100% si le programme d'échecs est le site le plus facile à apprendre (et il semble y avoir une remarque effrayante en haut que le site pourrait disparaître fin juillet). Si je me souviens bien, de nombreuses descriptions sont plutôt courtes / probablement pas faciles à comprendre si vous êtes débutant dans le domaine. Ce sera au moins une bonne collection complète de noms de toutes sortes d'algorithmes / améliorations, et vous pouvez essayer de rechercher les sources originales ou de rechercher tous ces noms sur Google pour des informations plus détaillées ailleurs.
Dennis Soemers
1

Si vous devez choisir entre l'élagage Minimax et Alpha-Beta, vous devez choisir Alpha-beta. Il est plus efficace et plus rapide car il peut tailler une partie substantielle de votre arbre d'exploration. Mais vous devez ordonner les actions du meilleur au pire en fonction du point de vue max ou min, afin que l'algorithme puisse rapidement réaliser si l'exploration est nécessaire.

Kaizokun
la source