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)    

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).

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.

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

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.

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.