Jeux optimaux de Tic Tac Torus

31

Ce défi concerne le jeu Tic Tac Toe, mais il se joue sur un tore.

Comment jouer

Pour créer le plateau de jeu nécessaire, vous commencez avec un plateau de jeu Tic Tac Toe classique. Pliez-le d'abord dans un cylindre en joignant le bord gauche et le bord droit. Ensuite, pliez-le en tore en joignant le bord supérieur et le bord inférieur. Voici une visualisation simple d'un tel plateau de jeu avec quelques mouvements joués (compétences Sick Paint!).

Tic Tac Torus

Les règles du Tic Tac Toe sur un tore sont les mêmes que celles du Tic Tac Toe ordinaire. Chaque joueur place des X et des Os alternés. Le premier avec 3 mêmes symboles dans une rangée, une colonne ou un en diagonale l'emporte.

Puisqu'un tore est assez difficile à visualiser, nous projetons simplement le tableau sur un papier. Maintenant, nous pouvons jouer au jeu en tant que Tic Tac Toe régulier. La seule différence est que vous pouvez également gagner avec 3 mêmes symboles dans une diagonale brisée. Par exemple, le joueur 1 (X) remporte le plateau suivant. Vous pouvez le voir facilement en changeant un peu la vue sur le tore.

Le joueur 1 (X) gagne en raison de 3 X dans une diagonale brisée

Si vous êtes intéressé, vous pouvez jouer au Tic Tac Toe sur un Torus sur Torus Games . Il existe une version Windows, Mac et Android.

Jeux optimaux

Dans ce défi étaient intéressés par des jeux optimaux. Un jeu optimal est un jeu où les deux joueurs jouent une stratégie optimale. Sur un plateau régulier de Tic Tac Toe, les jeux optimaux se terminent toujours par un match nul. De façon fascinante sur un plateau tore, le premier joueur gagne toujours. En fait, un jeu sur un plateau torus ne peut jamais se terminer par un match nul (même si les joueurs ne jouent pas de manière optimale).

La stratégie optimale est vraiment simple:

  • Si vous pouvez gagner en plaçant votre symbole, faites-le.
  • Sinon, si votre adversaire a deux symboles dans une ligne / colonne / agonaliagonale, essayez de le bloquer. Sinon, faites ce que vous voulez.
  • Sinon, faites ce que vous voulez.

Chaque jeu optimal se compose exactement de 7 coups et ces mouvements peuvent être décrits de la manière suivante:

  1. Le joueur 1 place un X n'importe où sur le plateau (9 choix)
  2. Le joueur 2 place un O n'importe où sur le plateau (8 choix)
  3. Le joueur 1 place un X n'importe où sur le plateau (7 choix)
  4. Le coup du joueur 2 peut être forcé (1 choix), sinon, il place le O n'importe où (6 choix)
  5. Le coup du joueur 1 est forcé (1 choix)
  6. Le joueur 2 est pris dans une fourchette (le joueur 1 peut gagner de deux manières différentes), donc le joueur 2 doit bloquer le joueur 1 dans un sens (2 choix)
  7. Le joueur 1 place son dernier coup et gagne (1 choix)

Il y a 9 * 8 * 1 * 6 * 1 * 2 * 1 + 9 * 8 * 6 * 1 * 1 * 2 * 1 = 1728 différents jeux optimaux sur notre tableau projeté. Ici vous pouvez voir un jeu optimal typique:

Exemple d'un jeu optimal

Si nous étiquetons chaque cellule du plateau avec les chiffres 0-8, nous pouvons décrire ce jeu par les chiffres 3518207. D'abord un X est placé dans la cellule 3 (ligne du milieu, colonne de gauche), puis un O dans la cellule 5 (ligne du milieu, colonne de droite), puis un X dans la cellule 1 (ligne du haut, colonne du milieu), ...

En utilisant cette notation numérique, nous avons automatiquement généré une commande. Maintenant, nous pouvons trier tous les 1728 jeux optimaux et nous obtenons la liste:

Game 0000: 0123845
Game 0001: 0123854
Game 0002: 0124735
Game 0003: 0124753
Game 0004: 0125634
   ...
Game 0674: 3518207
   ...
Game 1000: 5167423
Game 1001: 5167432
Game 1002: 5168304
   ...
Game 1726: 8765034
Game 1727: 8765043

Défi

Cette liste fait partie de votre travail. Vous recevrez un numéro kentre 0 et 1727 et vous devrez retourner le kjeu en notation numérique de cette liste triée.

Écrivez une fonction ou un programme, qui reçoit le nombre k(entier) calcule le jeu correspondant. Vous pouvez lire l'entrée via STDIN, l'argument de ligne de commande, l'invite ou l'argument de fonction et imprimer le résultat (7 chiffres) dans un format lisible (par exemple 0123845ou [0, 1, 2, 3, 8, 4, 5]) ou le renvoyer en utilisant une chaîne (format lisible par l'homme) ou un entier (contenant tous chiffres en base 10), ou dans n'importe quel format de tableau / liste.

Le type de défi est le code-golf. Par conséquent, le code le plus court l'emporte.

Jakube
la source
Pourquoi le premier coup du joueur 2 doit-il être dans la même ligne ou colonne que le premier coup du joueur 1? J'ai joué quelques matchs dans ma tête où le premier coup du joueur 2 se trouve dans l'une des mêmes diagonales et ils suivent le même schéma de jeu optimal. Il me semble que l'un des aspects de la carte toroïdale est que les lignes, les colonnes et les diagonales ont des effets symétriques sur le jeu.
Runer112
@ Runer112 Simplifie beaucoup la stratégie optimale. La seule règle maintenant est de bloquer votre adversaire si vous le pouvez, sinon faites ce que vous voulez.
Jakube
7
Juste un petit commentaire: en fait, il y a beaucoup moins de jeux uniques possibles ici. La symétrie translationnelle rend la position du premier mouvement non pertinente (car vous pouvez toujours centrer votre vue), donc divisez par 9 ... et la rotation de la planche ne fait que 2 seconds mouvements différents (diagonale ou carré adjacent) ... donc à la plupart des 48 jeux distincts. Si vous prenez en compte la symétrie de réflexion, elle descend encore plus loin. Cette version torus est beaucoup plus ennuyeuse que la version régulière. Golf loin.
orion
@orion En fait, le fait que le tore s'enroule, ne nous interdit pas de penser à "0" comme le "premier" rect sur le tableau du tore et de distinguer les neuf champs en général ... Pourtant, nous sommes d'accord sur le fait que le "méridien 0" soit à Greenwich , alors qu'à l'opposé de la Terre nous pouvons être une jambe en place où c'est jeudi, une jambe en place c'est mercredi (différence de 24h en heure locale!) - et tout cela malgré le fait que la Terre est ronde et n'a pas un "point de départ" ...
pawel.boczarski
@Rodney Nope, c'est un, pas un sept. Essayez de le calculer.
Jakube

Réponses:

6

JavaScript (ES6), 266 308 317 334 341

Une fonction renvoyant une chaîne. Edit Trouvé une solution arithmétique pour la fonction M (enfin!)

F=(n,x=[],M=(a,b,t=-a-b)=>(a-b)%3?a<3&b<3?3+t:a>5&b>5?21+t:12+t:9+t+a%3*3)=>
[for(a of z='012345678')for(b of z)for(c of z)for(d of z) 
a-b&&c-a&&c-b&&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c)&&(
f=M(c,e=M(b,d)),g=M(a,e),g<f?[f,g]=[g,f]:0,r=a+b+c+d+e,x.push(r+f+g,r+g+f))]
&&x[n]

Très naïf , il peut être raccourci de plusieurs façons . Il énumère simplement toutes les valeurs légales possibles et renvoie ce qui se trouve à la place n. La fonction M renvoie la position entre deux cellules, c'est le mouvement obligatoire pour bloquer un joueur opposé.

Plus lisible

F=(n,x=[],
  M=(a,b,t=-a-b)=>(a-b)%3? 
     a<3&b<3?
       3+t // first row
       :a>5&b>5?
          21+t // last row
          :12+t // middle row and diags
     :9+t+a%3*3 // columns
  )=>
  [for(a of z='012345678') // enumerate the first 4 moves
     for(b of z)
       for(c of z)
         for(d of z) 
           a-b&&c-a&&c-b // avoid duplicates
           &&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c) // and check if d must block a-c or it's free
           &&(
             e=M(b,d), // forced to block b-d
             f=M(c,e),g=M(a,e),g<f?[f,g]=[g,f]:0, // f and g could be in the wrong order
             r=a+b+c+d+e, // start building a return string
             x.push(r+f+g,r+g+f) // store all values in x
  )]&&x[n] // return value at requested position
edc65
la source
3

Octave, 467 369 363 309 297 caractères

297:

global t=0*(1:9)m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48 a;
function g(s,p)global a t m;
if nnz(s)<8&&any((t==1)*m>2)a=[a;s];return;end;q=t==3-p;
(r=sort(~q.*(1:9)*m(:,find([3 1]*([q;t==p]*m)==6)')))||(r=find(~t));
for i=r t(i)=p;g([s i+47],3-p);t(i)=0;end;end;g('',1);f=@(n)a(n+1,:);

Le seul changement pertinent est que nous ne vérifions jamais si le joueur actuel peut gagner, mais seulement la possibilité de l'adversaire de gagner le tour suivant . Comme le seul tour que le joueur 1 peut gagner est le tour 7 , c'est le seul endroit où l'algorithme produirait un jeu qui n'est pas optimal, mais il est très facile de filtrer une telle situation. Nous vérifions simplement chaque jeu généré s'il est gagné par le joueur 1 - si ce n'est pas le cas, le mouvement au tour 7 était incorrect, donc nous n'ajoutons pas ce jeu à la table de jeux optimale.

(Exactement la moitié des parties générées par cette règle sont fausses, c'est-à-dire qu'au 7ème tour le joueur 1 a toujours deux possibilités de bloquer le joueur deux, mais une seule le fera gagner instantanément).

Utilisation:

$ octave
octave:1>> source script.m
octave:2>> f(634)
ans = 3270148

Le code non golfé ressemble à:

 global t=0*(1:9);
 global m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48;
 global allgames;
 allgames=[];

 function r=canbewon(by)
  global t m
  q=[t==by;t==(3-by)]*m;
  g=(find([3 1]*q==6))';
  r=sort((~(t==by).*(1:9)) * m(:,g));
 end

 function games_starting_with(s)
 global allgames t;
 if 7==numel(s) && any((t==1)*m==3) # it's 7th move and first player won
  allgames=[allgames;s];
  return;
 end;
 poss=(find(~t));                  # for now all free slots are possible
 player=1+mod(numel(s),2);
 moves = canbewon(3-player);
 if numel(moves) poss=moves; end;  # ... no, we must block the other player
 for i=poss
  t(i)=player;
  games_starting_with([s char(i+47)]);
  t(i)=0;
 end
end

games_starting_with('');
f=@(n)(allgames(n+1,:));
pawel.boczarski
la source
1
petit conseil: vous pouvez supprimer les anciennes versions si elles utilisent la même logique car elles sont stockées dans l'historique des modifications afin qu'elles soient toujours disponibles
masterX244