Jeder erkennt, dass Tic Tac Toe ein gelöstes Spiel ist. Die Misère-Version von only-Xs bietet jedoch eine interessante Alternative.

In dieser Version des Spiels spielen beide Spieler Xs auf dem Brett und versuchen zu vermeiden, drei in einer Reihe zu machen. Wenn Sie mehr darüber erfahren möchten, hat Numberphile ein schönes Video zu diesem Konzept.

Spielen Sie mit einem Brett aus Misère Crosses einen optimalen Zug.

Eine Tafel besteht aus drei Zeilen mit jeweils drei Zeichen, die Xoder sind . Somit:

X X
X  
 XX

ist eine gültige Tafel. Sie können dies in jedem geeigneten Format verwenden, solange Ihre Eingabe und Ausgabe dasselbe Format verwenden. Zu den Formaten gehören (ohne darauf beschränkt zu sein): Eine mehrzeilige Zeichenfolge (mit optionalem nachgestellten Zeilenumbruch); Ein 2D-Array von Zeichen, die Xoder sind ; Ein 1D-abgeflachtes Array von Booleschen Werten, das angibt, ob jede Position gespielt wurde.

Ein optimaler Zug garantiert Ihnen, dass Sie gewinnen, indem Sie weiter optimal spielen, oder verlängert Ihren Verlust so lange wie möglich und wird durch die folgenden Regeln definiert:

• Vermeiden Sie es, drei in einer Reihe zu machen.
• Wenn Sie zuerst gehen, spielen Sie in der Mitte.
• Wenn das einzige belegte Feld das mittlere ist, spielen Sie in einem der verbleibenden Felder.
• Wenn das mittlere Feld nicht besetzt ist und ein äußeres Feld besetzt ist, spielen Sie gegenüber dem letzten Spiel Ihres Gegners.
• Wenn das mittlere Feld besetzt ist und ein äußeres Quadrat besetzt ist, spielen Sie einen "Ritterzug" (gegenüber, einen darüber) weg von einem vorherigen Zug, bei dem Sie nicht verlieren.
• Wenn keine verbleibenden Felder mehr vorhanden sind, auf denen Sie nicht verlieren, spielen Sie auf einem der verbleibenden Felder.

[HINWEIS: Dies hat sich in einem Fall als nicht optimal erwiesen, aber Sie sollten diesen Algorithmus trotzdem verwenden.]

Sie können davon ausgehen, dass alle Ihre vorherigen Züge optimal waren. Somit ist die erste Beispielkarte keine gültige Eingabe. Die Bewegungen Ihres Gegners können optimal sein oder auch nicht.

Wenn das Spiel beendet ist (dh eine Drei in einer Reihe gemacht wurde), ist das Verhalten undefiniert.

Da dies Code-Golf ist , gewinnt die kürzeste Antwort in Bytes!

Ein möglicher Weg, bei dem nur optimale Bewegungen verwendet werden, ist folgender:

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

Hier sind mögliche Eingaben, die vom Gegner mit nicht optimalen Zügen stammen:
(Beachten Sie, dass nur die linken Bretter in dieser Liste gültige Eingaben sind.)

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

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

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

Ruby, Rev B 121 Bytes

Die Übermittlung ist die anonyme Funktion abzüglich der f=. Wird im Testprogramm angezeigt, um die Verwendung zu veranschaulichen.

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 Bytes werden eingespart, indem das mittlere Quadrat zum niedrigstwertigen Bit anstelle des höchstwertigen Bits gemacht wird (Entfernen durch /2statt %256.). Verbleibende Einsparungen durch eine Neuorganisation der Tabelle akzeptabler Züge. Das Organisieren als freies / besetztes zentrales Quadrat anstelle der Gesamtzahl der X ermöglicht einen einfacheren Test. Außerdem enthält das Array jetzt nur noch 2 Zeichenfolgen, sodass die %w{string1 string2}Syntax zugunsten der ["string1","string2"]Syntax aufgegeben wird . Dies ermöglicht das Einfügen eines nicht druckbaren Zeichens \7, wodurch wiederum eine einfachere Codierung verwendet werden kann: 126-tanstelle von (36-t)%120.

Ruby, Rev. A 143 Bytes

->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}

Dies ist eine anonyme Funktion. Das Eingabe- / Ausgabeformat wurde offen gelassen, daher habe ich mich für eine 9-Bit-Binärzahl entschieden. Das Bit des 512 stellt die Mitte dar, wobei die verbleibenden Bits sich spiralförmig darum drehen (das Bit der 1 wird als Ecke betrachtet.)

Es gibt weit mehr mögliche Eingaben als akzeptable Ausgaben. Der Algorithmus besteht also darin, alle Bewegungen auszuprobieren und eine zu finden, die zu einem akzeptablen Ausgabemuster passt. Die akzeptablen Ausgabemuster für jede Anzahl von X sind fest codiert.

Die Informationen über das mittlere Quadrat werden entfernt und die verbleibenden 8 Bits werden mit 257 multipliziert, um sie zu duplizieren. Dieses Muster wird dann durch Rechtsverschiebung über die akzeptablen Muster hinaus gedreht.

Die Schleife wird nicht verlassen, wenn ein Muster gefunden wird, sodass das zurückgegebene Muster das LETZTE akzeptable gefundene Muster ist. Aus diesem Grund werden bevorzugte Muster (wo es eine Präferenz gibt) später in der Liste aufgeführt.

Angesichts der Strategie „Ritter bewegen“ ist es von geringer Bedeutung, ob ein Muster um 45 Grad gedreht wird oder nicht. Die ungolfed Version folgt der Ritterbewegungsstrategie und muss daher nicht zwischen Eck- und Randquadraten unterscheiden: Drei in einer Reihe sind sowieso zu vermeiden.

Ich fand jedoch, dass dies nicht immer die beste Strategie ist, da es den folgenden Trick gibt. Wenn Ihr Gegner zuerst geht und die Mitte einnimmt, sollte er gewinnen. Aber bei seinem zweiten Zug macht er den Fehler, dass Sie ein 2x2-Quadrat machen dürfen, das Sie nehmen sollten, da Sie ihn so zwingen können, drei in einer Reihe zu machen. Dies ist in der Golfversion implementiert. In diesem Fall wird ein kleiner zusätzlicher Code benötigt, um zwischen drei X in einer Ecke (Gegner zum Verlieren zwingen) und drei X entlang einer Kante (sofortiger Selbstmord) zu unterscheiden.

Ungolfed im Testprogramm

Die ungolfed Version folgt der in der Frage ausgedrückten Logik.

In der Golfversion wird der Tisch leicht modifiziert [[0],[1,17],[9],[37,7,51,85],[45],[47,119]], um das etwas andere Verhalten für den Fall zu implementieren r=3. Es wird dann auf druckbares ASCII komprimiert (Dekodierung erforderlich (t-36)%120). Ein zusätzliches Stück Logik ist erforderlich, um im Fall des Tabelleneintrags 7 zwischen drei X in einer Ecke und drei X entlang einer Kante zu unterscheiden:&&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}

Ausgabe des Testprogramms

Dies passiert, wenn der Computer selbst spielt.

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

SPIELANALYSE, DIE ZUERST SPIELT

Dies ist eigentlich sehr einfach und linear.

Wenn Sie zuerst spielen, ist das mittlere Feld immer das erste belegte Feld.

r = 0

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

r = 2

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

r = 4

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

Es gibt nur einen Weg (bis zur Symmetrie), fünf X einschließlich des mittleren Quadrats auf dem Brett zu haben, ohne dass das Spiel beendet ist. Im mittleren Quadrat befindet sich ein X, eines auf jeder Diagonale (in einem Winkel von 90 Grad zueinander) und eines auf jeder horizontalen / vertikalen Mittellinie (in einem Winkel von 90 Grad zueinander). Da eine ganze Kante nicht belegt werden kann, ist das Obige das einzige Anordnung möglich. Ein anderer Spieler muss beim nächsten Zug verlieren.

SPIELANALYSE ZWEITES SPIELEN

Das Spiel ist ganz anders, je nachdem, ob der andere Spieler das mittlere Feld wählt.

r = 1

mittlerer Platz besetzt

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

mittleres Quadrat frei

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

r = 3

Mittleres Feld besetzt, wenn ein anderer Spieler neben Ihrem letzten X spielt. In der ungolfed-Version wird es unterstützt, wenn ein Ritter wie unten entfernt ist

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

Das Obige ist jedoch NICHT der beste Zug und wird in der Golfversion nicht unterstützt. Der beste Zug ist wie folgt und erzwingt einen Sieg in der nächsten Runde:

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

Mittleres Feld besetzt, wenn ein anderer Spieler bei 90 oder 135 Grad bis zu Ihrem letzten X spielt (spielen Sie den Ritterzug weg.)

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

Mittleres Quadrat frei

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

r = 5

mittlerer Platz besetzt. Aus den oben in r = 4 genannten Gründen gibt es vier mögliche Züge, die alle verlieren. Es wird nur eine unterstützt: 101111 = 47.

mittleres Quadrat frei. Es gibt nur eine mögliche Platine bis zur Symmetrie, wie folgt. Ein anderer Spieler muss beim nächsten Zug verlieren, sodass r> 5 nicht unterstützt werden muss.

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