(Es gibt einige Herausforderungen, die die Verwendung der besten Strategie erfordern, aber hier tun wir es nicht. Selbst wenn Sie gewinnen können, dürfen Sie ein Unentschieden schließen.)

Herausforderung

Schreiben Sie ein Programm, das das Spiel Tic-Tac-Toe spielt. Es darf nicht verlieren (daher sollte es das Spiel entweder mit einem Unentschieden oder durch Gewinnen beenden).

Zulässige E / A-Methoden

1. Der Eingang kann die aktuelle Karte sein. Sie können davon ausgehen, dass alle vorherigen Züge des 2. Spielers von Ihrer Engine gespielt wurden.
2. Die Eingabe kann die Bewegung des ersten Spielers sein, und Ihre Funktion speichert, welche Bewegungen in der Vergangenheit stattgefunden haben. In diesem Fall wird die Funktion für jeden Zug mehrmals aufgerufen. oder die Funktion / Programm Eingabeaufforderung für mehrere Male.
3. Sie können einen zusätzlichen Input eingeben, der besagt, ob Sie der erste Spieler sind, oder zwei (möglicherweise verwandte) Funktionen schreiben, um das Problem des ersten Spielers und des zweiten Spielers zu lösen. Wenn Ihr Programm die Eingabemethode 2 (Mehrfachaufruf) verwenden muss, können Sie entscheiden, was beim ersten Aufruf übergeben wird.
4. Ausgang kann das Brett sein, nachdem Sie an der Reihe sind.
5. Die Ausgabe kann Ihr Zug sein.
6. Ein Zug kann als Zahlenpaar dargestellt werden (0-Indizierung oder 1-Indizierung), als Zahl im Bereich von 0 bis 8 oder als Zahl im Bereich von 1 bis 9.
7. Die Karte kann als 3 × 3-Array oder als Array der Länge 9 dargestellt werden. Selbst wenn die Sprache ein 0-Index-Array hat, können Sie 1-Index verwenden.
8. Die Zellen im Raster können 3 verschiedene Werte verwenden, um anzuzeigen X, Ound leer sein.

Gewinnkriterien

Kürzester Code in jeder Sprache gewinnen.

Befunge, 181 168 Bytes

>>4&5pp20555>>03>16p\::5g8%6p5v
 ^p5.:g605$_ #!<^_|#:-1g61+%8g<
543217539511|:_^#->#g0<>8+00p3+5%09638527419876
v<304p$_v#:->#$$:2`#3_:^
>#\3#13#<111v124236478689189378

Die Positionen auf dem Brett sind von 1 bis 9 nummeriert. Standardmäßig erhalten Sie den ersten Zug. Wenn Sie jedoch zulassen möchten, dass der Computer zuerst gestartet wird, können Sie für Ihren ersten Zug einfach 0 eingeben. Wenn Sie einen Zug ausgeführt haben, antwortet der Computer mit einer Nummer, die den Zug angibt.

Es gibt keine Überprüfungen, um sicherzustellen, dass Sie keinen gültigen Zug eingeben, und es gibt auch keine Überprüfungen, um festzustellen, ob jemand gewonnen oder verloren hat. Sobald keine Bewegungen mehr ausgeführt werden müssen, geht das Programm in eine Endlosschleife.

Es ist etwas schwierig, dies online zu testen, da es keine Online-Dolmetscher mit interaktiven Eingaben gibt. Wenn Sie jedoch im Voraus wissen, welche Schritte Sie ausführen werden (was voraussetzt, dass Sie wissen, wie der Computer reagieren wird), können Sie TIO-Tests mit diesen vorprogrammierten Schritten durchführen.

User spielt zuerst: Online ausprobieren!
Computer spielt zuerst: Probieren Sie es online!

Um es einfacher zu machen zu sehen, was los ist, habe ich auch eine Version, die das Board zwischen den Zügen ausgibt.

User spielt zuerst: Online ausprobieren!
Computer spielt zuerst: Probieren Sie es online!

Beachten Sie, dass Sie auf das Timeout von TIO warten müssen, bevor Sie die Ergebnisse sehen können.

Erläuterung

Die Karte wird im Befunge-Speicherbereich als flaches Array mit 9 Werten gespeichert, die von 1 bis 9 indiziert sind. Dadurch können wir die Nullpunktverschiebung als Sonderfall "keine Bewegung" verwenden, wenn wir den Computer zuerst spielen lassen möchten. Spielzüge werden als 4 und Computerbewegungen als 5 gespeichert. Zunächst werden alle Positionen auf 32 initialisiert (die Befunge-Speicher-Standardeinstellung). Wenn wir also auf das Board zugreifen, modifizieren wir mit 8, sodass wir entweder 0 oder 4 zurückerhalten oder 5.

In Anbetracht dieser Anordnung wissen wir, wenn wir die Werte von drei beliebigen Positionen auf dem Brett addieren, dass der Computer eine Bewegung vom Gewinnen entfernt ist, wenn die Summe 10 beträgt, der Spieler eine Bewegung vom Gewinnen entfernt ist, wenn die Summe 8 beträgt, und Die Positionen werden zwischen Computer und Spieler geteilt (es ist jedoch immer noch eine Position frei), wenn die Gesamtsumme 9 beträgt.

Unsere gesamte Strategie basiert auf diesem Konzept. Wir haben eine Routine, die eine Liste von Tripeln erstellt, die Sätze von drei Positionen auf dem Brett anzeigen. Wir berechnen die Summe dieser Positionen. Wenn die Summe einer bestimmten Summe entspricht, bewegt sich der Computer zu der Position, die im Satz frei ist.

Die Hauptliste der getesteten Tripel sind die Gewinnkombinationen (1/2/3, 1/5/9, 1/4/7 usw.). Wir suchen zuerst nach insgesamt 10 (der Computer ist im Begriff zu gewinnen) und dann nach insgesamt 8 (der Spieler ist im Begriff zu gewinnen und wir müssen diesen Zug blockieren). Weniger offensichtlich prüfen wir auch auf insgesamt 9 (wenn der Spieler und der Computer jeweils eine der Positionen haben, ist es eine gute Strategie, wenn der Computer die dritte Position einnimmt).

Vor diesem letzten Szenario besteht der andere strategische Schritt darin, alle Eckensätze (1/2/4, 2/3/6 usw.) sowie zwei gegenüberliegende Eckenkombinationen (1/8/9 und 3) zu überprüfen / 7/8). Wenn eine dieser Kombinationen 8 ergibt, dh der Spieler zwei der Positionen eingenommen hat, ist es eine gute Strategie für den Computer, die verbleibende freie Position einzunehmen.

Schließlich gibt es zwei Sonderfälle. Erstens versuchen wir immer, die Mittelposition einzunehmen, bevor wir uns bewegen. Dies wird mit der gleichen Routine wie bei allen anderen Zügen erreicht, nur mit einem Tripel, 5/5/5 und einer Zielsumme von 0. Wenn bei allen anderen Tests keine Bewegung gefunden wurde, versuchen wir, diese auszuführen eine der oberen Ecken als letztes Mittel. Dies wird wiederum einfach durch Testen der Tripel 1/1/1 und 3/3/3 mit einer Zielsumme von 0 erreicht.

Ich denke nicht, dass dies unbedingt eine perfekte Strategie ist - es kann Spiele geben, die der Computer unentschieden zieht und die möglicherweise gewonnen werden könnten -, aber es ist gut genug, um niemals ein Match zu verlieren. Ich habe ein Testskript ausgeführt, das versucht hat, alle möglichen Züge gegen den Computer zu spielen, und für jede gültige Folge von Zügen hat der Computer das Spiel entweder gewonnen oder unentschieden gespielt.

Python 2: 399 401 349 333 317 370 Bytes

2x Bugfix: Gutschrift auf l4m2

-52 Zeichen: Gutschrift für die U-Bahn

-16 Zeichen: Gutschrift an Jonathan Frech

-26 Zeichen: Gutschrift an User202729

def f(b):
 t=4,9,2,3,5,7,8,1,6;n=lambda k:[t[i]for i,j in enumerate(b)if j==k];p,o,a,I=n(2),n(1),n(0),t.index
 for i in p:
    for j in p:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in o:
    for j in o:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in 9,3,7,1:
    if i in a and 5 in p:return I(i)
 for i in 5,4,2,8,6:
    if i in a:return I(i)
 return I(a[0])

Probieren Sie es online!

Am ersten Tag eines Kurses in linearer Algebra, den ich im letzten Semester belegte, schlug mein scharfsinniger Dozent vor, wenn Sie die Tic-Tac-Toe-Tafel als Matrix darstellen:

4 | 9 | 2
--+---+--
3 | 5 | 7
--+---+--
8 | 1 | 6

Wenn Sie dann drei in einer Reihe haben, entspricht dies der Auswahl von drei Zahlen im Bereich [1,9], die sich zu 15 addieren. Diese Antwort nutzt diese Idee aus. Die Funktion erstellt eine Liste mit neun Nummern, die die Karte darstellen. 0 steht für ein leeres Feld, 1 ist vom Gegner besetzt und 2 steht für ein vorheriges Spiel des Programms. Die ersten 3 Zeilen geben an, welche Nummern das Programm ausgewählt hat (p), welche die Opposition ausgewählt hat (o) und welche noch verfügbar sind (a). Anschließend durchsucht es die verfügbaren Nummern und stellt fest, ob eine von ihnen, kombiniert mit zwei bereits ausgewählten Nummern, fünfzehn ergibt. Wenn dies der Fall ist, wird das Quadrat ausgewählt und gewonnen. Wenn es keine sofortigen Gewinnzüge gibt, wird geprüft, ob der Gegner mit der gleichen Methode gewinnen kann. Wenn sie können, wird es ihr Siegerquadrat nehmen. Wenn es weder einen Gewinnzug noch einen Blockzug gibt, es wird sich in einer Ecke bewegen. Dies verhindert, dass ein Idiot sich paart:

- - - 
- X -
- - -

- O -             # Bad Move
- X -
- - -

- O X
- X -
- - -

- O X
- X -
O - -

- O X
- X -
O - X

Wenn keine dieser Situationen eintritt, wird ein Quadrat willkürlich ausgewählt. Die Funktion gibt eine Zahl [0,8] aus, die das vom Algorithmus gewählte indizierte Quadrat 0 darstellt.

Bearbeiten: Der Algorithmus priorisiert jetzt das Zentrum über der Diagonale, wodurch verhindert wird, dass ein anderer Narr die Möglichkeit hat, mit l4m2 und verwandten Strategien zusammenzuarbeiten.

Edit: Zur Verdeutlichung nimmt die Funktion eine Tafel in Form eines Arrays auf und gibt einen Move als Integer auf [0,8] aus. Da diese E / A-Strategie so umständlich ist, finden Sie hier ein Wrapper-Skript, das die Interaktivität erhöht. Es wird ein einzelnes Befehlszeilenargument benötigt, das 1 sein sollte, wenn der Player an erster Stelle steht, und 0, wenn das Programm an erster Stelle steht.

import sys

def f(b):
 t=4,9,2,3,5,7,8,1,6;n=lambda k:[t[i]for i,j in enumerate(b)if j==k];p,o,a,I=n(2),n(1),n(0),t.index
 for i in p:
    for j in p:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in o:
    for j in o:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in 9,3,7,1:
    if i in a and 5 in p:return I(i)
     for i in 5,4,2,8,6:
        if i in a:return I(i)
 return I(a[0])

board = [0,0,0,0,0,0,0,0,0]
rep = {0:"-",1:"X",2:"O"}

turn = int(sys.argv[1])
while True:
    for i in range(3):
        print rep[board[i*3]]+" "+rep[board[i*3+1]]+" "+rep[board[i*3+2]]
        print
    if turn:
        move = int(raw_input("Enter Move [0-8]: "))
    else:
        move = f(board)
    board[move] = turn+1
    turn = (turn+1)%2