Des points et des boîtes algorithme de résolution de problèmes
Je suis actuellement en train de travailler sur un "des points et des boîtes" programme où l'entrée est générée automatiquement par un ordinateur, et notre production est ce que nous allons faire. Je vais être en compétition contre un autre joueur (leur algorithme).
Je suis représentant les points et les boîtes de conseil comme une matrice en Python. Gagner le jeu est une priorité: l'efficacité d'un algorithme n'est pas si important que cela.
Est-il meilleur, pas d'algorithme complexe pour automatiquement de déterminer ce que nous devrions faire, compte tenu d'un conseil?
P. S. - Vous n'avez pas besoin de me donner quelque chose dans le code si vous voulez...anglais algorithmes sont parfaitement acceptables.
Vous devez vous connecter pour publier un commentaire.
Ce jeu est jeu à somme zéro, donc, je vous suggère d'utiliser le min-max algorithme pour elle. Cet algorithme a été utilisé par d'un bleu profond pour gagner Kasparov aux échecs.
Créer votre fonction heuristique, qui évalue chaque état du jeu, et l'utiliser comme la fonction d'évaluation de min-max algorithme.
Vous pouvez également améliorer min-max en utilisant alpha-bêta prunning.
L'idée de min-max est de manière exhaustive la recherche à tous les coups possibles [jusqu'à une certaine profondeur d'habitude, puisque les états-vous besoin pour aller au-dessus est exponentielle en le nombre de profondeur], et a choisi le meilleur coup, en supposant que votre adversaire va également faire son meilleur mouvement possible.
p.s.
Ils sont fortement reliés entre eux, depuis le plus efficace de votre algorithme est, vous serez en mesure de vérifier les solutions possibles, afin de mieux la profondeur, et le plus de chances vous avez de gagner. Notez qu'avec un temps illimité, vous pouvez explorer toute l'arborescence du jeu et de venir avec une stratégie de réussite de chaque état de jeu. Cependant, en explorant l'ensemble du jeu-arbre est probablement irréaliste.
Je pense que minimax n'est pas le meilleur choix de l'algorithme de la stratégie dots-et-boîtes. Pour l'histoire complète sur ce jeu, vous avez vraiment besoin de lire le livre Les Points et les Boîtes de Jeu: Sophistiqué, un Jeu d'Enfant par Elwyn R. de Berlekamp, mais je vais vous donner un bref résumé ici.
De Berlekamp fait un certain nombre de puissants observations. La première est la double-croix de la stratégie, qui je suppose que vous connaissez (il est décrit dans le Page Wikipedia sur le jeu).
La seconde est la principe de parité pour de longues chaînes. Cela découle de trois faits sur la majorité des jeux joués:
en plus de la contrainte que le nombre de points de commencer avec, plus le nombre de double-croix, est égal au nombre de tours dans le jeu. Donc si il y a seize points pour commencer, et il y a un double-croix, il y aura dix-sept tours. (Et dans la majorité des jeux, ce qui signifie que le premier joueur qui gagne.)
Ce qui simplifie l'analyse de la mi-positions de jeu énormément. Prenons l'exemple de cette position avec 16 points et 11 coups joués (problème de 3.3 à partir de Berlekamp du livre). Quel est le meilleur coup ici?
Bien, si il y a deux longues chaînes, il y aura une double croix, le jeu prendra fin après six coups (16 + 1 = 11 + 6), et le joueur à aller de perdre. Mais si il y a une seule longue chaîne, il n'y aura pas de double croix et le jeu prendra fin après l'autre cinq mouvements (16 + 0 = 11 + 5) et le joueur de se déplacer va gagner. Alors, comment pouvez-le joueur à aller s'assurer qu'il n'est qu'une longue chaîne? Le seul coup gagnant sacrifices deux boîtes:
Minimax aurait trouvé ce mouvement, mais avec beaucoup plus de travail.
Le troisième et le plus puissant de l'observation, c'est que des points et des boîtes est un impartial jeu: les mouvements disponibles sont les mêmes, peu importe qui c'est le tour de jouer, et dans les postes typiques qui surviennent dans le cours du jeu (qui est, ceux contenant de longues chaînes de boîtes), c'est aussi un jeu: le dernier joueur à se déplacer gagne. La combinaison de ces propriétés signifie que les positions peuvent être analysés de manière statique à l'aide de Des rats Sprague–Grundy théorie.
Voici un exemple de la puissance de cette approche est, à l'aide de la figure 25, à partir de Berlekamp du livre.
Il y a 33 déplacement possible dans cette position, et bien joué le jeu dure environ 20 plus de coups, donc je serais surpris si il était possible pour les minimax pour compléter son analyse dans un délai raisonnable. Mais la poste a une long de la chaîne d' (la chaîne de six places dans la moitié supérieure) de sorte qu'il peut être analysé de manière statique. Le poste se divise en trois morceaux dont les valeurs sont nimbers:
Ces nimbers peut être calculée par la programmation dynamique en temps O(2n) pour un poste n coups restant, et vous aurez probablement envie de mettre en cache les résultats pour de nombreux petits postes de toute façon.
Nimbers ajouter à l'aide exclusive ou: *1 + *4 + *2 = *7. Donc, le seul coup gagnant (un mouvement qui réduit la nim-somme *0) est à changer *4 *3 (de sorte que les positions de la somme est *1 + *3 + *2 = *0). L'un des trois pointillée rouge se déplace d'est en train de gagner:
Édité à ajouter: je suis conscient que ce résumé ne fait pas vraiment constituer une algorithme en tant que tel, et laisse beaucoup de questions sans réponse. Pour certaines des réponses que vous pouvez lire de Berlekamp du livre. Mais il y a un peu à l'écart quand il s'agit de l'ouverture: la chaîne de comptage et de Sprague–Grundy théorie sont vraiment seulement pratique dans le milieu et fin de partie. Pour l'ouverture, vous aurez besoin d'essayer quelque chose de nouveau: si c'était moi, je serais tenté d'essayer Monte-Carlo tree search jusqu'au point où les chaînes peuvent être comptés. Cette technique a fait des merveilles pour le jeu de Go et peut-être productifs ici aussi.
Je pense que Gareth's réponse ci-dessus est excellente, mais juste à ajouter (je n'ai pas la réputation d'ajouter des commentaires) que des Points et des boîtes a été montré (au moins avec un croquis) pour être np-difficile selon cette: arxiv.org/pdf/cs/0106019v2.pdf
J'ai écrit une version javascript de points et de boîtes qui tente d'intégrer les stratégies mentionnées ci-dessus dotsandboxes.org. Ce n'est pas le meilleur disponible (qui n'a pas encore intégrer toutes les techniques que Gareth mentions) mais les graphismes sont sympas et il bat la plupart des humains et d'autres implémentations 🙂 n'hésitez pas à regarder le code et il y a d'autres liens à d'autres personnes de la version du jeu que vous pouvez vous entraîner à vous sur.