Tout le monde connaît le jeu tic-tac-toe 3x3. Avec le jeu correct, le premier coup de croix entraîne un nul. Vous pouvez créer manuellement un arbre de mouvements, où pour tout mouvement de zéros, il y a un mouvement de croix, ce qui conduit au meilleur résultat (pour les croix), c'est-à-dire à un match nul ou à une victoire. Cet arbre de mouvements épuise toutes les options, alors ils disent que le jeu est «résolu». Il existe une variété tridimensionnelle de tic-tac-toe 4x4x4 pour laquelle la réponse à la question de savoir qui va gagner le premier coup des tic tacs n'est pas évidente. De plus, la question se pose de savoir s'il est possible de construire un tel arbre minimal qui résoudra ce problème.
La réponse à cette question est sous la coupe.
Permettez-moi de vous rappeler ce qu'est le jeu tic-tac-toe 4x4x4 (il est aussi appelé Qubic).
Il s'agit d'un cube composé de 64 champs dans lesquels pour gagner, vous devez mettre 4 croix ou zéros consécutifs, et ils peuvent suivre n'importe quelle ligne, y compris les diagonales principales. Au total, il existe 76 lignes de ce type - 48 contours et verticales, 24 diagonales et 4 diagonales principales. Compte tenu de cela, on peut noter que tous les champs ne sont pas identiques: il y a 8 champs angulaires et 8 champs centraux qui contrôlent 7 lignes et 48 autres champs qui contrôlent 4 lignes. Par conséquent, il est logique d'essayer de prendre des positions qui contrôlent plus de lignes.
Quelle est la difficulté de construire un arbre de décision pour ce jeu? On peut en gros estimer 2 à 64 options, ce qui est beaucoup. Bien sûr, toutes ces options ne sont pas implémentées dans le jeu et de nombreuses branches de l'arbre sont coupées assez rapidement, mais même dans ce cas, la construction d'un tel arbre par simple énumération n'est pas possible. Comment pouvons-nous réduire la recherche afin de résoudre ce problème? Vous pouvez remarquer qu'après plusieurs mouvements de croix et de zéros, une situation peut survenir dans laquelle il est possible de créer une menace pour l'ennemi en mettant trois croix ou zéros sur une même ligne. Avec une telle menace, l'ennemi est obligé de faire son prochain mouvement vers l'espace vide restant dans cette ligne, sinon il perdra au prochain mouvement. De tels mouvements avec une menace peuvent être effectués plusieurs fois de suite, s'il y a un nombre suffisant de lignes sur lesquelles il n'y a que deux croix ou, respectivement, un zéro. Si une telle chaîne de mouvements conduit à une situation dans laquelle il y a deux lignes avec trois croix ou zéros, alors le joueur correspondant perd. C'est ce qu'on appelle une victoire forcée.
Nous numérotons tous les champs avec des nombres de 0 à 63 en commençant par la face supérieure et en allant avec des lignes horizontales de gauche à droite.
Nous illustrons cela avec un exemple d'un jeu:
0-3-60-21-15-51-12-63 4x8x5x10x20x40x28x44x24x16x36x52x48
Ici, les croix font le premier pas vers le coin le plus à gauche sur la face supérieure (0), puis les zéros répondent au coin le plus à droite sur la même face (3). Les croix vont dans le coin proche gauche sur le bord inférieur (60), les zéros correspondent dans le champ au deuxième à partir du bord supérieur, etc. Après le mouvement des orteils en 63, les croix commencent une séquence de mouvements forcés: 4 - check. Le tac-toe est obligé de répondre à 8, la croix est à 5 check, le tac-toe est répondu à 10, etc. jusqu'à ce que deux lignes avec trois croix se forment aux croix. Tac toe perdu.
Pour résoudre ce jeu, vous devez trouver de telles séquences pour tous les mouvements possibles du tac toe. Pour une solution optimale, ces séquences doivent être minimales.
Excursion historique
Patashnik a été le premier à résoudre ce jeu au début des années 80. Il a sélectionné manuellement les combinaisons initiales, puis a recherché un coup gagnant à l'aide d'un ordinateur. Il a montré que si les croix vont dans le coin, elles gagnent toujours avec le bon jeu. La prochaine étape a été prise par Victor Allis. Dans sa thèse du milieu des années 90, il a montré qu'une solution peut être obtenue entièrement sur ordinateur. Cependant, il n'a pas vérifié toutes les options que les croix peuvent gagner, mais seulement les dix premières, les plus prometteuses. Par conséquent, sa solution n'était pas optimale et il a laissé cette tâche à d'autres chercheurs.
J'ai décidé de résoudre ce problème de manière optimale, c'est-à-dire de trouver un arbre minimal. Évidemment, pour cela, il est nécessaire d'utiliser la recherche en largeur d'abord, par opposition à la recherche en profondeur Allis. Tout d'abord, la recherche de gains forcés pour une situation arbitraire a été mise en œuvre. Cependant, il s'est avéré que cela s'est avéré plutôt lent, car la recherche approfondie du gain forcé pour les longues combinaisons est assez coûteuse. La solution a été trouvée en ajoutant un référentiel d'options déjà calculées dans std :: unordered_set. Il vaut la peine de dire que le terrain de jeu a été encodé sous la forme de deux variables de 64 bits, une pour les croix, une pour les zéros, où 1 signifie la présence d'une croix ou d'un zéro dans le champ correspondant. Cette mise en cache a fourni une accélération significative. Cependant, le principal problème était une recherche en premier lieu de mouvements non forcés. Dans une recherche normale sans optimisation, le calcul ne s'est pas terminé dans un délai raisonnable.
J'ai dû me tourner à nouveau vers la mise en cache. Un autre octet a été ajouté au champ de jeu calculé avec le résultat du calcul du sous-arbre pour cette option d'arrangement de tic tac toe. Dans le même temps, le codage du terrain de jeu a commencé à occuper 17 octets. Ainsi, lors de la recherche en largeur et en augmentant progressivement la profondeur d'un arbre, des sous-arbres déjà calculés pourraient être supprimés. Avec cela, j'ai pu calculer les arbres minimum
pour le premier mouvement de la croix vers le coin (cellule 0) et les réponses des zéros à tous les champs qui contrôlent en quatre lignes.
Des difficultés ont surgi si le tac toe a pris le terrain qui contrôlait sept lignes lors du premier mouvement de représailles. Dans ce cas, le cache occupé par le cache dépassait 32 gigaoctets de RAM et mon Linux est passé à un échange. Il fallait chercher une autre solution.
Ensuite, je suis passé au fait que le terrain de jeu a de nombreux automorphismes, c'est-à-dire que si vous trouvez une solution pour une combinaison de croix et de zéros, alors les combinaisons correspondant à différentes rotations et réflexions auront également une solution. Il est à noter que grâce à ces automorphismes, le premier mouvement des croix n'a que deux options - une dans le champ 0 (contrôlant 7 lignes) et une dans le champ 1 (contrôlant 4 lignes). Par conséquent, dans mon cas, le premier mouvement que les croix font toujours dans le champ 0. Mais cela n'est vrai que pour un champ vide.
Nous revenons cependant aux automorphismes pour un terrain de jeu arbitraire. Comment les trouver tous?
J'ai utilisé la méthode suivante: comme le cube a trois dimensions, vous pouvez réorganiser les coordonnées (il y aura 6 permutations) et faire des réflexions (il y en aura 8). Par conséquent, il y aura au total 48 automorphismes spatiaux, mais le cube possède deux autres automorphismes internes. On permute les coordonnées des champs dans les première et deuxième paires de chaque ligne,
et le second laisse le premier et le dernier champ en place et réorganise uniquement les coordonnées des deuxième et troisième champs. Ces deux automorphismes peuvent également être appliqués simultanément. Ainsi, pour chacun des 48 automorphismes spatiaux, il y a quatre
(y compris les automorphismes internes triviaux). Sinon, pour tout le cube, il y a 192 automorphismes. Cela laisse espérer une réduction significative du nombre de champs déjà calculés.
Cependant, un autre problème se pose ici: si vous vérifiez les 192 automorphismes, vous devez transformer rapidement le terrain de jeu en échangeant des bits. Si cette transformation n'est pas effectuée rapidement, elle y ira tout le temps, il n'y aura pas de gain de productivité et toute l'entreprise d'automorphismes s'envolera dans le tuyau. J'ai donc commencé à chercher sur Internet un moyen rapide d'échanger des bits. Pour être honnête, je n'ai rien trouvé de convenable. Le seul moyen rapide et acceptable de réorganiser les bits consiste à précompiler la table et à y sélectionner une solution toute prête ayant le terrain de jeu actuel comme index. Pour moi, cette méthode ne convenait pas, car il fallait avoir un tableau de 2 à la puissance de 64 mots de soixante bits.
Je voulais déjà vraiment laisser cette idée, cependant, l'idée m'est venue à l'esprit qu'il n'est pas nécessaire d'avoir une grande table, mais vous pouvez en avoir plusieurs petites. En principe, il était possible de choisir un nombre différent de telles tables, mais je me suis installé sur 8 tables de 256 mots (pour chaque automorphisme). Ainsi, pour échanger des bits, je prends un octet dans un champ de 64 bits et, dans un tableau pré-calculé, je sélectionne un modèle où les bits sont déjà en place (à moins, bien sûr, qu'ils soient nuls dans le champ source). Ensuite, je prends l'octet suivant du champ 64 bits et dans le prochain tableau pré-calculé, je sélectionne un autre modèle et fais un «ou» logique avec le premier. Et donc 8 fois. Étant donné que ces opérations ne contiennent pas de sauts conditionnels, elles doivent être effectuées assez rapidement sans violer le pipeline dans le processeur.
Tout cela semble assez bien, cependant, pour coder tous ces automorphismes et permutations rapides de bits manuellement et sans erreurs est assez problématique. Par conséquent, un programme supplémentaire a été créé qui génère du code C, qui, à son tour,
inclus dans le programme principal.
Conclusion et évolution ultérieure
Après avoir créé le programme ci-dessus, il est devenu possible en quelques jours de trouver un arbre presque optimal pour jouer au tic-tac-toe 4x4x4. Pourquoi est-ce "presque optimal"? Parce que la longueur totale des mouvements forcés n'est pas prise en compte et il peut arriver qu'il y ait un arbre pour les mouvements non forcés de la même profondeur, mais avec une profondeur totale plus petite des mouvements forcés. Mais je pense que ce n'est pas un très gros inconvénient.
Ainsi, le jeu de tic-tac-toe 4x4x4 est complètement calculé, les croix gagnent toujours et vous pouvez clore ce sujet? Pas vraiment. Le fait est que puisque les croix passent en premier, elles ont un avantage. Et si vous essayez de compenser cet avantage d'une manière ou d'une autre? Je propose l'idée suivante - interdire aux croix de mettre la croix dans le champ qui contrôle 7 lignes au premier coup, en les restreignant aux champs ne contrôlant que 4 lignes. Malgré le fait que cela semble être un petit changement, en fait, le résultat du jeu peut changer considérablement et les zéros pourront réduire le jeu à un match nul, ou peut-être gagner. Donc, il y a quelque chose à explorer.