Spielen Sie ein perfektes 4x4 Hex-Spiel

10

Hintergrund

Hex ist ein abstraktes Strategiespiel für zwei Spieler, das auf einer K×KRaute aus sechseckigen Kacheln gespielt wird. Zwei gegenüberliegende Seiten der Raute sind weiß gefärbt, und die anderen beiden schwarz, und die beiden Spieler, schwarz und weiß, wechseln sich ab, indem sie ein Zeichen ihrer Farbe auf ein unbesetztes Plättchen legen. Der Spieler, der es zuerst schafft, einen Pfad zwischen den gegenüberliegenden Seiten seiner Farbe zu konstruieren, ist der Gewinner. Es ist bekannt, dass das Spiel nicht unentschieden enden kann und dass der erste Spieler unabhängig von der Brettgröße eine Gewinnstrategie hat (Details finden Sie auf der Wikipedia-Seite).

Die Aufgabe

Bei dieser Herausforderung legen wir die Kartengröße fest K = 4und stellen die Karte als das folgende Raster dar. Die dicken Linien kennzeichnen benachbarte Kacheln.

Ein 4x4 Gitter.

Ihre Aufgabe ist es, eine Gewinnstrategie für den ersten Spieler zu erstellen, die Sie entweder als Schwarz oder Weiß auswählen können. Dies bedeutet, dass Ihr Spiel unabhängig von den legalen Bewegungen des gegnerischen Spielers zu einem Sieg führen muss. Ihre Eingabe ist eine Spielposition (die Anordnung der Token auf dem Brett), und Ihre Ausgabe ist eine legale Bewegung in dem unten angegebenen Format. Wenn Sie selbst eine Gewinnstrategie finden möchten, lesen Sie diesen Spoiler nicht:

Umriss einer möglichen Gewinnstrategie, vorausgesetzt, Weiß steht an erster Stelle. Wählen Sie zuerst 5 aus. Wenn Sie danach einen Pfad von 5 zur unteren Reihe haben ODER Schwarz an einem beliebigen Punkt 0 oder 1 auswählt, wählen Sie die freie 0 oder 1 aus. Wenn Schwarz 9 oder 13 auswählt, wählen Sie 10 und dann welche von 14 oder 15 frei ist. Wenn Schwarz nicht 9, 13 oder 14 auswählt, wählen Sie 9 und als nächstes, was auch immer von 13 oder 14 frei ist. Wenn Schwarz 14 auswählt, antworten Sie mit 15. Wählen Sie anschließend 10 aus, wenn es frei ist. Wenn Schwarz 10 auswählt, antworten Sie mit 11. Wenn Schwarz dann 6 auswählt, antworten Sie mit 7 und als nächstes, je nachdem, welcher von 2 oder 3 frei ist. Wenn Schwarz nicht 6 auswählt, wählen Sie es aus, sodass Sie einen Pfad von 5 zur unteren Reihe haben.

Ein- und Ausgabe

Ihre Eingabe besteht aus einer Zeichenfolge mit 16 Zeichen WBE, die für Weiß, Schwarz und Leer steht. Sie repräsentieren die Kacheln der Tafel, wie oben aufgezählt. Sie können die Eingabemethode (die auch Ihre Ausgabemethode bestimmt) wie folgt auswählen:

  1. Eingabe von STDIN, Ausgabe von STDOUT.
  2. Eingabe als ein Befehlszeilenargument, Ausgabe an STDOUT.
  3. Eingabe als 16 einstellige Befehlszeilenargumente, Ausgabe an STDOUT.
  4. Eingabe als Argument der benannten Funktion, Ausgabe als Rückgabewert.

Ihre Ausgabe stellt das Plättchen dar, auf das Sie Ihren nächsten Spielstein legen, da Sie an der Reihe sind, sich zu bewegen. Sie können aus folgenden Ausgabeformaten wählen:

  1. Ein auf Null basierender Index (wie im obigen Bild verwendet).
  2. Ein einbasierter Index.
  3. Die Eingabezeichenfolge mit einer Eersetzt durch die von Woder BSie wählten für Ihren Player.

Regeln

Ihre Strategie muss deterministisch sein. Sie müssen mit Ihrer Strategie nicht richtig mit Spielpositionen umgehen, die vom leeren Brett aus nicht erreichbar sind, oder mit Positionen, die für einen der beiden Spieler bereits gewonnen haben, und Sie können darauf abstürzen. Umgekehrt müssen Sie auf Boards, die mit Ihrer Strategie erreichbar sind, einen legalen Schritt zurückgeben.

Dies ist Code-Golf, also gewinnt die niedrigste Byteanzahl. Standardlücken sind nicht zulässig.

Testen

Ich habe einen Python 3-Controller zum Überprüfen von Einträgen geschrieben, da es äußerst mühsam wäre, dies von Hand zu tun. Sie finden es hier . Es unterstützt die ersten drei Eingabeformate und Python 3-Funktionen (Funktionen in anderen Sprachen müssen in Programme eingeschlossen werden), alle drei Ausgabeformate und beide Player. Wenn eine Strategie nicht gewinnt, wird ein verlorenes Spiel ausgegeben, das Sie gefunden haben, sodass Sie Ihr Programm optimieren können.

Zgarb
quelle
Diese Herausforderung erinnert mich an den Versuch, eine Tic Tac Toe-KI zu komprimieren, als ich Taschenrechnerprogramme schrieb. ticalc.org/archives/files/fileinfo/354/35408.html
Sparr
2
Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.Ich hätte schon vor langer Zeit gewinnen sollen, oder irre ich mich?
Sebastian Höffner
@ SebastianHöffner Das sieht aus wie ein Fehler im Controller. Ich werde versuchen, es zu beheben, wenn ich Zeit habe.
Zgarb
@ SebastianHöffner Der Fehler sollte nun behoben sein.
Zgarb

Antworten:

6

Marbelous, 973b

Dies ist eine naive Umsetzung der in der Frage angedeuteten Strategie. Es wird erwartet, dass die Karte als 16 Befehlszeilen- / Hauptplatinenparameter wie bereitgestellt wird, hex.mbl B W E E E W E E E B E E E E E Eund es wird die nullindizierte Position der nächsten Bewegung von Weiß ausgegeben.

00 }1 }0
&G B? W!
&0 &G &G
!!
00 }0 }1
&H B? W!
&1 &H &H
!!
.. }D .. }9 }9 }D }E }A }D }9 }A .. }E }F }5
}9 B! }E E? W? E? .. E? B? B? W? .. E? .. E?
B! ?0 B! &M &N &O E? &I \\ .. &J .. &K E? &5
?0 ++ ?0 &9 .. &D &P &A &I /\ &J .. &E &L !!
++ .. ++ !! .. !! &E !! \/ &L /\ &K !! &F
\\ .. // .. .. .. !! .. .. \/ .. \/ .. !!
.. =3 \/
&M /\ &N
\/ &O /\ &P
}0 }1 }6 .. }6 .. }7 &7 }2 }3 }A }A }B }E }F
..
..
..
..
..
..
..
..
..
.. .. .. .. .. .. .. .. .. .. .. .. .. B? W!
.. .. .. .. .. .. .. .. .. .. .. .. .. &Q &Q
.. .. .. .. B? .. E? W? E? .. E? B? E? &F \/
.. .. .. &S /\ &T &S &T &U E? &A &R &R !!
.. .. .. &7 .. .. \/ .. &2 &V !! &B \/
.. .. .. !! .. .. &U /\ &V &3 .. !!
.. .. .. .. .. .. .. .. .. !!
.. .. ..
.. .. E?
E? .. &6
&X E? !!
!! &Y
.. !!
}4 }8 }C
\/ \/ \/
30 30 31 31 32 33 35 36 37 39 31 30 31 31 31 33 31 34 31 35
&0 &X &1 &Y &2 &3 &5 &6 &7 &9 &A &A &B &B &D &D &E &E &F &F
:W?
}0
^4
=1
{0
:B?
}0
^0
=0
{0
:E?
}0
^1
=0
{0
:W!
}0
^4
=0
{0
:B!
}0
^0
>0
{0

Ich denke, ich kann wahrscheinlich etwa 200 Zeichen davon mit einer besseren Verzweigung und Eliminierung der Wiederverwendung von Code spielen.

Sparr
quelle
Ich habe die Option für 16 Befehlszeilenargumente hinzugefügt und das Überprüfungsskript aktualisiert, damit diese Lösung getestet werden kann.
Zgarb
Marbelous +1 (PPCG glaubt, dass das Hinzufügen dieser Zeichen den Kommentar verbessert hat)
Rohan Jhunjhunwala
1

Python 3, 100b

b=input()
i=b.find('B')
if b[i]in'BW'and'E'in b:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])
  • Spieler: SCHWARZ
  • Methode: STDIN / STDOUT, MODIFIED_BOARD

Die Strategie besteht darin, zuerst nach einem Ban der Tafel zu suchen . Wenn es keine gibt, wird zurückgegeben -1, was in Python dasselbe ist wie last index. Auf einem leeren Brett befindet sich also mein erster Index index=-1, an dem ich mich zu bewegen beginne.

Wenn das Feld zu meiner Linken ( index-1) frei ist, geht mein nächster Zug dorthin. Wenn es genommen wird, gehe ich nach links. Ich muss nie aufsteigen: Wenn ich das tue, verliere ich das Tempo und verliere das Spiel.

Auf einer Vollpension ( Enirgendwo) mache ich keine Bewegung.

Das printscheint zunächst etwas seltsam: Ich muss das neue Board konstruieren (was ich durch Schneiden mache), aber dann muss ich 16 Zeichen ausschneiden. Dies ist ein Relikt, da ich mit negativen Indizes arbeite und b[i+1:]daher das Lochbrett und den Rest, den ich erwarte, zurückgeben werde, was es wichtig macht, den Rest abzuschneiden. Ein anderer Weg wäre gewesen, mit positiven Indizes zu arbeiten, z. B. durch Nehmen (b.find('B')+16)%16, aber es (+16)%16ist ein Byte mehr als ()[:16].

Ungolfed:

board = input()
index = board.find('B')
if board[index] in 'BW' and 'E' in board:
    index -= 1 + (board[index-1] is 'W') * 4
print((board[:index] + 'B' + board[index+1:])[:16])

Prüfung

Beim Ausführen der Hex-Controller-Testsuite ist ein seltsames Verhalten aufgetreten:

OUT: EEEEEEEEEEEEEEEB
OUT: WEEEEEEEEEEEEEBB
OUT: WWEEEEEEEEEEEBBB
OUT: WWWEEEEEEEEEBBBB
OUT: WWWWEEEEEEEBBBBB
OUT: WWWWWEEEEEBBBBBB
OUT: WWWWWWEEEBBBBBBB
OUT: WWWWWWWEBBBBBBBB
OUT: WWWWWWWWBBBBBBBB

Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

Ich denke, ich hätte entweder nach der 4. Runde gewinnen sollen oder mit demselben Board auf ein Vollboard zu antworten, sollte eine korrekte Antwort sein. Ich bin mir nicht sicher, was dort schief geht, bin nicht viel tiefer getaucht - ich wollte nur überprüfen, ob alle "Sonderfälle" abgedeckt sind. Aber da ich keine Situationen vertuschen muss, in denen jemand mit Raum 4 oder so beginnt, spielt es sowieso keine Rolle.

85b

Wenn ich mir jedoch erlaube, nicht nach einer Vollplatine zu suchen (dh das wegzulassen, 'E' in bkann ich den Code weiter vereinfachen, um nur 85 Bytes zu verwenden:

b=input();i=b.find('B')
if i!=-1:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])

Dies führt jedoch zu Folgendem:

Incorrect response 'WWWBWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

Dies könnte gezählt werden oder auch nicht, und da ich feststellte, dass es kein gültiger Schritt war, entschied ich mich für die längere, aber korrektere Antwort.

Sebastian Höffner
quelle