Codenames as a Game of Co-occurrence Counting (2022)

Abstract: Codenames is a popular board game, in which knowledge and cooperation between players play an important role. The task of a player playing as a spymaster is to find words (clues) that a teammate finds related to as many of some given words as possible, but not to other specified words. This is a hard challenge even with today’s advanced language technology methods. In our study, we create spymaster agents using four types of relatedness measures that require only a raw text corpus to produce. These include newly introduced ones based on co-occurrences, which outperform FastText cosine similarity on gold standard relatedness data. To generate clues in Codenames, we combine relatedness measures with four different scoring functions, for two languages, English and Hungarian. For testing, we collect decisions of human guesser players in an online game, and our configurations outperform previous agents among methods using raw corpora only.

## introduction one of the central subjects of artificial intelligence research has long been the development of agents that play various games at the human level or better. most studies in the field focus on combinatorial games, that can be easily formalized mathematically, such as chess and go (see, for example, @xcite . the popular board game codenames is different from these in many aspects and may provide an excellent experimental ground in areas such as predicting human behavior or implementing human-machine cooperation. in the original game, two teams compete against each other. a board of 25 word cards contains cards belonging to the blue or red team, neutral cards, and an instant defeat card (black). a team wins if all cards of their team are revealed earlier than the cards of the other team, or if the opponent reveals the black card. however, only one person (the spymaster) from both teams knows which card is of what color. therefore, the spymasters give the team a clue each turn, which consists of a clue word and a number. the other members of the team (guessers), in consultation with each other, reveal cards on the board they think are related to the clue word, until they bet on a wrong card, or reach the limit given by the spymaster as a number. this means it is possible to create two types of agents for the game, spymasters and guessers. the main task of both agents is to be able to cooperate with human players. to create agents capable of such high-level cooperation, we need to be able to predict human behavior in the game. this task includes modeling the relatedness of words, with the aim of obtaining relatedness measures that represent human perception well. this task is highly related to word association modeling, which has been studied extensively in psycholinguistics for a long time @xcite , but is by no means equivalent to it. in word association experiments, subjects should name any word associated with a given word as quickly as possible, but in this case, the spymaster's task is to find a word that is related to as many words from a given set as possible, but not or significantly less closely to a set of other words. the time allotted for the task is also limited at most very loosely (by the patience of the other players), and based on personal experiences, spymasters often use several minutes of thinking time to come up with the right clue. for this reason, connected words are often related in a complex way, even indirectly. the task of agents -to find words in the table related to the clue word -is more like simple associations, but time is not dominant here either, and more complex, indirect relations also matter. in a game between people, the relationship and common knowledge between the players can also count, but this is not an influencing factor in a game with an agent. ## a mathematical model of the game however, under such conditions, the behavior of the guessers is deterministic, which means the two spymasters are playing against each other. the dictionary, that is, the number of their possible decisions is finite, and spymasters know the outcome of each decision, which means they know each other's possible strategies. thus, the game becomes a sequential game with perfect information, like e.g. chess, go, or tic-tac-toe. a greedy decision is not necessarily optimal, since a spymaster needs to consider what options they will have later, depending on their own and the other spymasters' decisions, and should optimize their move based on that. within such a framework, the development of an optimal strategy may be the subject of further research, but is no more connected to computational and cognitive linguistics, so we will not discuss this further in this article. the above conditions are, of course, far from reality, since such a distance function, which perfectly corresponds to the mental representations of all people, certainly does not exist. this is clear from the fact that in classical association tests, where the actual task is to find nearest neighbors, the subjects never give the same answer @xcite ). however, it is a meaningful task to create a similarity function and construct a similarity matrix @xmath0, in which s @xmath1, w j ) approximates the average similarity perceived by people. furthermore, based on the similarity approximations, we can define a scoring function for possible clues, which realistically ranks them according to how many correct guesses a human guesser player is expected to give. our distance matrix and our scoring function together determine a greedy spymaster agent. since this task is challenging in itself, we disregard the possible non-greedy strategies and focus on optimizing similarity approximations and clue scoring functions for one round only. ## our codenames agents building on the studies of spence and owens (1990), we introduce several word relatedness measures based on co-occurrences, which we expect to be more suitable for modeling the human perception of word connections than representation methods created for other nlp tasks. we create spymaster agents with several new clue scoring functions combined to our relatedness measures. this way, our methods only require a raw text corpus of appropriate size, so they can be used for any language. we evaluate them in two languages (english and hungarian), in an online game with human players. foot_0 ## evaluation and analysis following @xcite , we use λ = 0.5 for koyyalagunta and koyyrestrict scoring functions, but also for the harmonic function. we pair all relatedness measures to all scoring functions, creating 16 agents in total, and generate clues for @xmath2. differently from @xcite , we consider all of our vocabulary words as possible clue words. for each possible clue word, the best target words in the set i n are the n closest words to the clue word, so scoring a possible clue is computationally inexpensive. we randomly create 100 boards, with each containing 10 good and 10 bad words. for each board, we generate clues with the 32 configurations detailed above. this results in 1304 distinct clues in english, and 1399 in hungarian. for evaluation, we create an online game, where human players get a board with one of the corresponding clues randomly, and have to choose the given number of words from the board which they think the clue refers to. the players do not know how the agents work, and to avoid that through the game they learn it at the end of the round they only see the color of their chosen words. we collected 443 rounds played in english, and 1365 in hungarian. this way, we have 31.5 rounds on average to evaluate english configurations, and 64 rounds for hungarian. for one board, players on average spent 39 seconds on guessing in english, while 37 seconds in hungarian. we note that the players of the hungarian game were most likely hungarian native speakers, while the same cannot be said about the english game, therefore we consider the hungarian data more reliable. in each category (defined by language, evaluation method, and the number of targets), we construct a 0.95 level confidence interval for the best mean precision using bootstrap, and mark the numbers falling into this interval underlined. among the configurations, fasttext similarity combined with the koyyalagunta scoring function was evaluated previously by @xcite , where it was the best agent without any language-specific resource, i.e. using raw corpora only. the results show that this is outperformed by many of our new configurations. on fasttext relatedness, our harmonic and har-monicdivide scoring functions result in a substantial improvement. most of the best performing configurations use fasttext as similarity measure combined with these functions, although the advantage of these methods is less significant when the guesses are evaluated on all blue words instead of the targets of the agent. also, the only agent that performs within the confidence interval of the best agent in their category is fasttext combined with harmonicdivide, therefore we consider it as our highest performing agent. the second best agents in this regard, falling short in one category only, are the graph similarity combined with koyyalagunta and koyyalaguntarestrict functions. as we can see, different relatedness measures fit different scoring functions. as mentioned in 4.2, we think that the harmonic functions are more beneficial where outliers with high relatedness can be found; more generally, the optimal clue scoring function depends on the distribution of the relatedness measures. the exact connection between them seems to be an exciting direction for future work. interestingly, the correlations of the relatedness measures to human-annotated relatedness data (seen in 4.1.5) are not predictive of their performance in codenames, as in those experiments fast-text had been outperformed by both npmi and graph relatedness. the results in the two languages are not perfectly in line either. for example, in english npmi 2 and graph relatedness perform worse than the two other relatedness measures, while the same does not appear in hungarian. we suspect that this is because npmi 2 and graph relatedness capture more indirect connections, which are more problematic to see for non-native speakers. ## summary and future work in this work, we separated the codenames spymaster agent's task into two parts. to cooperate with humans, we first need to specify a relatedness matrix that sufficiently approximates the relationships as judged by humans, and then define a scoring function on top of this that ranks the possible clues according to how many good guesses a human player is expected to give. based on previous research on associations, we generated some of our relatedness matrices based on co-occurrences between words in a corpus. we evaluated these relatedness measures with humanannotated relatedness data. however, we found that these scores were not predictive of the performance of the codenames agents based on these measures. we also introduced innovations in terms of scoring functions, firstly by refining the scoring function of @xcite , and secondly by using the harmonic mean of the relatedness to the clue word. this improved the performance of the best agents substantially. our best agents overall were fasttext cosine similarity combined with a function using harmonic mean, and path weights in a graph of co-occurrences, combined with functions using arithmetic mean of similarities. this raises the question about what relationship is there between relatedness and scoring functions. in future work, we would like to collect data on human spymaster-player decisions and evaluate guesser agents on them, which will directly allow the optimization of the relatedness measure. although many nlp methods have already been used to generate distance matrices, others are worth trying. examples include graph embedding of associations (bel-enguix, 2014) and graphglove @xcite . as each relatedness measure can be defined by a matrix, it is also possible to aggregate several matrices generated in different ways. for example, creating distance matrices based on co-occurrences, neural word representations, and knowledge graphs at the same time seems to be a promising new direction. the comparison of such different relatedness matrices could also provide important lessons in cognitive modeling and the interpretability of neural word representations.