On Optimal Strategies for Wordle and General Guessing Games
- URL: http://arxiv.org/abs/2305.09111v1
- Date: Tue, 16 May 2023 02:30:10 GMT
- Title: On Optimal Strategies for Wordle and General Guessing Games
- Authors: Michael Cunanan and Michael Thielscher
- Abstract summary: We develop a method for finding optimal strategies for guessing games while avoiding an exhaustive search.
This work is developed to apply to any guessing game, but we use Wordle as an example to present concrete results.
- Score: 6.85316573653194
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The recent popularity of Wordle has revived interest in guessing games. We
develop a general method for finding optimal strategies for guessing games
while avoiding an exhaustive search. Our main contributions are several
theorems that build towards a general theory to prove the optimality of a
strategy for a guessing game. This work is developed to apply to any guessing
game, but we use Wordle as an example to present concrete results.
Related papers
- Guessing Winning Policies in LTL Synthesis by Semantic Learning [0.0]
We provide a learning-based technique for guessing a winning strategy in a parity game originating from an synthesis problem.
Not only can the guessed strategy be applied as best-effort in cases where the game's huge size prohibits rigorous approaches, but it can also increase the scalability of rigorous synthesis in several ways.
arXiv Detail & Related papers (2023-05-24T12:57:53Z) - Learning to Play Stochastic Two-player Perfect-Information Games without
Knowledge [5.071342645033634]
We extend the Descent framework, which enables learning and planning in the context of two-player games with perfect information.
We evaluate them on the game Ein wurfelt! against state-of-the-art algorithms.
It is our generalization of Descent which obtains the best results.
arXiv Detail & Related papers (2023-02-08T20:27:45Z) - ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
We study the problem of finding an approximate Nash equilibrium of games with continuous action sets.
We propose two new methods that minimize an approximation of exploitability with respect to the strategy profile.
arXiv Detail & Related papers (2023-01-20T23:55:30Z) - Generalised agent for solving higher board states of tic tac toe using
Reinforcement Learning [0.0]
This study is aimed at providing a generalized algorithm for higher board states of tic tac toe to make precise moves in a short period.
The idea is to pose the tic tac toe game as a well-posed learning problem.
The study and its results are promising, giving a high win to draw ratio with each epoch of training.
arXiv Detail & Related papers (2022-12-23T10:58:27Z) - Optimal Correlated Equilibria in General-Sum Extensive-Form Games:
Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [99.00383370823839]
We study the problem of finding optimal correlated equilibria of various sorts.
We introduce the correlation DAG, a representation of the space of correlated strategies whose size is dependent on the specific solution concept.
We also introduce two new benchmark games: a trick-taking game that emulates the endgame phase of the card game bridge, and a ride-sharing game.
arXiv Detail & Related papers (2022-03-14T15:21:18Z) - Spatial State-Action Features for General Games [5.849736173068868]
We formulate a design and efficient implementation of spatial state-action features for general games.
These are patterns that can be trained to incentivise or disincentivise actions based on whether or not they match variables of the state in a local area.
We propose an efficient approach for evaluating active features for any given set of features.
arXiv Detail & Related papers (2022-01-17T13:34:04Z) - Portfolio Search and Optimization for General Strategy Game-Playing [58.896302717975445]
We propose a new algorithm for optimization and action-selection based on the Rolling Horizon Evolutionary Algorithm.
For the optimization of the agents' parameters and portfolio sets we study the use of the N-tuple Bandit Evolutionary Algorithm.
An analysis of the agents' performance shows that the proposed algorithm generalizes well to all game-modes and is able to outperform other portfolio methods.
arXiv Detail & Related papers (2021-04-21T09:28:28Z) - Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
We propose Portfolio Monte Carlo Tree Search with Progressive Unpruning for playing a turn-based strategy game (Tribes)
We show how it can be parameterized so a quality-diversity algorithm (MAP-Elites) is used to achieve different play-styles while keeping a competitive level of play.
Our results show that this algorithm is capable of achieving these goals even for an extensive collection of game levels beyond those used for training.
arXiv Detail & Related papers (2021-04-17T20:33:24Z) - Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies
in Extensive-Form Zero-Sum Games [123.76716667704625]
We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game.
In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game.
We provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile.
arXiv Detail & Related papers (2020-09-21T17:51:57Z) - Efficient exploration of zero-sum stochastic games [83.28949556413717]
We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay.
During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well.
Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
arXiv Detail & Related papers (2020-02-24T20:30:38Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.