Simultaneous AlphaZero: Extending Tree Search to Markov Games

Abstract

Many strategic planning problems require agents to act simultaneously, making turn-based search unsuitable and requiring a normal form game to be solved at each tree state. We introduce Simultaneous AlphaZero, a learning and search method for continuous-state, two-player zero-sum deterministic Markov games. A learned value function bootstraps finite-depth regret-matching search, while approximate regret transfer uses learned regret and average-strategy functions to warm start the local solver at deployment. We establish complementary guarantees for both components. First, we show that even a shallow finite-depth solver contracts errors in its learned frontier values, and we bound how local solution and value-fitting errors propagate through repeated learning and search. Second, imperfect regret and average-strategy transfer yields a finite-time approximate-equilibrium bound decomposing ordinary regret, game mismatch, regret-fitting error, and strategy-fitting error; any fixed finite warm start preserves the solver's asymptotic no-regret guarantee. Experiments in continuous Dubins pursuit-evasion and satellite custody maintenance compare unguided, value-only, and fully transferred search in direct solver cross-play. Across both domains, oracle-guided search generally improves performance over unguided search, demonstrating effective game-theoretic planning in large continuous state spaces.