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.


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.


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)    
  • 2
    \$\begingroup\$ +1, partly because I like the idea of a quarter of infinity. \$\endgroup\$ Commented Nov 28, 2014 at 9:57
  • \$\begingroup\$ define "reasonable amount of time". Is several seconds for (100,50) a reasonable amount of time? \$\endgroup\$ Commented Nov 28, 2014 at 11:35
  • \$\begingroup\$ Oh. Wait. the input is bounded by... 30??? That's a bit low, isn't it? \$\endgroup\$ Commented Nov 28, 2014 at 11:46
  • \$\begingroup\$ @JanDvorak You're right, it might allow cheap shortcuts. Changed to 99 -- I think that suffices? Apologies for editing specs after posting. \$\endgroup\$
    – xnor
    Commented Nov 28, 2014 at 11:51
  • \$\begingroup\$ @PeterTaylor Thanks, fixed. \$\endgroup\$
    – xnor
    Commented Nov 28, 2014 at 11:51

5 Answers 5


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


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)


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)

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

  • \$\begingroup\$ Seems that "So, an exponential recursive game tree search will not suffice" was optimistic, because what you describe sounds exactly like that. \$\endgroup\$ Commented Nov 28, 2014 at 12:56
  • \$\begingroup\$ @PeterTaylor this is O(n^4). Each cold pair takes O(n^3) time to find and there are O(n) of them. Optimising the generation would bring it to O(n^2) (if I read the sequence correctly). An exponential-time algorithm would be much slower. Should I run some tests? \$\endgroup\$ Commented Nov 28, 2014 at 13:02
  • \$\begingroup\$ It's ok, I believe you. \$\endgroup\$ Commented Nov 28, 2014 at 14:13
  • \$\begingroup\$ you can remove the x@ from x@(a,b)?p=... \$\endgroup\$ Commented Nov 29, 2014 at 10:19
  • \$\begingroup\$ Not sure how it got there. Fixing, thanks. \$\endgroup\$ Commented Nov 29, 2014 at 10:35

GolfScript (63 57 bytes)


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



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


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.


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.


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
  • \$\begingroup\$ s is cast to int - saves a few characters over /____1. rZ39 can be replaced by U39, using unary range. Likewise, you can replace r99) with U99. \$\endgroup\$
    – isaacg
    Commented Dec 1, 2014 at 12:55
  • \$\begingroup\$ @isaacg Thanks! I totally forgot about U. I should really update the explanation :P \$\endgroup\$ Commented Dec 1, 2014 at 13:38
  • \$\begingroup\$ @isaacg Just a thought about Pyth, I think you could make @ perform set intersection if its second argument is a list now. It's a bit awkwardly left out since a was changed :P \$\endgroup\$ Commented Dec 2, 2014 at 14:56
  • \$\begingroup\$ That's a good idea - I've implemented it. I also changed the intersection code to allow a few tricks that weren't possible before, including taking the intersection of two lists of lists. \$\endgroup\$
    – isaacg
    Commented Dec 3, 2014 at 2:09

Javascript ES6 - 280 bytes




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.

  • \$\begingroup\$ Wait, outputting an array is ok? \$\endgroup\$ Commented Nov 28, 2014 at 15:45
  • \$\begingroup\$ @JanDvorak: xnor has a tuple listed in the list of valid outputs, hence I figured so. Maybe he can clarify the matter. It's a trivial fix, at any rate. \$\endgroup\$
    – COTO
    Commented Nov 28, 2014 at 16:04
  • \$\begingroup\$ An array or a singleton array of the pair is fine; multiple winning moves are not. \$\endgroup\$
    – xnor
    Commented Nov 28, 2014 at 22:14

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}}$_=$$_


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.