Was ist dein nächster Schritt?

18

Diese Herausforderung besteht darin, eine Minimax-Funktion in einer Sprache Ihrer Wahl zu schreiben , um den nächstbesten Zug in einem NxN - Tic-Tac-Toe- Spiel unter Berücksichtigung des aktuellen Board-Status auszugeben . Der Board-Eingang kann als Matrix, 2D-Sammlung oder alles andere akzeptiert werden , was für Sie sinnvoll ist, sich aber an die Regeln hält . Die Ausgabe ist der nächstbeste Zug für jeden, der gerade an der Reihe ist , wobei davon ausgegangen wird , dass X begonnen hat .

Schneller Hintergrund zum Minimax-Algorithmus

Die Grundidee des Minimax-Algorithmus besteht darin, alle möglichen Ergebnisse als DAG aufzulisten und sie dann mit dem Vorteil zu gewichten, den die Zugfolge für den Spieler hat, der durch den ersten Zug eingegeben wird. Alle möglichen Ergebnisse werden dann beim ersten Zug "gezählt" und auf der Grundlage der Summe aller Ergebnisse bewertet (-1 für einen Verlust, 0 für ein Unentschieden und 1 für einen Sieg). In Implementierungen, bei denen mehrere Spieler spielen müssen, listen Sie alle möglichen Züge des Spielers und alle möglichen Antworten des Gegners auf. Zum Beispiel gibt es in einem Tic-Tac-Toe-Spiel (nach dem ersten Zug) 8 mögliche erste Züge, die Sie ausführen können, und alle scheinen gleich zu sein, wenn Sie nur den nächsten Zug analysieren. Indem Sie jedoch alle möglichen Ergebnisse für jede mögliche Gruppe von Zügen durchlaufen, die zu einem endgültigen Ergebnis führen, und sie alle zusammenfassen,

Weitere Informationen zu dem Mini-Max-Algorithmus in Bezug auf Tic-Tac-Toe finden Sie hier: http://neverstopbuilding.com/minimax

XKCD (nur 3x3-Lösung)

Alle möglichen Züge für ein 3x3-Tic-Tac-Toe-Spiel.

Die Regeln

  • Es kann jede Sprache verwendet werden, es sind jedoch keine externen Minimax-Bibliotheken zulässig.
  • Die Ausgabe kann eine Koordinate (0-n, 0-n) oder eine Zahl (1-n * n) sein, die den besten nächsten Zug angibt.
    • Darüber hinaus müssen Sie in der Lage sein, zu identifizieren, wann das beste Szenario ein Verlust oder ein Unentschieden anstelle eines Gewinns ist.
    • Die Art und Weise, wie Sie einen Verlust oder ein Unentschieden bezeichnen, liegt wiederum bei Ihnen.
  • Die Eingabe muss das herkömmliche X und O verwenden, und Sie müssen davon ausgehen, dass X zuerst verschoben wird. Leerzeichen können durch alles dargestellt werden.
  • Sie können davon ausgehen, dass alle Eingänge in Ihrem Programm n O und n + 1 X haben. Mit anderen Worten, Sie können davon ausgehen, dass Sie eine wohlgeformte Karte haben.
  • Der aktuelle Status der Karte muss die einzige Eingabe für Ihr Programm sein. Wenn Sie eine Rekursion verwenden, müssen Hilfsmethoden erstellt werden, um die Eingabeanforderungen zu vereinfachen. Weitere Informationen finden Sie unter /codegolf//a/92851/59376 .
  • Jeder Wert von 10> = n> = 1 muss unterstützt werden. Wenn Ihr Programm für n> 10 "abläuft", finde ich dies auch akzeptabel, da einige Sprachen eine erheblich geringere Verarbeitungsleistung haben (insbesondere bei Verwendung von mit dem Web verbundenen Konsolen).

Beurteilen

  • Dies ist Code-Golf, daher gewinnt die niedrigste Byte-Anzahl des Programms, und Standard-Lücken sind allgemein nicht zulässig.
  • Bei einem Gleichstand gewinnt das Programm, das das größte 'n' unterstützt.

Beispieleingaben

2x2

[[X,O]
 [-,-]]

Ausgabe: 2 oder [0,1] (3 oder [1,1] wären wohl auch richtig) (Irgendeine Form der Angabe des Ortes, willkürlich, solange Sie das von Ihnen verwendete Format leicht erklären können)


3x3

[[X,O,X]
 [O,X,-]
 [-,-,-]]

Ausgabe: -1 (Verlust)


Auch hier ist jedes gewünschte Eingabeformat zulässig, es müssen jedoch X- und O-Zeichen verwendet werden. Die angegebenen Beispiele sollten sich nicht auf dieses Format beschränken, sondern nur inspirieren.

Magische Kraken-Urne
quelle
Sorry DJMCMayhem, ich habe tatsächlich versucht, diese Dinge zu markieren, konnte es aber nicht, da ich neu hier bin.
Magic Octopus Urn
Bonus ebenfalls entfernt, nichts als Langeweile hinzugefügt.
Magic Octopus Urn
Ist das folgende Ausgabeformat zulässig: Ein Diagramm der Brettposition mit einem eindeutigen Zeichen auf jedem ursprünglich leeren Feld, das angibt, ob das Spielen dort zu einem Gewinn / Verlust / Unentschieden führt (z. B. W, L und D)
Ton Hospel
1
Im 3x3-Beispiel sollte O verlieren, egal was er spielt, aber Sie sagen, die Ausgabe sollte [2,1] sein, warum ist das so?
Dada
Bearbeitet, guter Fang. Ich weiß nicht, was ich dachte, das war das negative Beispiel.
Magic Octopus Urn

Antworten:

8

Perl, 101 98 Bytes

Enthält +4für-0p

Führen Sie mit der Eingabe auf STDIN

tictactoe.pl
OXO
---
--X
^D

Die Ausgabe ist das gleiche Diagramm, aber bei jeder Aktualisierung des Status wird 1ein Gewinn, 2ein Unentschieden und 3ein Verlust angezeigt . Für diesen Fall wäre das

OXO
223
21X

also 3 Züge ziehen, 1 gewinnt und 1 verliert (Ich aktualisiere die Lösung, wenn dieses Ausgabeformat nicht akzeptabel ist, aber der Basiscode gleich bleibt)

tictactoe.pl:

#!/usr/bin/perl -0p
m%@{[map"O.{$_}"x"@-"."O|",1-/.(
)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2

Dies ist bereits schmerzhaft langsam und verbraucht viel Speicher für das leere 3 * 3-Board (warum geht die Rekursion eigentlich nicht so tief. Muss ein Speicherleck sein). Das Hinzufügen von Memoizing kostet 6 Bytes, ist aber viel vernünftiger:

#!/usr/bin/perl -0p
$$_||=m%@{[map"O.{$_}"x"@-"."O|",1-/.(\n)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2
Tonne Hospel
quelle
Wow, übersehen, dass es pl ist und wahrscheinlich nicht für n = 10 mit vielen Leergut laufen würde ... Sie haben beide Dinge getan, auf die ich gehofft hatte, jemanden zu sehen. Eine Zeichenfolge, die das Ergebnis für alle Züge und nicht nur für die besten abbildet. Bravo.
Magic Octopus Urn
Wenn eine rekursive Funktion 'leak' ist, wie kann das in Ordnung sein ??? Zu hohe Sprache machen nicht das 32-Bit-Register in der CPU (oder so etwas wie die einfache Anweisung) zu sehen
RosLuP
@RosLup Leak bedeutet in diesem Zusammenhang nicht unbedingt, dass nicht erreichbarer Speicher verloren geht. Perl ist ziemlich eigenartig, wenn es Speicher freigibt. Dies geschieht ziemlich oft später als erwartet und verwendet daher viel mehr Speicher als erwartet. In der Erwartung, dass Sie Ihre Datenstrukturen erweitern, wird tendenziell auch mehr zugewiesen als direkt benötigt. In diesem Fall würde die Verwendung einer "normalen" Rekursion mit einer Funktion anstelle des Missbrauchs von do$010-mal weniger Speicherplatz verbrauchen. Wohlgemerkt, dieser Fall ist so extrem, dass es sich tatsächlich um ein echtes Speicherleck handelt.
Ton Hospel
Nicht nur, dass man die Register oder die Basisanweisungen (aus den hlls-Anweisungen) nicht sieht, sondern die Kontrolle über die Speichernutzung verliert ... Für mich skalieren sie nicht ...
RosLuP
Es ist lange genug her, du gewinnst meinen Mann, traurig, dass wir keine weiteren Versuche bekommen haben.
Magic Octopus Urn
2

Javascript (ES6), 320 294 Bytes

(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

Eingang

1) Ein Array von Zeichen, das die aktuelle Karte beschreibt, wie zum Beispiel:

[['X', '-'], ['-', 'O']]

2) Eine Ganzzahl, die die aktuelle Runde beschreibt: 1 = X, -1 =O

Ausgabe

Ein Array aus:

  • Ein Array, das den besten Zug im [x, y]Format beschreibt
  • Das Ergebnis des Spiels ist eine ganze Zahl: 1 = Gewinn, -1 = Verlust, 0 = Unentschieden

Beispiel

Im folgenden Beispiel Xwird garantiert, dass Sie gewinnen, indem Sie spielen [1, 2].

let f =
(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

console.log(JSON.stringify(f(
  [['O','X','O'],
   ['-','-','-'],
   ['-','-','X']],
  1
)));

Ein seltsames Spiel. Der einzige Gewinnzug ist kein Spiel.
Wie wäre es mit einem schönen Schachspiel?

Arnauld
quelle
Gut gemacht, guter erster Einstieg. Ich habe nur Anmerkungen, die das Potenzial haben, Bytes mit der angegebenen Information "X wird immer zuerst verschoben" zu speichern. Und hast du es mit einem nicht 3x3 Board versucht;)?
Magic Octopus Urn
@carusocomputing - Verstehe nicht genau, was du mit 'X bewegt sich immer zuerst' vorhast. Es könnte verwendet werden, um zu bestimmen, welche Seite allein auf der Platine in Bewegung ist, aber eine Berechnung, die tatsächlich mehr Bytes kosten würde; Ich schätze, du redest über etwas anderes. Antwort: Ja, ich habe einige Tests mit etwas größeren Boards durchgeführt. Das sollte wie erwartet funktionieren, solange ... äh ... nicht zu viele freie Stellen vorhanden sind. :-)
Arnauld
Die Herausforderung sagt The current state of the board must be the only input to your program. Ihr Code benötigt zwei Eingaben, wodurch diese Regel verletzt wird.
Dada
1
@Dada - ich frage mich darüber, aber ich nahm die aktive Farbe ist Teil des Staates der Platte (wie eine Schachposition kommt immer mit aktiver Farbe + en passant Quadrat + Verfügbarkeit Rochade). Ich denke, das OP sollte diesen Punkt klarstellen. (Und wenn Sie Recht haben, klingt das nach einer unnötigen zusätzlichen Schwierigkeit, IMHO.)
Arnauld
1
Mmm .. Ich mag die Erklärung des Board-Status in seiner Antwort. Wenn man darüber nachdenkt, werden in einigen Sprachen möglicherweise nur Zeichenfolgen als Eingabe verwendet. Wenn eine Karte wie XXOOXO-OO in niedrigen Bytezahlen nur schwer zu entschlüsseln ist, wenn zusätzliche Informationen wie die Größe der Karte fehlen. Ich erlaube keine zusätzlichen Eingaben, die zum Board-Status beitragen, obwohl ich immer noch der Meinung bin, dass die Information "Angenommen, X bewegt sich zuerst" anders ist als "Wer ist dran?". Einige Sprachen werden davon ausgehen;).
Magic Octopus Urn