Play Wythoff's Nim perfectly

Question

Your goal is to write a perfect player for the game of Wythoff's Nim.

Rules of Wythoff's Nim

Wythoff's Nim is a deterministic two-player game played with two piles of identical counters. Players alternate turns, in which they do one of these:

1. Remove one or more counters from the first pile
2. Remove one or more counters from the second pile
3. Remove an equal number of counters (one or more), from both the first pile and the second pile.

Of course, piles can't go negative, but they can to 0. Whichever player removes the last counter overall wins the game.

For the more geometrically-minded, here is an equivalent formulation of the game that you can play on this applet. A single queen starts on some square of a quarter-infinite chessboard whose corner is in the bottom-left. Players alternate moving the queen, which moves like a chess queen but restricted to three directions:

1. Down
2. Left
3. Diagonally down and left

Whoever moves the queen to the corner wins.

Associating the queen's coordinates (with corner (0,0)) to the sizes of the respective piles, it's easy to see both games are the same.

Perfect play

(You can skip this if familiar with the notions of perfect play and winning moves.)

Since Wythoff's Nim is a finite and deterministic game, it has a notion of perfect play. A perfect player is a strategy that will always win from a theoretically won position, meaning a position in which there exists a strategy that guarantees a win.

To be a winning strategy, it suffices to move to always move to a theoretical winning position for the player who just moved, and thus the player not going next. The first of these winning positions (also called cold positions) are (0,0), (1,2), (2,1), (3,5), (5,3). See the Wikipedia article for an explanation of an algorithm to find a winning strategy for Wythoff's Nim, as well as a formula to generate win positions.

Program requirements

Write a program or function takes a position as input and outputs a winning move in the form of the position after that move. Fewest bytes wins.

If no winning move exists, i.e., the position is a theoretical loss, your program should indicate so and forfeit.

Your program must run within a reasonable amount of time. So, an exponential recursive game tree search will not suffice. If you want to precompute and hard-code a strategy, that's fine.

Input

A pair (i,j) of non-negative numbers representing pile sizes, each at most 99. This can be two numbers, a tuple, a list, or whatever container you prefer.

Output

Print or output the position after your move, again as two numbers or a container thereof. This must be a legal move to a winning position. If there's multiple such moves, any one is fine, but only one.

If there's no winning move, you must indicate this in the output. Any output like False, None, 0, or (-1,-1) will do, as long as it's not a legal position, and is the same for every losing input.

Example runs

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)    

Answer 1

Haskell, 167 165 characters

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

The algorithm is inefficient, but it still runs within a second (though not in the interactive console) for inputs < 100.

Explanation:

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

The list of cold positions given a set of previous cold positions is one cold position followed by the list of cold positions given this position and the previous ones (Inefficiency: this position is generated twice)

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

One cold position is the first pair such that there are no cold positions reachable from that pair (Inefficiency: we should search from the previous pair instead)

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

Positions reachable from a pair are those such that their first elements match, their second elements match, their difference matches, or the smaller heap before removal is the larger heap after removal.

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

(main method) If the heaps are in the wrong order, swap them. Else, if the first cold position reachable from a position is the position itself, indicate failure (ideally, one would return Maybe (Int,Int) instead). Else return that cold position (Inefficiency: said pair is looked up twice. Worse, the list of cold positions is generated twice)

Answer 2

GolfScript (63 57 bytes)

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

Expects input from stdin in the form [a b], and leaves output on stdout in that form or 0 if it's a losing position. Online demo

Overview

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

computes a list of cold positions (including the flipped version [b a] for each cold position [a b]) using the Beatty sequence property.

Then ? searches for the first cold position satisfying the block created by

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

which basically checks that the position is reachable from the input position by computing the vector difference and then verifying that it's either [0 x], [x 0], or [x x] for some x > 0. IMO that test is the cleverest bit: 0|$ forces any array in one of those formats into the form [0 x] while mapping [0 0] to [0], [a b] where neither a nor b is 0 to a three-element array, and [-x 0] or [-x -x] to [-x 0]. Then (!*,1= checks that we have [0 x].

Finally 0]0=` does the fallback case and formatting for output.

Answer 3

Pyth 57 58 61 62

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

Try it online.

Pretty similar to other answers, but that wikipedia page didn't give much else to go on ;) The magic number 39 is the number of cold positions with values < 99.

Defines a function g that you can call like g 30 25. Returns [] for failure, [(13,8)] on success.

Explanation

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

Answer 4

Javascript ES6 - 280 bytes

Minified

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)

Expanded

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

Nice and quick algorithm. Runs in O(n), but would run in constant time if not for a byte-saving loop. The loop is implemented as a recursive incrementer, hence the script will eventually fail with a recursion error for n in the hundreds or thousands. Uses the same Beatty sequence property that Mr. Taylor mentions, but rather than computing the sequence, it simply steps up to the correct term(s).

Runs properly on all of the test inputs and many dozens besides that I tested.

The function to invoke is f. It returns an array on success and a 0 upon giving up.

Answer 5

Perl 5 - 109 (with 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}}$_=$$_

Usage:

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

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

Simply calculates solution for each possible input then just does a single lookup.