16
\$\begingroup\$

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)    
\$\endgroup\$
  • 2
    \$\begingroup\$ +1, partly because I like the idea of a quarter of infinity. \$\endgroup\$ – Level River St Nov 28 '14 at 9:57
  • \$\begingroup\$ define "reasonable amount of time". Is several seconds for (100,50) a reasonable amount of time? \$\endgroup\$ – John Dvorak Nov 28 '14 at 11:35
  • \$\begingroup\$ Oh. Wait. the input is bounded by... 30??? That's a bit low, isn't it? \$\endgroup\$ – John Dvorak Nov 28 '14 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 Nov 28 '14 at 11:51
  • \$\begingroup\$ @PeterTaylor Thanks, fixed. \$\endgroup\$ – xnor Nov 28 '14 at 11:51
6
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Seems that "So, an exponential recursive game tree search will not suffice" was optimistic, because what you describe sounds exactly like that. \$\endgroup\$ – Peter Taylor Nov 28 '14 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\$ – John Dvorak Nov 28 '14 at 13:02
  • \$\begingroup\$ It's ok, I believe you. \$\endgroup\$ – Peter Taylor Nov 28 '14 at 14:13
  • \$\begingroup\$ you can remove the x@ from x@(a,b)?p=... \$\endgroup\$ – proud haskeller Nov 29 '14 at 10:19
  • \$\begingroup\$ Not sure how it got there. Fixing, thanks. \$\endgroup\$ – John Dvorak Nov 29 '14 at 10:35
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\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 Dec 1 '14 at 12:55
  • \$\begingroup\$ @isaacg Thanks! I totally forgot about U. I should really update the explanation :P \$\endgroup\$ – FryAmTheEggman Dec 1 '14 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\$ – FryAmTheEggman Dec 2 '14 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 Dec 3 '14 at 2:09
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wait, outputting an array is ok? \$\endgroup\$ – John Dvorak Nov 28 '14 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 Nov 28 '14 at 16:04
  • \$\begingroup\$ An array or a singleton array of the pair is fine; multiple winning moves are not. \$\endgroup\$ – xnor Nov 28 '14 at 22:14
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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