Winning Strategies for a String Construction Game
Python, 132

def f(S,n):
 if n&lt;1:return S
 a,b=[f({x[1:]for x in S if x[0]==c},n-1)for c in'01']
 return{'A'+y for y in a|b}|{'B'+y for y in a&amp;b}


Example run: 

f({'000','001','010','011','100','101','110','111'},3) == 
{'ABA', 'ABB', 'AAA', 'AAB', 'BBB', 'BBA', 'BAB', 'BAA'}


This is only kind-of golfed, mostly to show the algorithm. The inputs and output are sets of strings. Python doesn't seem to have the right features to express parts of this compactly, so it would be cool if someone wrote this in a better-suited language.

Here's how the recursion can be expressed mathematically. Unfortunately, PPCG still lacks math rendering, so I'll have to use code blocks. 

The objects of interest are sets of strings. Let | represent set union and &amp; represent set intersection.

If c is a character, let c#S represent prepending the character c to all strings in S. Conversely, let the contraction c\S be the one-character-shorter strings of S that follow initial character c, e.g., 0\{001,010,110,111} = {01,10}.

We can uniquely split a set of strings S with chars in 01 by their first character.

S = 0#(0\S) | 1#(1\S)


Then, we can express the desired function f as follows, with the bases cases in the first two lines and the recursive can in the last line:

f({})   = {}
f({''}) = {''}
f(S)    = A#(f(0\S)|f(1\S)) | B#(f(0\S)&amp;f(1\S))


Note that we don't need to use the length n.

Why does this work? Let's think about the move-strings that let Alice win for a set of strings S. 

If the first character is A, Alice can pick the first move ('0' or '1'), letting her choose to reduce the problem to S0 or S1. So now the remaining move-string has to be in  at least one of f(S0) or f(S1), hence we take their union |. 

Similarly, if the first character is 'B', Bob gets to pick, and he'll pick the worse one for Alice, so the remaining move-string must be in the intersection (&amp;).

The base cases simply check if S is empty or not at the end. If we're tracking the length of the strings n, by subtracting 1 each time we recurse, the bases can instead be written:

f(S) = S if n==0


The recursive solution also explains the fun fact that f(S) has the same size as S. It's true for the base cases, and for the inductive case

f(S) = A#(f(0\S)|f(1\S)) | B#(f(0\S)&amp;f(1\S))


we have

size(f(S)) = size(A#(f(0\S)|f(1\S)) | B#(f(0\S)&amp;f(1\S)))
           = size(A#(f(0\S)|f(1\S))) + size(B#(f(0\S)&amp;f(1\S))))
           = size((f(0\S)|f(1\S))) + size((f(0\S)&amp;f(1\S))))
           = size(f(0\S)) + size(f(1\S))  [since size(X|Y) + size(X&amp;Y) = size(X) + size(Y)]
           = size(0\S) + size(1\S)
           = size(S)