Comment appliquer l'algorithme min max à un jeu hexadécimal

Question

Comment concevoir un algorithme efficace pour le jeu hexadécimal en utilisant l'algorithme min max puisque son facteur de branchement est trop élevé. Le jeu de tic tac toe normal est fait en utilisant l'algorithme min max mais dans ce cas pour un jeu de plateau 11 * 11 nous avons 121 combinaisons donc pour réduire le nombre de combinaisons quelle est l'approche minmize cette combinaison

Answer 1

arbre de mouvements pour un jeu ne peut être explorer pleinement pour des choses simples comme tic-tac-toe. D'autres jeux, comme les échecs, seront trop profonds et auront trop d'options à chaque mouvement (grand facteur de ramification).

Il existe des mesures pour lutter contre cette limitation, au niveau très général de votre question. Plus important encore, vous avez besoin d'une heuristique pour attribuer une valeur aux positions de jeu intermédiaires. Cela vous permet d'appliquer minimax même si l'analyse de tous les mouvements jusqu'à la fin du jeu n'est pas possible. Ces heuristiques peuvent être assez simples. Par exemple, dans les échecs, vous pouvez donner une valeur aux pièces (pion 1, chevalier 3, etc.) et simplement additionner. Vous pourriez le rendre un peu plus complexe compte tenu de la position au tableau et ainsi de suite, mais il y aura un compromis avec la performance ici. C'est la base de nombreux systèmes d'IA. Une amélioration classique est appelée alpha-beta pruning. Ceci est basé sur l'évaluation ordonnée des nœuds de l'arbre des mouvements, de sorte que les branches qui sont déjà garanties comme étant pires que d'autres peuvent être omises, ce qui améliore l'efficacité. (Considérez, par exemple, une branche où un joueur peut forcer un mouvement gagnant: les alternatives à ce mouvement dans cette branche ne sont pas importantes, puisque ce joueur forcera toujours le mouvement gagnant si le jeu va de cette façon).

D'autres algorithmes modifient la façon dont nous explorons l'arbre des mouvements. Monte-Carlo tree search est un exemple de ceci. L'idée de base ici est d'évaluer les nœuds et d'explorer l'arbre de manière coordonnée (par opposition à avant, où nous explorons d'abord l'arbre le plus profond possible et nous évaluons ensuite les feuilles). Nous avons ici un équilibre exploration-exploitation (vous devez décider si vous voulez développer des positions plus prometteuses, ou si vous voulez favoriser l'exploration de nouveaux mouvements, éventuellement décevants).