Tic-Tac-Latin!

Dies ist eine wahre Geschichte, daher wurden die Namen geändert.

Mein Lateinlehrer, Mr. Latin, hat seine eigene (kein Scherz) Tic Tac Toe-Variante entwickelt. Nennen wir es Tic-Tac-Latin. Das Spiel ist einfach, es ist im Wesentlichen Tic Tac Toe, das auf einem Vier-mal-Vier-Raster gespielt wird.

Formale Regelerklärung

Eine Linie ist entweder eine Zeile, eine Spalte oder eine Diagonale. Es gibt zwei Symbole, 'X' und 'O', aber eines oder beide können ein anderes Symbol ersetzen.
Sie erhalten einen Punkt, wenn Sie drei Ihrer Symbole und einen der anderen Charaktere haben.

Diese Arrangements punkten:

---Ö
-Ö--
XXXO
XOOX

O -XX
- O -
- X -
--- O.

Diese punkten nicht:

----
XXXX
----
OOOO

----
XXX-
----
OOO-

Das Spiel wird gewonnen, wenn ein Spieler mehr Punkte als ein anderer hat. Das Spiel ist nur dann unentschieden, wenn das Brett voll ist.

Herausforderung

Löse dieses Spiel. Ihre Aufgabe ist es, einen Weg zu finden, um einen Sieg oder ein Unentschieden zu garantieren, je nachdem, welches das optimale Ergebnis ist.

Ihre Lösung kann entweder zuerst oder zweitens starten (und daher das Symbol auswählen). Es ist nicht zwingend erforderlich, ein interaktives Spiel zu implementieren, bei dem sich die Benutzereingaben bewegen und sich die entsprechende Anzeige ändert. Es kann sich auch um eine Funktion oder ein Programm handeln, das die Eingabe als Spielstatus verwendet und ein neues Brett oder eine Beschreibung ihres Zuges ausgibt . Jede Option muss innerhalb von ungefähr zehn Sekunden pro ausgeführtem Zug ausgeführt werden.

---

Das Spielen Ihres Spielers gegen eine beliebige Abfolge von Zügen muss das optimale Ergebnis liefern. Dies bedeutet, dass Sie davon ausgehen können, dass die Eingabeposition vom Spiel mit Ihrem Player aus erreichbar ist. Einsendungen müssen deterministisch sein und müssen nicht unbedingt einen Optimalitätsnachweis liefern. Wenn sie jedoch geknackt werden (indem sie geschlagen werden), werden Ihre Einsendungen als ungültig betrachtet (Sie können sie belassen, aber in der Überschrift hinzufügen (geknackt)).

---

Dies ist eine nicht triviale Aufgabe, daher ist jede gültige Einreichung beeindruckend und verdient einen akzeptierten Tick, aber ich werde Code Golf zum primären Gewinnkriterium machen.

Der Gewinner wird ausgewählt, indem Sie diese Liste durchgehen, bis ein Gewinner ausgewählt ist.

• Kürzeste gelöste Implementierung, die immer gewinnt
  
• Kürzeste Implementierung
  

Perl, 147 Bytes (nicht konkurrierend, dauert mehr als 10 Sekunden pro Zug)

Beinhaltet +4 für -0p

Das Programm wird abgespielt X. Es wird ein perfektes Spiel spielen.

Geben Sie die Karte über STDIN ein, z.

tictaclatin.pl
-X-O
-X--
X-X-
O--O
^D

Der Ausgang wird das gleiche Board sein, wobei alle Xdurch ersetzt werden Ound umgekehrt. Die leeren Stellen werden mit einer Zahl gefüllt, die das Ergebnis angibt, wenn X dort spielen würde. 1Dies bedeutet, dass das Ergebnis ein Gewinn, 2ein Unentschieden und 3ein Verlust ist. Ein fertiges Spiel gibt nur die gleiche Position mit umgekehrten Farben zurück.

In diesem Beispiel wäre die Ausgabe:

1O1X
1O33
O3O3
X33X

Die Position ist also ein Gewinn, Xwenn er an den drei Stellen oben und links spielt. Alle anderen Züge verlieren.

Diese verwirrende Ausgabe ist praktisch, wenn Sie wissen möchten, wie das Spiel nach einem Zug fortgesetzt wird. Da das Programm immer abgespielt wird X, müssen Sie tauschen Xund Odie Züge für sehen O. Hier ist zum Beispiel ziemlich klar, dass man Xgewinnt, wenn man oben links spielt, aber was ist, wenn man oben Xauf der dritten Position spielt? Kopieren Sie einfach die Ausgabe, setzen Sie eine Oanstelle der von Ihnen ausgewählten Bewegung ein und ersetzen Sie alle anderen Zahlen -erneut durch. Hier also:

-OOX
-O--
O-O-
X--X

Ergebend:

3XXO
3X33
X3X3
O33O

Offensichtlich sollte jeder Zug Overlieren. Wie verliert er also, wenn er oben links spielt? Tun Sie dies erneut, indem Sie Ooben links eingeben und die Ziffern ersetzen durch -:

OXXO
-X--
X-X-
O--O

Geben:

XOOX
1O33
O3O3
X33X

X hat also nur einen Weg, um seinen Sieg zu erringen:

XOOX
OO--
O-O-
X--X

Geben

OXXO
XX33
X3X3
O33O

Die Situation für Obleibt hoffnungslos. Es ist jetzt leicht zu erkennen, dass jeder Zug Xsofort gewinnen kann. Versuchen wir wenigstens, 3 O's hintereinander zu machen:

OXXO
XX--
X-X-
O-OO

Geben:

XOOX
OO13
O3O3
X3XX

Xspielt den einzigen Gewinnzug (beachten Sie, dass dies XXXOentlang der dritten Spalte erfolgt:

XOOX
OOO-
O-O-
X-XX

Hier ist die Ausgabe:

OXXO
XXX-
X-X-
O-OO

weil das Spiel schon beendet war. Sie können den Gewinn in der dritten Spalte sehen.

Das eigentliche Programm tictaclatin.pl:

#!/usr/bin/perl -0p
y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/sx;$@<=>0||s%-%$_="$`O$'";$$_||=2+do$0%eg&&(/1/||/2/-1)

Auf das leere Board angewendet werden 9506699 Positionen ausgewertet, was auf meinem Computer 30 GB und 41 Minuten dauert. Das Ergebnis ist:

2222
2222
2222
2222

Also zieht jeder Startzug. Das Spiel ist also ein Unentschieden.

Die extreme Speichernutzung wird hauptsächlich durch die Rekursion mit verursacht do$0. Die Verwendung dieser 154-Byte-Version mit einer einfachen Funktion benötigt 3 GB und 11 Minuten:

#!/usr/bin/perl -0p
sub f{y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/sx;$@<=>0||s%-%$_="$`O$'";$$_||=2+&f%eeg&&(/1/||/2/-1)}f

Das ist erträglicher (aber immer noch zu viel, etwas muss immer noch Speicher verlieren).

Das Kombinieren einer Reihe von Beschleunigungen führt zu dieser 160-Byte-Version (5028168 Positionen, 4 Minuten und 800 MB für die leere Karte):

#!/usr/bin/perl -0p
sub f{y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/osx;$@<=>0||s%-%$_="$`O$'";$a{$_}//=&f+1or return 1%eeg&&/1/-1}f

Letzteres wird 0für einen Sieg (nicht zu verwechseln mit O), 1für ein Unentschieden und 2für einen Verlust verwendet. Die Ausgabe von diesem ist auch verwirrender. Bei einem Gewinn ohne Farbtausch wird der Gewinnzug für X ausgefüllt. Wenn das Eingabespiel jedoch bereits gewonnen wurde, wird der Farbtausch immer noch ausgeführt und es wird kein Zug ausgefüllt.

Alle Versionen werden natürlich schneller und verbrauchen weniger Speicher, wenn die Karte voll ist. Die schnelleren Versionen sollten in weniger als 10 Sekunden einen Zug erzeugen, sobald 2 oder 3 Züge gemacht wurden.

Grundsätzlich sollte diese 146-Byte-Version auch funktionieren:

#!/usr/bin/perl -0p
y/XO/OX/,$@=-$@while/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^/sx,--$|;$@<=>0||s%-%$_="$`O$'";$$_||=2+do$0%eg&&(/1/||/2/-1)

aber auf meinem Computer löst es einen Perl-Fehler aus und entleert den Kern.

Alle Versionen funktionieren im Prinzip immer noch, wenn das 6-Byte-Positions-Caching von $$_||=entfernt wird, dies jedoch so viel Zeit und Speicher benötigt, dass es nur für fast gefüllte Boards funktioniert. Aber theoretisch habe ich zumindest eine 140-Byte-Lösung.

Wenn Sie $\=kurz vor dem (Kosten: 3 Bytes) setzen $@<=>0, folgt auf jede Ausgabekarte der Status der gesamten Karte: 1für XGewinne, 0für Unentschieden und -1für Verluste.

Hier ist ein interaktiver Treiber, der auf der oben genannten schnellsten Version basiert. Der Treiber hat keine Logik, wann das Spiel beendet ist, so dass Sie sich selbst stoppen müssen. Der Golfcode weiß es jedoch. Wenn der vorgeschlagene Zug ohne -Ersetzung durch irgendetwas zurückkehrt, ist das Spiel beendet.

#!/usr/bin/perl
sub f{
    if ($p++ % 100000 == 0) {
        local $| = 1;
        print ".";
    }
y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/osx;$@<=>0||s%-%$_="$`O$'";$a{$_}//=&f+1or return 1%eeg&&/1/-1}

# Driver
my $tomove = "X";
my $move = 0;
@board = ("----\n") x 4;
while (1) {
    print "Current board after move $move ($tomove to move):\n  ABCD\n";
    for my $i (1..4) {
        print "$i $board[$i-1]";
    }
    print "Enter a move like B4, PASS (not a valid move, just for setup) or just press enter to let the program make suggestions\n";
    my $input = <> // exit;
    if ($input eq "\n") {
        $_ = join "", @board;
        tr/OX/XO/ if $tomove eq "O";
        $p = 0;
        $@="";
        %a = ();
        my $start = time();
        my $result = f;
        if ($result == 1) {
            tr/OX/XO/ if $tomove eq "O";
            tr/012/-/;
        } else {
            tr/OX/XO/ if $tomove eq "X";
            tr/012/123/;
        }
        $result = -$result if $tomove eq "O";
        my $period = time() - $start;
        print "\nSuggested moves (evaluated $p positions in $period seconds, predicted result for X: $result):\n$_";
        redo;
    } elsif ($input =~ /^pass$/i) {
        # Do nothing
    } elsif (my ($x, $y) = $input =~ /^([A-D])([1-4])$/) {
        $x = ord($x) - ord("A");
        --$y;
        my $ch = substr($board[$y],$x, 1);
        if ($ch ne "-") {
            print "Position already has $ch. Try again\n";
            redo;
        }
        substr($board[$y],$x, 1) = $tomove;
    } else {
        print "Cannot parse move. Try again\n";
        redo;
    }
    $tomove =~ tr/OX/XO/;
    ++$move;
}

JavaScript (ES6) 392 Bytes

a=>b=>(c="0ed3b56879a4c21f",r=[],k=f=>r.push([a.filter(f),b.filter(f)]),[0,1,2,3].map(i=>k(n=>n%4==i)+k(n=>(n/4|0)==i)),k(n=>n%5==0),k(n=>n&&n-15&&!(n%3)),g=r.find(o=>(o[0].length==1&&o[1].length==2)||(o[0].length==2&&o[1].length==1)),g?parseInt(c[30-[...g[0],...g[1]].map(i=>parseInt(c[i],16)).reduce((p,c)=>p+c)],16):[...a,...b].indexOf(15-a[0])+1?15-a.find(i=>b.indexOf(15-i)==-1):15-a[0])

Verwendung

Der "Bot" spielt als Zweiter.

Zeichnen Sie ein 4x4-Raster, das wie folgt nummeriert ist:

+----+----+----+----+
|  0 |  1 |  2 |  3 |
+----+----+----+----+
|  4 |  5 |  6 |  7 |
+----+----+----+----+
|  8 |  9 | 10 | 11 |
+----+----+----+----+
| 12 | 13 | 14 | 15 |
+----+----+----+----+

Lassen Sie uns dies in der Browserkonsole ausführen: Stellen Sie es einfach f=vor den Code

Also, wenn ich anfangen will 1, würde ich rennen f([1])([])und es wird mir geben 14.

Netter Zug ... Was ist, wenn ich 2danach spiele ? f([2,1])([14]). Es wird zurückkehren 13.

Ich versuche mich zu ergeben. Spielen 3. f([3,2,1])([14,13]). Oh 0! Du hast mich!

Spielen 0? f([0,2,1])([14,13]). 15Ok, lass uns weiterspielen ...

Hinweis

1. Interaktiv spielen. Beginnen Sie mit f([your-step])([]).

2. Bereiten Sie Ihren nächsten Schritt vor. (Siehe Demo oben)

3. Helfen Sie dem "Bot", seine Schritte einzugeben. Es gibt keine guten Ergebnisse, wenn Sie eine zufällige Einstellung vornehmen. (Wie f([1,2,4])([14,12])wird geben 14- Hey, der Bot wollte in 13seinem zweiten Zug weiterspielen!

Kurze Zusammenfassung

Solange Sie sich nicht ergeben, spielt der Bot einen Spiegelzug.

Vielen Dank an @EHTproductions, dass Sie mir mitgeteilt haben, dass ich die Spielregeln und Golftipps falsch verstanden habe: P.

Jetzt wird auch erkannt, ob es Schachmatt hat. Wenn ja, blockieren Sie es!

Seine Prioritäten: Blockieren> Spiegeln> (Fallback) suchen nach Möglichkeiten, einen Spiegel zu reproduzieren