Tout le monde se rend compte que Tic Tac Toe est un jeu résolu. Cependant, la version Misère de only-Xs offre une alternative intéressante.

Dans cette version du jeu, les deux joueurs jouent des X sur le plateau et essaient d'éviter d'en faire trois d'affilée. Si vous souhaitez en savoir plus à ce sujet, Numberphile a une belle vidéo sur ce concept.

Étant donné une planche de Misère Crosses, jouez un coup optimal.

Un tableau est composé de trois lignes de trois caractères chacune, qui sont Xou . Donc:

X X
X  
 XX

est une planche valide. Vous pouvez le prendre dans n'importe quel format pratique, tant que vos entrées et sorties utilisent le même format. Les formats incluent (mais ne sont pas limités à): une chaîne de plusieurs lignes (avec un retour à la ligne facultatif); Un tableau 2D de caractères qui sont Xou ; un tableau aplati 1D de valeurs booléennes représentant si chaque position a été jouée.

Un coup optimal est celui qui garantit que vous gagnerez en continuant à jouer de manière optimale ou prolonge votre perte aussi longtemps que possible et est défini par les règles suivantes:

• Évitez d'en faire trois de suite.
• Si vous allez en premier, jouez au milieu.
• Si le seul espace occupé est le milieu, jouez dans l'un des espaces restants.
• Si la case du milieu n'est pas occupée et une case extérieure l'est, jouez en face du dernier jeu de votre adversaire.
• Si la case du milieu est occupée et une case extérieure l'est, jouez un "coup de chevalier" (en face, un de plus) loin d'un coup précédent qui ne vous fait pas perdre.
• S'il ne reste aucun carré où vous ne perdrez pas, jouez dans l'un des carrés restants.

[REMARQUE: cela s'est avéré non optimal dans un cas, mais vous devez quand même utiliser cet algorithme.]

Vous pouvez supposer que tous vos mouvements précédents étaient optimaux. Ainsi, le premier exemple de carte n'est pas une entrée valide. Les mouvements de votre adversaire peuvent être optimaux ou non.

Si le jeu est terminé (c.-à-d. Un trio consécutif a été effectué), le comportement n'est pas défini.

Comme il s'agit de code-golf , la réponse la plus courte en octets gagne!

Un chemin possible, utilisant uniquement des mouvements optimaux, est le suivant:

[   ]  [   ]  [X  ]  [X  ]  [X  ]  [X  ]  [XX ]
[   ]->[ X ]->[ X ]->[ XX]->[ XX]->[ XX]->[ XX]
[   ]  [   ]  [   ]  [   ]  [ X ]  [XX ]  [XX ]

Voici les entrées possibles provenant de l'adversaire utilisant des mouvements non optimaux:
(Notez que seules les cartes de gauche de cette liste sont des entrées valides.)

[X  ]  [X  ]
[   ]->[   ]
[   ]  [  X]

[XX ]  [XX ]
[   ]->[   ]
[  X]  [ XX]

[XX ]  [XX ]
[X  ]->[X X]
[ XX]  [ XX]

Ruby, Rev B 121 octets

La soumission est la fonction anonyme, moins la f=. Montré dans le programme de test pour illustrer l'utilisation.

f=->n{["~mK)\7","}uYwQO"][l=n%2].bytes{|t|9.times{|i|(m=n|1<<i)==n||8.times{|j|m/2*257>>j&255==126-t&&t+j%2!=119&&l=m}}}
l}

puts g=f[gets.to_i]
puts
[7,6,5,
 8,0,4,
 1,2,3].each{|i|print g>>i&1; puts if i/3==1}

2 octets économisés en faisant du carré central le bit le moins significatif au lieu du bit le plus significatif (supprimer par /2au lieu de %256.) Économies restantes par une réorganisation de la table des mouvements acceptables. L'organisation en carré central libre / occupé au lieu du nombre total de X permet un test plus simple. De plus, maintenant il n'y a que 2 chaînes dans le tableau, donc la %w{string1 string2}syntaxe est abandonnée au profit de la ["string1","string2"]syntaxe. Cela permet d'inclure un caractère non imprimable \7, ce qui permet à son tour d'utiliser un encodage plus simple: 126-tau lieu de (36-t)%120.

Ruby, Rev A 143 octets

->n{l=r=("%b"%n).sum%8
%w{$ %5 - I+Wy Q S#}[r].bytes{|t|9.times{|i|(m=n|1<<i)==n||8.times{|j|m%256*257>>j&255==(t-36)%120&&t+j%2!=43&&l=m}}}
l}

Il s'agit d'une fonction anonyme. Le format d'entrée / sortie a été laissé ouvert, j'ai donc opté pour un nombre binaire 9 bits. le bit de 512 représente le centre, avec les bits restants en spirale autour de lui (le bit de 1 est considéré comme un coin.)

Il y a beaucoup plus d'entrées possibles que de sorties acceptables, donc l'algorithme consiste à essayer tous les mouvements et à en trouver un qui correspond à un modèle de sortie acceptable. Les modèles de sortie acceptables pour chaque nombre de X sont codés en dur.

Les informations sur le carré central sont supprimées et les 8 bits restants sont multipliés par 257 pour les dupliquer. Ce modèle est ensuite tourné au-delà des modèles acceptables par déplacement de droits.

La boucle n'est pas quittée lorsqu'un motif est trouvé, donc le motif renvoyé sera le DERNIER motif acceptable trouvé. Pour cette raison, les modèles préférables (où il y a une préférence) viennent plus loin dans la liste.

Compte tenu de la stratégie de «déplacement des chevaliers», peu importe si un motif est tourné de 45 degrés ou non. La version non golfée suit la stratégie de déplacement des chevaliers et n'a donc pas besoin de faire la différence entre les carrés d'angle et les carrés de bord: trois de suite doivent être évités de toute façon.

Cependant, j'ai trouvé que ce n'est pas toujours la meilleure stratégie, car il y a l'astuce suivante. Si votre adversaire passe en premier et prend le centre, il devrait gagner. Mais lors de son deuxième mouvement, il fait l'erreur de vous permettre de faire un carré 2x2, vous devez le prendre, car cela vous permet de le forcer à faire trois de suite. Ceci est implémenté dans la version golfée. Un peu de code supplémentaire est nécessaire dans ce cas pour distinguer entre trois X dans un coin (forcer l'adversaire à perdre) et 3 X le long d'un bord (suicide immédiat.)

Non testé dans le programme de test

La version non golfée suit la logique exprimée dans la question.

Dans la version golfée, la table est légèrement modifiée [[0],[1,17],[9],[37,7,51,85],[45],[47,119]]pour implémenter le comportement légèrement différent pour le boîtier r=3. Il est ensuite compressé en ASCII imprimable (nécessitant un décodage (t-36)%120). Un peu de logique supplémentaire est nécessaire pour différencier entre trois X dans un coin et trois X le long d'un bord dans le cas de l'entrée de table 7:&&t+j%2!=43

f=->n{l=r=("%b"%n).sum%8                                      #convert input to text, take character checksum to count 1's(ASCII 49.) 
                                                              #0 is ASCII 48, so %8 removes unwanted checksum bloat of 48 per char.
                                                              #l must be initialised here for scoping reasons.
  [[0],[1,17],[9],[11,13,37,51,85],[45],[47,119]][r].each{|t| #according to r, find the list of acceptable perimeter bitmaps, and search for a solution.
    9.times{|i|(m=n|1<<i)==n||                                #OR 1<<i with input. if result == n, existing X overwritten, no good.
                                                              #ELSE new X is in vacant square, good. So.. 
      8.times{|j|m%256*257>>j&255==t&&l=m}}                   #%256 to strip off middle square. *257 to duplicate bitmap.
                                                              #rightshift, see if pattern matches t. If so, write to l
  }
l}                                                            #return l (the last acceptable solution found) as the answer.

#call function and pretty print output (not part of submission)
puts g=f[gets.to_i]
puts
[6,7,0,
 5,8,1,
4,3,2].each{|i|print g>>i&1; puts if i<3}

Sortie du programme de test

C'est ce qui se produit lorsque l'ordinateur se joue lui-même.

C: \ Users \ steve> ruby ​​tictac.rb
0
256

000
010
000

C: \ Users \ steve> ruby ​​tictac.rb
256
384

010
010
000

C: \ Users \ steve> ruby ​​tictac.rb
384
400

010
010
100

C: \ Users \ steve> ruby ​​tictac.rb
400
404

010
010
101

C: \ Users \ steve> ruby ​​tictac.rb
404
436

010
110
101

C: \ Users \ steve> ruby ​​tictac.rb
436
444

010
110
111

ANALYSE DE JEU JOUER D'ABORD

C'est en fait très simple et linéaire.

Lorsque vous jouez en premier, la case du milieu sera toujours la première case occupée.

r = 0

...  binary representation 0
.X.
...

r = 2

X..  binary representation 1001=9 
.XX
...

r = 4

X.. binary representation 101101=45
.XX
XX.

Il n'y a qu'une seule façon (jusqu'à la symétrie) d'avoir cinq X, y compris le carré du milieu sur le plateau sans que le jeu ne soit terminé. Il y a un X dans le carré du milieu, un sur chaque diagonale (à 90 degrés l'un de l'autre) et un sur chaque ligne médiane horizontale / verticale (à 90 degrés l'un de l'autre.) Comme un bord entier ne peut pas être occupé, ce qui précède est le seul arrangement possible. L'autre joueur doit perdre au prochain coup.

ANALYSE DE JEU JOUANT DEUXIÈME

Le jeu est assez différent selon que l'autre joueur choisit la case du milieu.

r = 1

carré du milieu occupé

.X. X..  binary representation 1 
.X. .X.
... ...

carré du milieu libre

X.. .X. binary representation 10001=17
... ...
..X .X.

r = 3

Carré du milieu occupé, si un autre joueur joue à côté de votre dernier X Jouer l'éloignement d'un chevalier comme ci-dessous est pris en charge dans la version non jouée

XX. .XX binary representation 1011=11 
.X. XX. or mirror image 1101=13
X.. ...

Cependant, ce qui précède n'est PAS le meilleur coup et n'est pas pris en charge dans la version golfée. Le meilleur coup est le suivant, forçant une victoire au tour suivant:

XX. binary representation 111=7.           XXX
XX. Only to be used where j is odd.        .X.
... Even j would look like image to right. ...

Carré central occupé, si un autre joueur joue à 90 ou 135 degrés par rapport à votre dernier X (éloignez le chevalier.)

X.X .X. binary representation 100101=37 
.X. .XX
.X. X..

Carré moyen gratuit

X.X .X. XX. binary representations:
... X.X ...    1010101=85 (first two)
X.X .X. .XX and 110011=51 (last one)

r = 5

carré du milieu occupé. Pour les raisons indiquées ci-dessus en r = 4, il y a quatre coups possibles, tous perdants. un seul est pris en charge: 101111 = 47.

carré du milieu libre. Il n'y a qu'une seule carte possible jusqu'à la symétrie, comme suit. L'autre joueur doit perdre au prochain coup, il n'est donc pas nécessaire de soutenir r> 5.

XX. binary representation 1110111=119
X.X
.XX