Will Alice win in this Stick Bomber game?

Question

Background

Stick Bomber is a two-player game I just made up. Initially, some sticks are placed in one or more groups, and the sticks in each group are laid out in a straight line. So a configuration with three groups of 3, 5, and 8 sticks each may look like the following. For conciseness, we can call it a (3,5,8) configuration.

|||  |||||  ||||||||

Let's call the two players Alice (the one who plays first) and Bob (second). At each turn, the player selects one stick anywhere on the board, and removes that stick along with the ones directly adjacent to it (left or right within the group).

For example, if Alice chooses the 3rd stick in the 5-stick group, the board becomes (3,1,1,8) (sticks removed in the middle split the group into two):

|||  |xXx|  ||||||||

Then, if Bob chooses the first stick in the 8-stick group, the board becomes (3,1,1,6):

|||  |  |  Xx||||||

Then if Alice chooses the 2nd stick in the 3-stick group, that group is entirely removed and the state becomes (1,1,6):

xXx  |  |  ||||||

The one who eliminates all the sticks from the board wins the game.

For single-pile initial states, Alice can win in 1 turn for (1) through (3), and (5) in three turns by removing the middle. However, Alice cannot win for (4) because any move will result in a (1) or (2), where Bob can win in 1 turn.

Challenge

Given an initial configuration of Stick Bomber, determine whether Alice can win the game. Assume that both Alice and Bob play perfectly, i.e. each player always plays a winning move whenever possible.

The input is guaranteed to be a non-empty sequence of positive integers, but it is not guaranteed to be sorted. For output, you can choose to

1. output truthy/falsy using your language's convention (swapping is allowed), or
2. use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

Single-group configurations

For n < 70, Alice wins for (n) unless n is one of the following. This result was generated using this Python code. This sequence and its inversion (the list of n's where Alice wins) are not yet part of the OEIS.

4, 8, 14, 20, 24, 28, 34, 38, 42, 54, 58, 62

Multi-group truthy

[2, 9] [3, 5] [3, 7] [3, 9] [7, 8]
[1, 2, 7] [1, 8, 9] [3, 8, 9] [6, 7, 9] [7, 8, 9]
[1, 3, 6, 6] [1, 4, 4, 9] [1, 5, 6, 7] [2, 5, 6, 7] [3, 4, 8, 9]

Multi-group falsy

[1, 6] [1, 7] [4, 4] [5, 5] [5, 9]
[1, 7, 8] [2, 3, 9] [3, 3, 4] [4, 5, 9] [8, 9, 9]
[1, 2, 4, 4] [1, 4, 4, 7] [2, 2, 5, 9] [2, 6, 6, 7] [3, 4, 7, 9]

Answer 1

JavaScript (Node.js), 110 101 99 90 bytes

Thanks to @tsh for -9 bytes!

g=s=>s.some((a,i)=>!a&&!g(t=[...s],t.splice(i-1,3,1)))
i=>g(i.flatMap(n=>[1,...Array(n)]))

Try it online! (with test cases)

Answer 2

Python 2, 84 bytes

f=lambda a:0in[f(a[:i]+[v-1,x-v-2]+a[i+1:])for i,x in enumerate(a)for v in range(x)]

Try it online!

Answer 3

Jelly, 17 16 bytes

ḟⱮ’r‘Ɗ߀Ạ¬
Rj0TÇ

Try it online!

Slow as hell.

Explanation

Rj0TÇ    Main link.
             [1, 3, 5]
R          For each n in the array, create an array of n sticks.
             [[1], [1, 2, 3], [1, 2, 3, 4, 5]]
 j0        Join by 0 (non-sticks).
             [1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5]
   T       Indices of truthy values (sticks).
             [1, 3, 4, 5, 7, 8, 9, 10, 11]
    Ç      Call the helper link.

ḟⱮ’r‘Ɗ߀Ạ¬    Helper link.
 Ɱ     €        For each stick n in the array:
  ’               n-1
    ‘             n+1
   r              Inclusive range [n-1,n,n+1]
ḟ                 Remove those three sticks if present
      ß           Call this link recursively on the remainder
        Ạ       See if there is nothing or only 1's in the list
                (i.e. if the opponent won before this turn, or can
                force a victory whatever we do)
         ¬      Invert to see if we can force a victory from here

Answer 4

JavaScript, 72 bytes

f=a=>a.some(g=(v,i,a)=>v-->0&&!f(b=[...a,v-1,a[i]-v-2],b[i]=0)+g(v,i,a))

Try it online!

A port of current Python answer by dingledooper.

Answer 5

Charcoal, 63 bytes

⊞υ⮌⌕Ａ⪫ＸχＡω0ＦυＦι⊞υ⁻ι…·⊖κ⊕κ≔⟦⟧ζＷ⁻υＥζ§κ⁰⊞ζ⟦⌊ι⊙⌊ι№ζ⟦⁻⌊ι…·⊖κ⊕κ⁰⟧⟧⊟⊟ζ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a winning position, nothing for a losing position. Explanation:

⊞υ⮌⌕Ａ⪫ＸχＡω0

Start enumerating all positions reachable from the starting position, which is calculated by taking 10 to the power of the input groups, concatenating the result, and taking the indices of the 0s from highest to lowest (i.e. reverse of the usual order).

ＦυＦι⊞υ⁻ι…·⊖κ⊕κ

For each position and stick, calculate the result of bombing that stick and add the result to the list of reachable positions.

≔⟦⟧ζＷ⁻υＥζ§κ⁰

Enumerate the list of reachable positions in ascending order, so that all positions reachable from a given position have been enumerated before that position. Additionally, the enumeration deduplicates the positions.

⊞ζ⟦⌊ι⊙⌊ι№ζ⟦⁻⌊ι…·⊖κ⊕κ⁰⟧⟧

For each position, check whether any play results in a losing position. Push that position plus the win flag to the enumeration.

⊟⊟ζ

Output the win flag for the original position.