Codenames as a Game of Co-occurrence Counting

Réka Cserháti, Istvan Kollath, András Kicsi, Gábor BerendACL 2022

TL;DR

This paper tackles the challenge of building AI spymasters for the popular word game Codenames. By exploring novel relatedness measures based on co-occurrence statistics and innovative clue scoring functions, the authors significantly improve agent performance, outperforming previous methods that relied solely on raw text corpora.

What Problem Does This Paper Address?

Codenames is a cooperative word game where a "spymaster" gives one-word clues to their teammate to identify specific words on a board, while avoiding words belonging to the opposing team or the "assassin" word. The core difficulty lies in finding a clue word that is semantically related to multiple target words without being too closely related to undesirable words. This requires a deep understanding of word associations and human perception of relatedness, which is a complex task for AI. Previous attempts have often relied on pre-trained language models or knowledge graphs, which can be resource-intensive or language-specific. This paper aims to develop AI spymasters that can achieve human-level performance using only raw text corpora, making them more adaptable and accessible.

Methods

The authors approach this problem by breaking down the spymaster's task into two main components:

  1. Relatedness Measures: Instead of relying on complex neural embeddings, they focus on measures derived from co-occurrence statistics in raw text. They introduce new measures based on co-occurrences that outperform standard FastText cosine similarity on gold-standard relatedness data. These include:
  2. FastText: Cosine similarity of FastText word embeddings (used as a baseline).
  3. Normalized PMI (NPMI): A standard method for measuring word relatedness from co-occurrences, with a focus on positive values.
  4. Squared NPMI Matrix: This novel approach involves multiplying the NPMI matrix by itself, effectively modeling indirect connections between words, inspired by the idea that words can be related through intermediate concepts.
  5. NPMI Graph: This method constructs a graph where edge weights represent the inverse of NPMI values, and distances are calculated as shortest path lengths. Relatedness is then derived from these distances.
  6. Clue Scoring Functions: To evaluate the quality of potential clues, they combine the relatedness measures with several scoring functions. They refine existing functions and introduce new ones, including:
  7. Koyyalagunta: A scoring function that penalizes clues too close to "bad" words.
  8. KoyyRestrict: A stricter version of Koyyalagunta that only allows clues if the closest "bad" word is sufficiently distant.
  9. Harmonic: A function that uses the harmonic mean of relatedness scores, which is hypothesized to be better at handling outliers with very high relatedness.
  10. HarmonicDivide: A variation of the Harmonic function where the penalty is applied via division.

Datasets

  • Training Corpora:
    • English: Concatenation of English Wikipedia and English OpenSubtitles (5.692 billion tokens).
  • Hungarian: Lemmatized Hungarian Webcorpus and Hungarian Wikipedia (1.414 billion tokens).
  • Evaluation Datasets:
    • Human decisions collected from an online Codenames game.
  • Gold standard relatedness data: MEN and WS-353 datasets were used to evaluate the relatedness measures themselves.

Key Insights and Ideas

  • Indirect Connections Matter: The "Squared NPMI Matrix" and "NPMI Graph" relatedness measures, which capture indirect word associations, show promise. This aligns with human intuition that relatedness isn't always direct (e.g., "religion" and "tree" might be indirectly related through "Christmas").
  • Co-occurrence is Powerful: The paper demonstrates that simple co-occurrence statistics, when processed effectively, can yield relatedness measures competitive with, and sometimes superior to, those derived from complex neural models like FastText.
  • Scoring Functions are Crucial: The choice of scoring function significantly impacts agent performance. The Harmonic and HarmonicDivide functions, which handle potential outliers and extreme relatedness values, led to substantial improvements.
  • Relatedness vs. Performance: Interestingly, the correlation of relatedness measures with human-annotated relatedness data (like MEN and WS-353) was not a perfect predictor of their performance in the Codenames game. This suggests that the specific task demands of Codenames require a nuanced approach beyond general semantic similarity.
  • Language Differences: Performance varied between English and Hungarian, with indirect connection measures (NPMI², Graph) performing less consistently in English, possibly due to non-native speakers having more difficulty with subtle indirect links.

Key Results

The paper reports significant improvements in agent performance, measured by the rate of correct guesses made by human players.

  • Hungarian Game: The best performing configuration was FastText similarity combined with the HarmonicDivide scoring function, achieving a correct guess rate of 0.759 for 2 targets and 0.759 for 3 targets (P@all). This outperformed previous state-of-the-art agents that used raw corpora only.
  • English Game: Similarly, FastText similarity with Harmonic scoring performed very well, achieving 0.783 for 2 targets and 0.760 for 3 targets (P@all).
  • The authors highlight that many of their new configurations outperform previous agents that used raw corpora only.

Limitations and Future Work

  • Limitations:
    • The study primarily focuses on spymaster agents and does not deeply explore guesser agents or the full game dynamics.
  • The evaluation of relatedness measures against human-annotated data did not perfectly predict their performance in the Codenames game.
  • The exact relationship between different relatedness measures and scoring functions remains an open question.
  • Future Work:
    • Collect data on human spymaster-player decisions to directly optimize relatedness measures.
  • Explore other NLP methods for generating distance matrices, such as graph embedding techniques.
  • Investigate methods for aggregating multiple relatedness matrices (e.g., from co-occurrences, neural representations, and knowledge graphs) to create more robust representations.
  • Further analyze the interplay between relatedness measures and scoring functions.

Summary updated

BibTeX
@inproceedings{cserhati2022codenames,
  author = {Réka Cserháti and Istvan Kollath and András Kicsi and Gábor Berend},
  title = {{Codenames as a Game of Co-occurrence Counting}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2022},
}
Figure