I tried coming up with a two player game with an exponential number of choices at each step, but a polynomially limited game length. Here is my idea:
The game is played on a graph that is an $n$-dimensional hypercube where each vertex is represented by an $n$-tuple in $\{0,1\}^n$.
Additionally we initialize a set of marked vertices $M= \emptyset$
Lastly, we introduce a function $next : \{0,1\}^n \to 2^{\{0,1\}^n}$ such that $u \in next(v) \iff dist(u,v) = \lfloor n/2 \rfloor$ where $dist$ is the minimum length of a path in the graph connecting $u$ and $v$.
Players alternate turns with player 1 starting. At each turn the following steps happen:
- player picks a node $v$ s.t. $next(v) \cap M = \emptyset$
- update $M$ in the following way: $M := M \cup next(v)$
This continues until a player can no longer choose a $v$ in step 1. The first player that can not pick such a node loses.
Now at first glance this seems like it satisfies my original requirements.
The number of choices in each steps is only bounded by $2^n$ which is clearly exponential.
It is easy to show that $|next(v)|=\binom{n}{n/2}$ as to obtain a vertex that has exactly distance $n/2$ to $v$ you would have to "flip" $n/2$ of the $n$ components defining $v$.
As $next(v) \cap M = \emptyset$ we know that $M := M \cup next(v)$ increases the size of $M$ by exactly $|next(v)|=\binom{n}{n/2}$.
Clearly the size of $M$ is bound by $2^n$. As in each step we add $\binom{n}{n/2}$ vertices to $M$, the game can last at most $2^n/\binom{n}{n/2}$ rounds.
Using that $\forall i: \binom{n}{n/2} \geq \binom{n}{i}$ we get $2^n = \sum_{i=0}^n \binom{n}{i} \leq \sum_{i=0}^n \binom{n}{n/2} = n \binom{n}{n/2}$ and thus can conclude that the game lasts for at most $n$ rounds, i.e. is polynomially bounded. Looking at the graph for exactly $2^n/\binom{n}{n/2}$ I think it's even logarithmic.
Now my question is whether there is a way to formulate a winning strategy for this game that is not simply traversing this exponentially branching game tree.
That could either be to find an equivalent game that is only finitely branching (perhaps using symmetry?) or even giving a closed form of the set of dimensions for which player 1 has a winning strategy.
Further, what about variations of the game? How would rounding up $n/2$ affect the result for odd $n$? What if we initialize $M$ in the input?
I find it quite hard to get a grasp or feeling about this problem since the maximum number of moves grows very slowly. Even for just $8$ moves you'd require $41$ dimensions and thus $2^{41}$ vertices.
However I think it is at least not necessary to keep track of all these $2^{41}$ vertices. I believe it should be enough to collect the picked vertices in a set $P$ to then find that $next(v) \cap M = \emptyset \iff \not\exists p\in P: dist(v,p) \leq n \text{ and } dist(v,p) \text{ is even}$
But even with this I haven't found any approach to figure out whether this game becomes interesting for large $n$.
Although counting the increase in size of $M$ indicates that the game ends after at most $2^n/\binom{n}{n/2}$ moves (which is $O(\sqrt n)$), we can say more: the game ends after $2$ moves. The first player always loses.
Lemma. If $v,w$ disagree in an even number of positions, then $\operatorname{next}(v) \cap \operatorname{next}(w) \ne \varnothing$, and therefore, after $v$ is played, $w$ cannot be played.
Proof. First, construct a "midpoint" $x$ between $v$ and $w$ by starting at $v$, looking at the $2k$ positions where $v$ and $w$ disagree, and flipping any $k$ of them. Now $d(x,v) = d(x,w) = k$. Then, starting at $x$, look at the $n-2k$ positions where $v$ and $w$ agree, and flip them one at a time. This increases the distance from both $v$ and $w$ by $1$, so that distance increases from $k$ to $k+1$ to $k+2$ and so on up to $k + (n-2k) = n-k$.
As a result, we've found points that are equidistant from $v$ and $w$, and at each distance between $k$ and $n-k$ from both. We have $2k \le n$, so $k \le \lfloor \frac n2\rfloor$ and $n-k \ge \lfloor \frac n2 \rfloor$; therefore one of these points is at a distance of exactly $\lfloor \frac n2\rfloor$ from both $v$ and $w$. This point is in $\operatorname{next}(v) \cap \operatorname{next}(w)$. $\qquad\square$
No matter what vertex $v$ the first player makes, adding $\operatorname{next}(v)$ to $M$ will forbid all vertices at an even distance from $v$, by the lemma. Effectively, if $v$ has an even number of $1$s in it, then all other vertices with an even number of $1$s are forbidden; if $v$ has an odd number of $1$s, then all other vertices with an odd number of $1$s are forbidden.
The second player's move must choose a vertex $w$ of the opposite parity, but this forbids all other possible plays.
Now, the first player loses, because there are no possible moves left.