Hintergrund

Mu Torere ist ein Spiel, von dem nur zwei bekannt sind, dass es von den Maori Neuseelands vor dem europäischen Einfluss gespielt wird. Dies macht es zu einem sehr einzigartigen Spiel, da es ein "objektives Gewinnkriterium" und Spielregeln hat, die sich von den meisten anderen existierenden Spielen unterscheiden.

Spielweise:

Das Brett ist ein Achteck. Zwischen jedem benachbarten Scheitelpunkt bestehen Verbindungen, und es gibt einen Zentralknoten, der mit allen Scheitelpunkten verbunden ist. Zu jedem Zeitpunkt sind acht der neun Knoten mit Steinen besetzt. Zu Beginn gibt es vier weiße und vier schwarze Steine, die jeweils eine Hälfte des Achtecks ​​einnehmen, wobei der Mittelknoten leer ist. Schwarz bewegt sich zuerst.

In jeder Runde kann ein Spieler einen seiner Steine ​​entlang einer der 16 Kanten von einem Knoten zum leeren Knoten bewegen. Ein Stein kann nur von einem äußeren Knoten zum mittleren Knoten bewegt werden, wenn sich der Stein neben dem Stein eines Gegners befindet.

Ein Spieler verliert, wenn er nicht in der Lage ist, einen legalen Zug auszuführen. Dies geschieht, wenn keine Kante einen Stein mit dem leeren Knoten verbindet.

Hier ist eine Website, die die Regeln erklärt (mit einem Diagramm) und einige Analysen anbietet.

Die Herausforderung

Ihre Herausforderung besteht darin, das kürzeste Programm zu schreiben, mit dem Mu Torere gegen einen menschlichen Gegner perfekt gespielt werden kann. Ihr Programm sollte in der Lage sein, das Spielbrett anzuzeigen und zu aktualisieren, Bewegungen auszuführen und Bewegungen eines menschlichen Gegners zu empfangen. Am wichtigsten ist, sollte es ein perfektes Spiel spielen.

Perfektes Spiel?

Ja, perfektes Spiel. Ich habe einige Spielanalysen durchgeführt und festgestellt, dass das Spiel unendlich lange hält, wenn es von beiden Seiten perfekt gespielt wird. Dies bedeutet, dass Ihr Programm niemals verlieren sollte. Außerdem sollte Ihr Programm in der Lage sein, einen Sieg zu erzwingen, wenn der menschliche Gegner einen Fehler macht, der es dem Programm ermöglicht, einen Sieg zu erzwingen. Wie Ihr Programm den perfekten Zug findet, liegt ganz bei Ihnen.

Einzelheiten

Nach jedem Zug (und zu Beginn des Spiels) sollte Ihr Programm den Spielplan ausdrucken. Wie auch immer Sie sich entscheiden, die Karte muss alle Knoten anzeigen und vollständig verbunden sein (alle 16 Verbindungslinien sollten ohne gekreuzte Linien gezeichnet sein). Zu Beginn sollte das Board die richtige Startposition haben. Eine Möglichkeit, dies zu erreichen, besteht darin, das Spielbrett zu einem Quadrat zu machen.

w-w-w
|\|/|
b-o-w
|/|\|
b-b-b

Die beiden Farben sind Schwarz und Weiß oder Dunkel / Hell. Auf dem Spielplan muss angegeben werden, welche Knoten von welchen Spielerstücken besetzt sind, z. B. mit einem "b" oder "w", und welcher Knoten frei ist. Die Teilnehmer werden ermutigt (aber nicht verpflichtet), das Spielbrett grafischer zu gestalten, anstatt nur Text.

Ihr Spielplan sollte über ein Nummerierungssystem verfügen, das jedem Knoten eine eindeutige Nummer gibt. Sie können das Board beliebig nummerieren, dies sollte jedoch in Ihrer Antwort oder im Programm erläutert werden. Die quadratische Tafel kann wie folgt nummeriert werden:

1-2-3
|\|/|
4-5-6
|/|\|
7-8-9

Der Mensch ist der erste, der sich bewegt. Seine Eingabe wird eine einzelne Zahl sein. Dies ist die Nummer des Knotens, auf dem sich der bewegte Stein gerade befindet. Wenn ich einen Stein von Knoten 4 auf einen leeren Knoten 5 verschieben möchte, gebe ich a ein 4. Die 5 ist impliziert, da es der einzige leere Knoten ist.

Angenommen, der Mensch wird immer einen legalen Zug machen.

Nachdem der Mensch seinen Zug gemacht hat, sollte eine aktualisierte Tafel gedruckt werden. Nachdem sich Ihr Programm für einen legalen Zug entschieden hat, sollte es eine weitere aktualisierte Tafel drucken und dann warten, bis der Mensch einen weiteren Zug ausführt.

Ihr Programm sollte enden, sobald es gewonnen hat.

Anmerkungen

Es gelten die Standard-Code-Golfregeln, kein Zugriff auf externe Dateien usw. usw. Außerdem werde ich Ihrem Programm eine flexible Zeitbeschränkung von 15 Sekunden (auf einem vernünftigen Computer) auferlegen, damit es jede seiner Bewegungen ausführt. Wie gesagt, dieses Spiel hat die Möglichkeit, Endlosschleifen zu bilden, und ich möchte nicht, dass eine Tiefensuche in eine Endlosschleife gerät.

Rubin, 390 Zeichen

o=->s,c{f=s=~/o/;[*0..8].select{|t|s[t]==c&&(t<1||(t+6)%8+1==f||t%8+1==f||f<1&&(s[(t+6)%8+1]!=c||s[t%8+1]!=c))}.map{|t|k=s*1;k[f]=c;k[t]=?o;k}}
v=->s,c,h{f=o[s,c];f==[]?0:h<1?1:2-f.map{|t|v[t,c>?b??b:?w,h-1]}.min}
q=->g{puts"1-2-3\n|\\|/|\n8-0-4\n|/|\\|\n7-6-5\n".tr"0-8",g;$>.flush}
q[g="obbbbwwww"]
(g.tr!?o,?b;g[gets.to_i]=?o;q[g];q[g=o[g,?w].sort_by{|q|v[q,?w,5]}[-1]])while v[g,?b,5]>0

Eine Implementierung in Ruby, die direkt den Spielbaum berechnet (der ziemlich viel Code benötigt) und somit immer optimal spielt. Die Platinenpositionen drehen sich wie in der folgenden Abbildung gezeigt nach außen:

1 - 2 - 3
| \ | / |
8 - 0 - 4
| / | \ |
7 - 6 - 5

Bash und Freunde ( 463 447 Zeichen)

t(){ tr 0-8a-i $b$b
}
p(){ t<<E
0-1-2
|\|/|
3-4-5
|/|\|
6-7-8

E
}
g(){ b=`tr $x$e $e$x<<<012345678|t`
p
e=$x
}
b=bbbbowwww
e=4
m=0
p
while [ $m != 5 ]&&read x;do
g
m=0
for y in {0..8};do
s=0
S=05011234
grep -E "w.*($y$e|$e$y)"<<<${b:$y:1}30125876340142548746>/dev/null&&for p in wow.\*/ww wow.\*/w bbo.\*/b obb.\*/b www wbw .
do
((s++))
tr $y$e $e$y<<<3012587630/4e|t|grep $p>/dev/null&&break
done
s=${S:$s:1}
[ $s -gt $m ]&&m=$s x=$y
done
g
done

Der Mensch spielt als b, der Computer alsw . Die Position der Karte ist wie im Dokument oben nummeriert. Es stellt sich heraus, dass die Heuristiken für ein perfektes Spiel überraschend einfach sind.

Auf der anderen Seite ist es ziemlich schwierig, den interessanten Weg zu verlieren. http://ideone.com/sXJPy demonstriert den kürzestmöglichen Selbstmord gegen diesen Bot. Beachten Sie, dass mit der zusätzlichen 0 am Ende geprüft werden soll, ob die Schleife korrekt durchbrochen wurde.