Bestimmen Sie den Gewinner von Connect 4

19

Sie erhalten ein teilweise gefülltes Connect 4-Raster (7x6).

O X             
O X          
X O X O     O
X O X O   X X
O X X X O O X
O O O X X O X

(Die Eingabe kann als 1D- oder 2D-Array sowie als Buchstaben oder Zahlen usw. erfolgen.)

Annehmen, dass

  • X hat das Spiel gestartet.
  • Niemand hat bisher gewonnen.
  • Die Spieler haben vielleicht bis jetzt nicht gut gespielt, aber ab jetzt werden beide optimale Strategien anwenden.
  • Eingangsnetz ist nicht fehlerhaft.

Sie müssen einen einzelnen Wert ausgeben, der angibt, welcher Spieler gewinnt (oder ein Unentschieden).

Code Golf Herausforderung; so gewinnt der kürzeste Code. Ihr Programm muss die Ausgabe nicht in angemessener Zeit tatsächlich berechnen, aber Sie sollten in der Lage sein, zu beweisen, dass die Ausgabe in einer begrenzten Zeit korrekt erhalten wird.

ghosts_in_the_code
quelle
Verbunden.
Martin Ender
@ MartinBüttner Heißt das, ich werde abgelehnt, oder ist es in Ordnung, meine Frage hier zu lassen?
ghosts_in_the_code
4
Es bedeutet nur, dass die Fragen zusammenhängen, nicht mehr und nicht weniger. Durch das Posten des Links sollen die Herausforderungen in der Seitenleiste "Verknüpft" des jeweils anderen angezeigt werden, damit die Benutzer die damit verbundenen Herausforderungen leichter finden können. Wenn ich Ihre Frage als Duplikat angesehen hätte, hätte ich dies gesagt (oder sie einfach geschlossen), also keine Sorge. :)
Martin Ender
2
Ist "optimales Spiel" gut definiert? Wenn ja, können Sie einen Link bereitstellen, der den Algorithmus für ein optimales Spiel beschreibt?
Rainbolt
2
@Rainbolt Es wurde behoben und es gibt auch perfekte Algorithmen . Lesen Sie Wikipedia für mehr.
ghosts_in_the_code

Antworten:

16

Perl, 119 118 117 Bytes

Beinhaltet +4 für -0p

Gib gedrehtes Brett mit Leerzeichen auf STDIN (Schwerkraft zieht Steine ​​nach rechts)

connect4.pl
  OXXX
   XOO
    OX
  OOXX
  XXXO
XXOOXO
OOXXOO
^D

connect4.pl:

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

3Wird gedruckt, wenn der Spieler gewinnt, 1wenn der Spieler verliert und wenn 2er unentschieden spielt.

Bei älteren Perls können Sie ein Literal verwenden ^S, um ein Byte zu erhalten. Wenn Ihnen extreme Ineffizienz nichts ausmacht , können Sie die $$_||=(Transpositionstabelle) weglassen und 6 weitere Bytes gewinnen. Wenn Sie das weglassen, $_=wird Ihnen angezeigt, wo anstelle des Ergebnisses zu spielen ist (spielen 1und gewinnen, wenn es eines gibt, spielen 2und zeichnen, wenn es eines gibt, oder spielen 3und verlieren).

Erstellt und bewertet einen vollständigen Minimax-Baum. Sie haben nicht genügend Speicher und Zeit, es sei denn, die Platine ist bereits ausreichend gefüllt.

Tonne Hospel
quelle
2
Warum um alles in der Welt hat jemand eine Gegenstimme abgegeben? Das Golfen ist wirklich erstaunlich (ich spiele mit Perl und es ist extrem schwierig , eine solche Lösung zu finden - ich bin mir nicht sicher, ob ein anderer Perl-Golfer, den ich kenne, auf diesen Code gekommen ist). Und der Code hat das erforderliche Verhalten.
Dada
Das macht mein Gehirn weh. +1!
Levelonehuman
@Dada woher weißt du, dass diese Antwort abgelehnt wurde? Ich sehe 3 als Abstimmung ...
RosLuP
@RosLuP Als ich diesen Beitrag zum ersten Mal sah, hatte er 1 Gegenstimme. Wenn Sie genügend Repräsentanten haben, können Sie auch sehen, wie viele Up- und Down-Stimmen ein Post hat: In diesem Fall hat er jetzt 4 Up- und 1 Down-Stimmen.
Dada