Can Alice win the game?

Question

Can Alice win the game?

The game's rules are as follows. First, a finite non empty set of positive integers \$X\$ is defined. Then, Alice and Bob take turns choosing positive integers, with Alice going first. Each integer must be strictly less than the previous one, and the game ends when one of the players chooses \$1\$.

Alice wins if the numbers she and Bob chose sum to a number in \$X\$, otherwise Bob wins.

Example games

Define \$X=\{20, 47\}\$. Alice chooses \$19\$, Bob chooses \$2\$, Alice chooses \$1\$. We have \$19+2+1=22\$ which is not in \$X\$ so Bob wins.

---

Define \$X=\{5, 6, 7, 8\}\$. Alice chooses \$4\$, Bob chooses \$3\$, Alice chooses \$1\$. We have \$4+3+1=8\$ which is in \$X\$ so Alice wins.

Challenge

Your challenge is to write a program or function without standard loopholes which, when given a collection of positive integers \$X\$, will output or produce some consistent value if Alice has a winning strategy, and a different consistent value if Alice does not have a winning strategy.

A winning strategy is a strategy which will let Alice win no matter how Bob plays.

Note that in the first example game Alice did not have a winning strategy: If her first choice was any number other than \$19\$ or \$46\$ then Bob could choose \$1\$ and win. On the other hand if her first choice was \$19\$ or \$46\$ then Bob could choose \$2\$ and win.

In the second example, Alice did have a winning strategy: After choosing \$4\$, she could choose \$1\$ after any of Bob's possible choices and win (or Bob could choose \$1\$ and she would win immediately).

Input and output

The input will be a collection of positive integers in ascending order, in any convenient format, given with any convenient input method. This collection represents the set \$X\$. The output will be one of two distinct values chosen by you, depending on whether or not Alice has a winning strategy with the given collection. Example IO:

Input    -> Possible Output
20 47    -> false
5 6 7 8  -> true
5 6 7 10 -> true (Alice chooses 4. If Bob chooses 3, Alice chooses 2; otherwise she chooses 1.)
5 6 7 11 -> false (A chooses n>6, B chooses n-1. A chooses 6 or 5, B chooses 2. A chooses 4, B chooses 3. A chooses n<4, B chooses 1.)

Rules

• No standard loopholes
• Shortest code in bytes wins

Note

This was the result of trying to make a finite version of the Banach Game.

Answer 1

JavaScript (ES6),  89 85 83  81 bytes

Takes input as a set. Returns either \$0\$ or \$1\$.

Note: Although it doesn't make sense from a theoretical perspective, the set is expected to be defined in ascending order so that the highest value appears at the end once it's converted back to an array.

f=(s,n=~[...s].pop(),b,t=0,g=i=>--i>n?b^f(s,i,!b,t-i)||g(i):0)=>~n?b^g``:s.has(t)

Try it online!

Commented

  f = (         // f is a recursive function taking:
    s,          //   s = input set
    n = ~[...s] //   n = opposite of the value played by the previous player,
        .pop(), //       or -(maximum value of the set + 1) for the first iteration
    b,          //   b = flag telling whether it's Bob's turn
    t = 0,      //   t = sum of all (positive) values played so far
    g = i =>    //   g is a recursive function taking a counter i <= 0
      --i > n ? //     decrement i; if i is greater than n:
        b ^     //       invert the result of the following call if it's Bob's turn
        f(      //       recursive call to g:
          s,    //         pass s unchanged
          i,    //         pass the new value of i
          !b,   //         invert the flag b
          t - i //         subtract i from the sum
        )       //       end of recursive call
        || g(i) //       if the above result is falsy, try a recursive call to g
      :         //     else:
        0       //       stop recursion
  ) =>          //
    ~n ?        // if n is not equal to -1:
      b ^ g``   //   invoke g with i = [''] (zero'ish)
                //   and invert the result if it's Bob's turn
    :           // else:
      s.has(t)  //   return true if t is in s (Alice wins), or false otherwise

Answer 2

R, 86 83 bytes

-1 byte by using !m instead of m<1; -1 byte by realizing I only need one long OR || (the first one can be a short OR |); -1 byte by toggling B and using subtraction instead of equality of booleans.

a=function(x,m=max(x),B=T)!m|all(x-1)-B||any(sapply(1:m,function(y)!a(x-y,y-1,!B)))

Try it online!

Exhaustive recursive search. Takes input as a vector. Outputs TRUE or FALSE.

At each step, subtracts the value chosen by the player from all the values in the set x.

Alice wins if at her turn, the updated x includes 1. Bob wins if at his turn, the updated x does not include 1. To this end, the function includes a boolean B, worth TRUE when Alice plays and FALSE when Bob plays, and checks all(x != 1) != B. If this condition is verified then the player wins, else the player wins if there is a move which makes the other player lose (last condition in the code, uses recursion).

The initial !m (equivalent to m!=0) is there to check whether at the last move, the other player played 1 even though it is a losing move.

Edit: Arnauld added an explanation to his JavaScript answer while I was typing; it seems we have similar algorithms.

Answer 3

Jelly, 37 36 bytes

Ḣ’,_@ɗ€Ḣ;€CÑ€¬Ẹ
1ǬḢoḊ’Ạ=ɗ/$Ʋ?
Ṁ,;0Ç

Try it online!

Translation of @RobinRyder’s R solution so be sure to upvote that one!

Answer 4

Python 2, 102 101 100 bytes

f=lambda A,t=0,s=1,m=0:t<1if(s in A)^t else[any,all][t](f(A,1-t,s+i,i)for i in range(2,m or max(A)))

Try it online!

Returns True/False for if Alice has a winning strategy.

Recurses alternating between Alice and Bob (with t==0/1, respectively). s-1 is the running sum of choices so far; and m-1 is the maximum integer value allowed for a player to choose.

If s is in A and it's Alice's turn, she wins by choosing 1. If s is not in A and it's Bob's turn, he would choose 1 and Alice loses. In both cases, that would stop the recursion.

Otherwise, if m==0, then this is Alice's first turn; and she cannot win if she chooses a value greater than or equal to max(A).

If it is Alice's turn, then she can win if there is any valid integer choice that eventually ends up winning.

Conversely, on Bob's turn, Alice wins only if none of Bob's possible choices guarantee eventually in a loss for Alice; which is to say that Alice wins on Bob's turn only if all his choices eventually yield an Alice win.