Oracular Form and Computing Strong Game-Theoretic Jotto Strategies
Sam Ganzfried · arXiv (Cornell University) · 2011
We develop a new approach that computes approximate equilibrium strategies in Jotto, a popular word game. Jotto is an extremely large two-player game of imperfect information; its game tree has many orders of magnitude more states than games previously studied, including no-limit Texas Hold'em poker. To address the fact that the game is so large, we propose a novel strategy representation called oracular form, in which we do not explicitly represent a strategy, but rather appeal to an oracle that quickly outputs a sample move from the strategy's distribution. Our overall approach is based on an extension of the fictitious play algorithm to this oracular setting. We make several interesting observations from the computed strategies and demonstrate the superiority of our algorithm over a benchmark algorithm.