TL;DR
This paper introduces a general theoretical framework for finding and proving optimal strategies in guessing games, moving beyond brute-force search. By developing novel theorems and lower-bounding techniques, the authors demonstrate how to mathematically guarantee a strategy's optimality, showcasing this with a rigorous analysis of the popular game Wordle.
What Problem Does This Paper Address?
Guessing games, like the popular Wordle, present a fascinating challenge: how can a player (or an AI agent) deduce a hidden secret (e.g., a word) using a series of limited guesses and feedback clues? While many strategies exist, proving their absolute optimality is computationally prohibitive due to the vast search space. Existing work often focuses on specific games like Mastermind or relies on heuristics that don't guarantee optimality. This paper aims to bridge this gap by developing a general, mathematically rigorous method to find and prove optimal strategies for any guessing game, using Wordle as a primary example.
Methods
The authors build a theoretical foundation for guessing games, defining them formally as a tuple of guess sets, secret sets, response sets, an affirmative response, and an answering function. They introduce the concept of "candidate sets" which represent the possible secrets remaining given the history of guesses and responses.
Key methodological contributions include:
- Valuations and Combined Valuations: Building on existing "valuation" functions (which score guesses based on how well they reduce the candidate set), the paper explores combining multiple valuations to find better strategies. They systematically test combinations to identify effective heuristics.
- Lower Bounding Techniques: The core of their contribution lies in developing novel theorems and techniques to establish lower bounds for the minimum number of turns required to solve a game. This involves concepts like "useful guesses" (guesses that are guaranteed to reduce the candidate set in a non-trivial way) and "strategy trees" (visualizing a strategy as a tree where nodes are guesses and branches are responses).
- Recursive Lower Bounds: They introduce a series of lower bounds (LB1, LB2, etc.) and corresponding value estimates (V1, V2, etc.) that recursively approximate the true minimum number of turns. These bounds are designed to converge to the true optimal value, allowing for proof of optimality without exhaustive search.
- Filtering for Optimality: The paper outlines a process where these lower bounds are used to "filter" potential starting guesses. If a guess's estimated optimal value exceeds a known upper bound for the game, it can be ruled out as part of an optimal strategy.
Datasets
The paper uses the Wordle game as its primary example. The "datasets" in this context are the sets of allowable guesses ($G_w$) and secrets ($S_w$). The authors mention using the original Wordle sets where $|G_w| = 12972$ and $|S_w| = 2315$. They also apply their methods to variants like FFXIVrdle, Mininerdle, Nerdle, and Primel, noting their respective guess and secret set sizes.
Key Insights and Ideas
- Generalizability: The framework is designed to be game-agnostic, applicable to any guessing game that fits the defined structure, not just Wordle.
- Beyond Brute Force: The most significant insight is the development of a method to prove optimality without needing to explore every possible game state, which is computationally infeasible for most non-trivial games.
- The Power of Lower Bounds: By establishing rigorous lower bounds on the minimum number of turns, the authors can effectively prune the search space and identify truly optimal strategies.
- Strategy Trees as a Proof Tool: Visualizing strategies as trees provides an intuitive way to understand the game's structure and develop the mathematical proofs for optimality.
- Combined Valuations Outperform Single Ones: The empirical results show that combining multiple heuristics (valuations) leads to significantly better strategies than relying on any single one.
Key Results
- The paper successfully identifies an optimal strategy for Wordle, achieving a total score (sum of turns over all secrets) of 7920.
- They demonstrate that the strategy found using their combined valuation approach (specifically, a combination involving MOSTPARTS, INSET, and EXPSIZESPLIT) is indeed provably optimal.
- The method was also applied to several Wordle variants (FFXIVrdle, Mininerdle, Nerdle, Primel), confirming the optimality of the strategies found for these games as well.
- The paper provides a theoretical framework and theorems that can be used to prove the optimality of strategies for any general guessing game.
Limitations and Future Work
- Deterministic Strategies: The current work focuses on deterministic strategies, where the next guess is always uniquely determined. The authors acknowledge that future work could explore non-deterministic strategies.
- Answering Function: The current framework assumes a deterministic answering function (the teacher always gives the same response for a given guess and secret). Future work could extend this to handle non-deterministic answering functions.
- Efficiency of Estimating Functions: While the developed estimating functions (Vi) converge to the true optimal value, the authors suggest exploring faster-computing functions that converge in fewer iterations.
- Applications: The authors hope their theorems can aid in applications related to guessing games, meta-reasoning, and the development of "discriminatory" predicates for AI.
Summary updated