×

Playing codenames with language graphs and word embeddings. (English) Zbl 07379286

Summary: Although board games and video games have been studied for decades in artificial intelligence research, challenging word games remain relatively unexplored. Word games are not as constrained as games like chess or poker. Instead, word game strategy is defined by the players’ understanding of the way words relate to each other. The word game Codenames provides a unique opportunity to investigate common sense understanding of relationships between words, an important open challenge. We propose an algorithm that can generate Codenames clues from the language graph BabelNet or from any of several embedding methods – word2vec, GloVe, fastText or BERT. We introduce a new scoring function that measures the quality of clues, and we propose a weighting term called DETECT that incorporates dictionary-based word representations and document frequency to improve clue selection. We develop BabelNet-Word Selection Framework (BabelNet-WSF) to improve BabelNet clue quality and overcome the computational barriers that previously prevented leveraging language graphs for Codenames. Extensive experiments with human evaluators demonstrate that our proposed innovations yield state-of-the-art performance, with up to 102.8% improvement in precision@2 in some cases. Overall, this work advances the formal study of word games and approaches for common sense language understanding.

MSC:

68Txx Artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Agirre, E., Alfonseca, E., Hall, K., Kravalova, J., Pasca, M., & Soroa, A. (2009). A study on similarity and relatedness using distributional and WordNet-based approaches. InProceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 19-27, Boulder, Colorado. Association for Computational Linguistics.
[2] Ashktorab, Z., Dugan, C., Johnson, J., Pan, Q., Zhang, W., Kumaravel, S., & Campbell, M. (2021). Effects of communication directionality and AI agent differences in humanAI interaction. InProceedings of the 2021 CHI Conference on Human Factors in Computing Systems, CHI ’21. Association for Computing Machinery.
[3] Atkinson, T., Baier, H., Copplestone, T., Devlin, S., & Swan, J. (2019). The text-based adventure AI competition.IEEE Transactions on Games,11(3), 260-266.
[4] Bojanowski, P., Grave, E., Joulin, A., & Mikolov, T. (2017). Enriching word vectors with subword information.Transactions of the Association for Computational Linguistics,
[5] Budanitsky, A., & Hirst, G. (2006). Evaluating WordNet-based measures of lexical semantic relatedness.Computational linguistics,32(1), 13-47. · Zbl 1234.68399
[6] Campbell, M., Hoane Jr, A. J., & Hsu, F.-h. (2002). Deep blue.Artificial Intelligence, 134(1-2), 57-83. · Zbl 0982.68122
[7] Collobert, R., Weston, J., Bottou, L., Karlen, M., Kavukcuoglu, K., & Kuksa, P. (2011). Natural language processing (almost) from scratch.Journal of Machine Learning Research,12, 2493-2537. · Zbl 1280.68161
[8] De Deyne, S., Navarro, D. J., Perfors, A., Brysbaert, M., & Storms, G. (2019). The “small world of words” english word association norms for over 12,000 cue words.Behavior research methods,51(3), 987-1006.
[9] Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2019). BERT: Pre-training of deep bidirectional transformers for language understanding. InProceedings of NAACL-HLT, pp. 4171-4186, Minneapolis, Minnesota. Association for Computational Linguistics.
[10] Devlin, J., Zbib, R., Huang, Z., Lamar, T., Schwartz, R., & Makhoul, J. (2014). Fast and robust neural network joint models for statistical machine translation. InProceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1370-1380.
[11] Guo, J., He, H., He, T., Lausen, L., Li, M., Lin, H., Shi, X., Wang, C., Xie, J., Zha, S., Zhang, A., Zhang, H., Zhang, Z., Zhang, Z., Zheng, S., & Zhu, Y. (2020). Gluoncv and gluonnlp: Deep learning in computer vision and natural language processing.Journal of Machine Learning Research,21(23), 1-7. · Zbl 07255054
[12] Hirst, G., St-Onge, D., et al. (1998). Lexical chains as representations of context for the detection and correction of malapropisms.WordNet: An electronic lexical database, 305, 305-332.
[13] Iacobacci, I., Pilehvar, M. T., & Navigli, R. (2016). Embeddings for word sense disambiguation: An evaluation study. InProceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 897-907.
[14] Jaramillo, C., Charity, M., Canaan, R., & Togelius, J. (2020).Word Autobots: Using transformers for word association in the game codenames. InProceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 16(1), pp. 231-237.
[15] Kim, A., Ruzmaykin, M., Truong, A., & Summerville, A. (2019). Cooperation and codenames: Understanding natural language processing via codenames. InProceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 15(1), pp. 160-166.
[16] Mahoney,M.(2011(accessedOctober3,2020)).Aboutthetestdata.. http://mattmahoney.net/dc/textdata.html.
[17] Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., & Dean, J. (2013). Distributed representations of words and phrases and their compositionality.Advances in Neural Information Processing Systems,26, 3111-3119.
[18] Navigli, R., Jurgens, D., & Vannella, D. (2013). Semeval-2013 task 12: Multilingual word sense disambiguation. InProceedings of the 7th International Workshop on Semantic Evaluation (SemEval), in the Second Joint Conference on Lexical and Computational Semantics (*SEM 2013), pp. 222-231.
[19] Navigli, R., & Ponzetto, S. P. (2012). Babelrelate! a joint multilingual approach to computing semantic relatedness. InProceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI 2012). · Zbl 1270.68299
[20] Pennington, J., Socher, R., & Manning, C. D. (2014). GloVe: Global vectors for word representation. InProceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1532-1543.
[21] Reh˚ˇuˇrek, R., & Sojka, P. (2010). Software framework for topic modelling with large corpora. InProceedings of the LREC 2010 Workshop on New Challenges for NLP Frameworks, pp. 45-50, Valletta, Malta. ELRA.
[22] Rovatsos, M., Gromann, D., & Bella, G. (2018). The Taboo challenge competition.AI Magazine,39(1), 84-87.
[23] Schnabel, T., Labutov, I., Mimno, D., & Joachims, T. (2015). Evaluation methods for unsupervised word embeddings. InProceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 298-307.
[24] Shen, J. H., Hofer, M., Felbo, B., & Levy, R. (2018). Comparing models of associative meaning: An empirical investigation of reference in simple language games. InProceedings of the 22nd Conference on Computational Natural Language Learning, pp. 292-301, Brussels, Belgium. Association for Computational Linguistics.
[25] Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., et al. (2016). Mastering the game of Go with deep neural networks and tree search.Nature,529(7587), 484-489.
[26] Speer, R., Chin, J., & Havasi, C. (2017). Conceptnet 5.5: An open multilingual graph of general knowledge. InProceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI’17, p. 4444-4451. AAAI Press.
[27] Thawani, A., Srivastava, B., & Singh, A. (2019). Swow-8500: Word association task for intrinsic evaluation of word embeddings.InProceedings of the 3rd Workshop on Evaluating Vector Space Representations for NLP, pp. 43-51.
[28] Tissier, J., Gravier, C., & Habrard, A. (2017). Dict2vec : Learning word embeddings using lexical dictionaries. InProceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 254-263.
[29] Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., et al. (2019). Grandmaster level in StarCraft II using multi-agent reinforcement learning.Nature, 575(7782), 350-354.
[30] Xu, Y., & Kemp, C. (2010). Inference and communication in the game of password. In Advances in Neural Information Processing Systems, pp. 2514-2522.
[31] Yannakakis, G. N., & Togelius, J. (2018).Artificial Intelligence and Games, Vol. 2. Springer.
[32] Zunjani, F. H., & Olteteanu, A.-M. (2019). Towards reframing codenames for computational modelling and creativity support using associative creativity principles
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.