Spielen Sie Wythoffs Nim perfekt

16

Ihr Ziel ist es, einen perfekten Spieler für das Spiel Wythoffs Nim zu schreiben .

Regeln von Wythoffs Nim

Wythoffs Nim ist ein deterministisches Zwei-Spieler-Spiel, das mit zwei Stapeln identischer Spielsteine ​​gespielt wird. Die Spieler wechseln sich ab, indem sie eine der folgenden Aktionen ausführen:

  1. Entfernen Sie eine oder mehrere Marken vom ersten Stapel
  2. Entfernen Sie eine oder mehrere Marken vom zweiten Stapel
  3. Entfernen Sie eine gleiche Anzahl von Zählmarken (eine oder mehrere) sowohl vom ersten als auch vom zweiten Stapel.

Natürlich können Stapel nicht negativ werden, aber sie können auf 0 gesetzt werden. Derjenige Spieler, der den letzten Zähler insgesamt entfernt, gewinnt das Spiel.

Für die Geometrischeren ist hier eine äquivalente Formulierung des Spiels, das Sie auf diesem Applet spielen können . Eine einzelne Dame beginnt auf einem Feld eines viertel-unendlichen Schachbretts, dessen Ecke sich unten links befindet. Die Spieler ziehen abwechselnd die Dame, die sich wie eine Schachkönigin bewegt, jedoch auf drei Richtungen beschränkt ist:

  1. Nieder
  2. Links
  3. Diagonal nach unten und links

Wer die Dame in die Ecke zieht, gewinnt.

Wenn Sie die Koordinaten der Dame (mit Ecke (0,0)) mit den Größen der jeweiligen Stapel verknüpfen, können Sie leicht erkennen, dass beide Spiele gleich sind.

Perfektes Spiel

(Sie können dies überspringen, wenn Sie mit den Vorstellungen von perfektem Spiel und Gewinnzügen vertraut sind.)

Da Wythoffs Nim ein endliches und deterministisches Spiel ist, hat es eine Vorstellung von perfektem Spiel . Ein perfekter Spieler ist eine Strategie, die immer von einer theoretisch gewonnenen Position gewinnt, dh von einer Position, in der es eine Strategie gibt, die einen Sieg garantiert.

Um eine Gewinnstrategie zu sein, genügt es, sich immer auf eine theoretische Gewinnposition für den Spieler zu bewegen, der gerade umgezogen ist, und damit für den Spieler, der nicht weiter geht. Die ersten dieser Gewinnpositionen (auch als kalte Positionen bezeichnet ) sind (0,0), (1,2), (2,1), (3,5), (5,3). Im Wikipedia-Artikel finden Sie eine Erklärung eines Algorithmus zur Ermittlung einer Gewinnstrategie für Wythoffs Nim sowie eine Formel zur Generierung von Gewinnpositionen.

Programmanforderungen

Schreiben eines Programms oder einer Funktion nimmt eine Position als Eingabe ein und gibt einen Gewinnzug in Form der Position nach diesem Zug aus. Wenigste Bytes gewinnt.

Wenn kein Gewinnzug existiert, dh die Position ein theoretischer Verlust ist, sollte Ihr Programm dies anzeigen und verfallen.

Ihr Programm muss innerhalb eines angemessenen Zeitraums ausgeführt werden. Eine exponentielle rekursive Spielbaumsuche reicht also nicht aus. Wenn Sie eine Strategie vorberechnen und hart codieren möchten, ist das in Ordnung.

Eingang

Ein Paar (i,j)nicht negativer Zahlen, die jeweils höchstens die Stapelgröße darstellen 99. Dies können zwei Zahlen, ein Tupel, eine Liste oder ein beliebiger Container sein.

Ausgabe

Drucken oder geben Sie die Position nach Ihrem Umzug erneut als zwei Zahlen oder einen Container davon aus. Dies muss ein legaler Schritt zu einer Gewinnerposition sein. Wenn es mehrere solcher Züge gibt, ist jeder in Ordnung, aber nur einer.

Wenn es keinen Gewinnzug gibt, müssen Sie dies in der Ausgabe angeben. Jede Ausgabe wie False, None, 0, oder (-1,-1)tun wird, solange es keine rechtliche Position ist, und ist für jeden Verlierer Eingang.

Beispiel läuft

f(5,0)   = (0,0)
f(2,2)   = (1,2)   # Or (2,1) or (0,0) 
f(1,2)   = False
f(13,9)  = (13,8)  # Or (10,6)
f(10,6)  = False
f(5,10)  = (5,3)
f(25,30) = (8,13)    
xnor
quelle
2
+1, zum Teil, weil ich die Idee eines Viertels der Unendlichkeit mag.
Level River St
Definieren Sie "angemessene Zeit". Sind mehrere Sekunden für (100,50) eine angemessene Zeitspanne?
John Dvorak
Oh. Warten. die Eingabe ist begrenzt durch ... 30 ??? Das ist ein bisschen niedrig, nicht wahr?
John Dvorak
@ JanDvorak Du hast recht, es könnte billige Verknüpfungen zulassen. Geändert zu 99 - ich denke das reicht aus? Entschuldigung für die Bearbeitung der Spezifikationen nach dem Posten.
XNOR
@ PeterTaylor Danke, behoben.
XNOR

Antworten:

6

Haskell, 167 165 Zeichen

c p=o p:c(o p:p)
o p=[(a,b)|a<-[0..],b<-[0..a],(a,b)?p==[]]!!0
(a,b)?p=[y|y@(c,d)<-p,c==a||c==b||d==b||a+d==b+c]
f x@(a,b)|a<b=f(b,a)|x?c[]!!0==x=(0,-1)|1>0=x?c[]!!0

Der Algorithmus ist ineffizient, läuft jedoch innerhalb einer Sekunde (jedoch nicht in der interaktiven Konsole) für Eingaben <100.

Erläuterung:

c p=o p:c(o p:p)

Die Liste der kalten Positionen bei einer Reihe von vorherigen kalten Positionen ist eine kalte Position, gefolgt von der Liste der kalten Positionen bei dieser Position und den vorherigen Positionen (Ineffizienz: Diese Position wird zweimal generiert).

o p=[(a,b)|a<-[0..],b<-[0..a],(a,b)?p==[]]!!0

Eine kalte Position ist das erste Paar, sodass von diesem Paar keine kalten Positionen erreichbar sind. (Ineffizienz: Wir sollten stattdessen nach dem vorherigen Paar suchen.)

(a,b)?p=[y|y@(c,d)<-p,c==a||c==b||d==b||a+d==b+c]

Von einem Paar aus erreichbare Positionen sind solche, bei denen die ersten Elemente, die zweiten Elemente, die Differenz oder der kleinere Haufen vor dem Entfernen mit dem größeren Haufen nach dem Entfernen übereinstimmen.

f x@(a,b)|a<b=f(b,a)
         |x?c[]!!0==x=(0,-1)
         |1>0=x?c[]!!0

(Hauptmethode) Wenn sich die Haufen in der falschen Reihenfolge befinden, tauschen Sie sie aus. Wenn die erste kalte Position, die von einer Position aus erreichbar ist, die Position selbst ist, geben Sie einen Fehler an (im Idealfall würde man Maybe (Int,Int)stattdessen zurückkehren). Anderenfalls kehre diese kalte Position zurück (Ineffizienz: das Paar wird zweimal nachgeschlagen. Schlimmer noch, die Liste der kalten Positionen wird zweimal generiert).

John Dvorak
quelle
Es scheint, dass " Eine exponentielle rekursive Spielbaumsuche nicht ausreicht ", weil das, was Sie beschreiben, genau so klingt.
Peter Taylor
@PeterTaylor das ist O (n ^ 4). Jedes kalte Paar braucht O (n ^ 3) Zeit, um zu finden, und es gibt O (n) von ihnen. Die Optimierung der Generierung würde es auf O (n ^ 2) bringen (wenn ich die Sequenz richtig lese). Ein Exponentialzeit-Algorithmus wäre viel langsamer. Soll ich ein paar Tests durchführen?
John Dvorak
Es ist in Ordnung, ich glaube dir.
Peter Taylor
Sie können den x@fromx@(a,b)?p=...
proud haskeller 29.11.14
Ich bin mir nicht sicher, wie es dahin gekommen ist. Reparieren, danke.
John Dvorak
5

GolfScript ( 63 57 Bytes)

{\]zip{~-}%0|$(!*,1=}+1,4*{..,,^[(.@,2/+.2$]+}38*2/?0]0=`

Erwartet die Eingabe von stdin im Formular [a b]und belässt die Ausgabe auf stdout in diesem Formular oder 0wenn es sich um eine Verlustposition handelt. Online-Demo

Überblick

,4*{..,,^[(.@,2/+.2$]+}38*2/

berechnet eine Liste der kalten Positionen (einschließlich der gespiegelten Version [b a]für jede kalte Position [a b]) unter Verwendung der Beatty-Sequenzeigenschaft .

Dann ?sucht nach der ersten Kaltstellung erfüllt den Block erstellt von

{\]zip{~-}%0|$(!*,1=}+

Dabei wird im Wesentlichen überprüft, ob die Position von der Eingabeposition aus erreichbar ist, indem die Vektordifferenz berechnet und anschließend überprüft wird, ob dies entweder oder für einige der Fälle der Fall [0 x]ist . IMO , dass Test ist die geschickteste Bit: Kräfte jede Anordnung in einem dieser Formate in die Form während Zuordnung zu , wo weder noch ist an ein Array mit drei Elementen, und oder zu . Dann prüft, ob wir haben .[x 0][x x]x > 00|$[0 x][0 0][0][a b]ab0[-x 0][-x -x][-x 0](!*,1=[0 x]

Zum Schluss 0]0=`wird der Fallback-Fall und die Formatierung für die Ausgabe ausgeführt.

Peter Taylor
quelle
4

Pyth 57 58 61 62

K1.618Jm,s*dKs*d*KKU39M<smf|}TJ}_TJm,-Ghb-Hebt^,0hk2U99 1

Probieren Sie es online aus.

Ziemlich ähnlich zu anderen Antworten, aber diese Wikipedia-Seite hat nicht viel anderes zu bieten;) Die magische Zahl 39ist die Anzahl der kalten Positionen mit Werten < 99.

Definiert eine Funktion g, die Sie gerne aufrufen können g 30 25. Kehrt []bei [(13,8)]Erfolg als Fehler zurück .

Erläuterung

K1.618                            : K=phi (close enough for first 39 values)
      Jm,s*dKs*d*KKU39            : J=cold positions with the form (small,big)
M<s                              1: Define g(G,H) to return this slice: [:1] of the list below 
   mf|}TJ}_TJ                     : map(filter: T or reversed(T) in J, where T is each member of..
             m,-Ghb-Hebt^,0hk2    : [(G H) - (0 x+1),(x+1 0) and (x+1 x+1)]
                              U99 : for each x from 0 - 98
FryAmTheEggman
quelle
swird in int umgewandelt - speichert ein paar Zeichen /____1. rZ39kann durch U39unären Bereich ersetzt werden. Ebenso können Sie ersetzen r99)mit U99.
Isaacg
@isaacg Danke! Ich habe es total vergessen U. Ich sollte die Erklärung wirklich aktualisieren: P
FryAmTheEggman
@isaacg Nur ein Gedanke an Pyth, ich denke, Sie könnten festlegen, dass eine Mengenkreuzung ausgeführt wird, @wenn das zweite Argument jetzt eine Liste ist. Es ist ein bisschen a
umständlich weggelassen
Das ist eine gute Idee - ich habe es umgesetzt. Ich habe auch den Kreuzungscode geändert, um einige Tricks zuzulassen, die vorher nicht möglich waren, einschließlich der Kreuzung von zwei Listen mit Listen.
isaacg
2

Javascript ES6 - 280 Bytes

Minimiert

r=x=>~~(x*1.618);g=(y,x)=>y(x)?g(y,x+1):x;s=A=>A?[A[1],A[0]]:A;f=(a,b)=>j([a,b])||j([a,b],1);j=(A,F)=>l(A,F)||s(l(s(A),F));l=(A,F)=>([a,b]=A,c=(F&&a+b>=r(b)&&(e=g(x=>a+b-2*x-r(b-x),0))?[a-e,b-e]:(e=g(x=>r(a+x)-2*a-x,0))+a<b?[a,a+e]:(e=r(b)-b)<a?[e,b]:0),c&&r(c[1]-c[0])==c[0]?c:0)

Erweitert

r = x => ~~(x*1.618);
g = (y,x) => y(x) ? g(y,x+1) : x;
s = A =>A ? [A[1],A[0]] : A;
f = (a,b) => j([a,b]) || j([a,b],1);
j = (A,F) => l(A,F) || s(l(s(A),F));
l = (A,F) => (
    [a,b] = A,
    c = (
        F && a+b >= r(b) && (e = g( x => a+b - 2*x - r(b - x), 0 )) ? [a-e,b-e] :
        (e = g( x => r(a+x) - 2*a - x, 0)) + a < b ? [a,a+e] :
        (e = r(b) - b) < a ? [e,b] : 0
    ),
    c && r(c[1] - c[0]) == c[0] ? c : 0
);

Netter und schneller Algorithmus. Läuft in O (n), aber ohne eine bytesparende Schleife in konstanter Zeit. Die Schleife ist als rekursiver Inkrementierer implementiert, daher schlägt das Skript möglicherweise mit einem Rekursionsfehler für n in den Hunderten oder Tausenden fehl . Verwendet die gleiche Beatty-Sequenzeigenschaft wie Mr. Taylor, aber anstatt die Sequenz zu berechnen, wird einfach zu den richtigen Begriffen gesprungen.

Läuft einwandfrei auf allen Testeingängen und vielen Dutzenden davon, die ich getestet habe.

Die aufzurufende Funktion ist f. Es gibt ein Array bei Erfolg und 0bei Aufgeben zurück.

COTO
quelle
Warten Sie, die Ausgabe eines Arrays ist in Ordnung?
John Dvorak
@ JanDvorak: xnor hat ein Tupel in der Liste der gültigen Ausgaben aufgeführt, daher habe ich es mir gedacht. Vielleicht kann er die Sache klären. Auf jeden Fall ist es eine triviale Lösung.
COTO
Ein Array oder ein Singleton-Array des Paares ist in Ordnung. Mehrfachgewinne gibt es nicht.
xnor
1

Perl 5 - 109 (mit 2 Flags)

#!perl -pl
for$a(@v=0..99){for$b(@v){$c=$a;$d=$b;${$:="$a $b"}||
map{$$_||=$:for++$c.$".++$d,"$a $d","$c $b"}@v}}$_=$$_

Verwendung:

$ perl wyt.pl <<<'3 5'

$ perl wyt.pl <<<'4 5'
1 2

Berechnet einfach die Lösung für jede mögliche Eingabe und führt dann eine einzelne Suche durch.

nutki
quelle