"Games against Nature" [Papadimitriou '85] are two-player games of perfect information, in which one player's moves are made randomly (here, uniformly); the final payoff to the non-random player is given by some $[0, 1]$-valued function of the move history. Estimating the value of such games under optimal play, and computing near-optimal strategies, is an important goal in the study of decision-making under uncertainty, and has seen significant research in AI and allied areas [Hnich, Rossi, Tarim, Prestwich '11], with only experimental evaluation of most algorithms' performance. The problem's PSPACE-completeness does not rule out nontrivial algorithms. Improved algorithms with theoretical guarantees are known in various cases where the payoff function $F$ has special structure, and Littman, Majercik, and Pitassi [LMP'01] give a sampling-based improved algorithm for general $F$, for turn-orders which restrict the number of non-random player strategies.

We study the case of general $F$ for which the players strictly alternate with binary moves $(w_1, r_1, w_2, r_2, \ldots, w_{n/2}, r_{n/2})$---for which the approach of [LMP'01] does not improve over brute force. We give a randomized algorithm to approximate the value of such games under optimal play, and to execute near-optimal strategies. Our algorithm achieves exponential savings over brute-force, making $2^{(1 - \delta) n}$ queries to $F$ for some absolute constant $\delta > 0$, and certifies a lower bound $\hat{v}$ on the game value $v$ with additive expected error bounded as $E[v - \hat{v}] \leq \exp(-\Omega(n))$. (On the downside, $\delta$ is tiny and the algorithm uses exponential space.)

Our algorithm is recursive, and bootstraps a "base case" algorithm for fixed-size inputs. The method of recursive composition used, the specific base-case guarantees needed, and the steps to establish these guarantees are interesting and, we feel, likely to find uses beyond the present work.