The Japanese game Oshi-Zumo, a two-player, zero-sum game of incomplete information, is analyzed to determine its Nash-optimal mixed strategies. While previous research identified pure winning strategies for specific game states, this analysis completes the game’s resolution by computing the optimal mixed strategies required for complex positions where pure strategies are insufficient. The study demonstrates that these strategies can be calculated efficiently using linear programming on standard hardware.
The methodology involves using dynamic programming to evaluate game states and linear programming to solve for optimal move distributions. To address numerical instability encountered with standard solvers, the implementation utilizes a two-phase approach that defaults to rational arithmetic via the GNU arbitrary precision library when floating-point calculations prove unreliable. This approach successfully computes the Nash-optimal strategy for the standard 50-coin, 3-location game in approximately 12 seconds on a 1-GHz processor.
Key findings reveal that Nash-optimal strategies in Oshi-Zumo often exhibit an "odd-even" probability pattern in bid selection, though the underlying cause remains an open question. Tournament simulations against various heuristic algorithms indicate that while a Nash-optimal player is theoretically sound, it is not inherently exploitative. Simple, hand-crafted strategies can perform surprisingly well against a Nash-optimal opponent, suggesting that the game serves as an effective, computationally manageable testbed for developing adaptive, exploitative AI agents. By bridging the gap between simple games like Rock-Paper-Scissors and complex, high-stakes environments like Poker, Oshi-Zumo provides a valuable framework for studying game-theoretic decision-making and the development of stronger-than-human game AI.
