Jotto Game Eval

jotto-game-eval

Computing Strong Game-Theoretic Strategies in Jotto — Ganzfried (2011) (arXiv:1107.3342, 2011)

What this evaluates

Evaluates the quality of computed game-theoretic strategies in the word-guessing game Jotto by measuring expected guesses against a benchmark opponent and in self-play, as well as the equilibrium approximation error (epsilon).

Datasets

• Jotto (2-5 letter variants) — total ?; splits: 2-letter (51), 3-letter (421), 4-letter (1373), 5-letter (2833)

Metrics

• epsilon (primary) — range: other
  • The maximum payoff improvement a player could gain by deviating to a best response (full best response for hider, greedy best response for guesser). Lower values indicate a strategy closer to a Nash equilibrium.
• overall_payoff_vs_benchmark — range: other
  • The average of the hider payoff and guesser payoff when the computed strategy plays against a benchmark algorithm (random hider, greedy best-response guesser). Payoff is measured as the expected number of guesses.
• self_play_hider_payoff — range: other
  • The expected number of guesses required when both players use the computed strategy, measured from the hider's perspective.

Input / output format

Input: A filtered dictionary of valid words (no duplicate letters, no anagrams) and a target word length (2, 3, 4, or 5).

Output: An oracular strategy representation that samples moves on demand rather than explicitly storing a full strategy table.

Scoring recipe

def compute_epsilon(strategy, opponent):
    hider_dev = max_payoff_gain(strategy, opponent, role='hider')
    guesser_dev = max_payoff_gain(strategy, opponent, role='guesser')
    return max(hider_dev, guesser_dev)

def compute_payoff(strategy, opponent):
    hider_payoff = simulate(strategy, opponent, role='hider')
    guesser_payoff = simulate(strategy, opponent, role='guesser')
    return (hider_payoff + guesser_payoff) / 2

Common pitfalls

• Epsilon measures worst-case deviation gain, not average performance or regret.
• Payoff is symmetric and averaged across both hider and guesser roles, not just one side.
• The dictionary is heavily filtered (no duplicate letters, no anagrams), which drastically reduces the state space compared to raw word lists.

Evidence (verbatim from paper)

One metric for evaluating our algorithm is to play the strategies it computes against a benchmark algorithm. The benchmark algorithm we chose selects his word uniformly at random as the hider, and plays the greedy best response to the uniform strategy as the guesser. ... The overall payoff is the average of the hider and guesser payoff. ... Recall that ε denotes the maximum payoff improvement one player could gain by deviating to a best response (full best response for the hider and greedy best response for the guesser). Note that in all cases, our ε is significantly lower than that of the benchmark.

Citation

@misc{ganzfried2011computing,
  title={Computing Strong Game-Theoretic Strategies in Jotto},
  author={Ganzfried (2011)},
  year={2011},
  note={arXiv:1107.3342}
}

• arXiv: 1107.3342