The paper describes GUL.LE.VER, GUiLlottine gLovE resolVER, a Glove based system developed to solve the game “La Ghigliottina” which participated in the Evalita 2020 (Basile et al., 2020) task Ghigliottin-AI. The system described positioned #2, with 0.26 of Precision and 0.46 R@10, more than one guillotine is solved every four games, achieving results comparable to human players. The system proved to solve a different kind of guillotines compared to the first classified system 'Il Mago della ghigliottina' (Sangati et al., 2018). An approach based on these two kinds of systems may result in a boost in this field of research.
“La Ghigliottina” is a language game in which the
gamer has to guess the word that is most
correlated with other five words, named clues. An
example is the guillotine ”Certificate, Son, Tragedy,
Star, Venus”, the solution, in this case, is ”Birth”.
The game structure is simple, but some complex
steps are required in order to solve a guillotine.
The gamer’s background knowledge has to be rich
enough to cover a large variety of fields, such as
common culture, proverbs, etc. Additionally, the
gamer’s reasoning has to be fast enough to give
the solution in less than a minute. In this
article, an artificial player for The Guillotine has been
built: GUL.LE.VER, the GUiLlotine gLovE
resolVER. It’s mostly based on the Glove
Copyright ©2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Italian Wiktionary, Wikiquote, Wikipedia (only
titles), the Italian Collocations Dictionary (Tiberi,
2018), and resources scraped on the web
containing Italian polirematics, proverbs and songs titles.
The Glove algorithm was chosen for its intrinsic
power in capturing the co-occurrence correlation
between two words that are not synonyms, due to
the co-occurrence matrix that the algorithm builds
before the training. Other similar algorithms, such
as Word2Vec, do not have this characteristic. The
solution for the guillotine is searched in the vector
space near the clues, obtaining a list of solution
candidates. This list is descending reordered
using a hybrid function composed by two parts: one
part is based on the Pointwise Mutual Information
In order to find the solution for a particular game,
a player needs to know the rules that regulate
the game and, based on the game type, he also
needs to possess a background knowledge that
helps him in finding the solution. We can
distinguish two types of games based on these two
requirements: closed-world games and open-world
games. Closed-world games provide the player
with all the knowledge necessary for playing the
game (like chess), otherwise open-world games
can not be solved without additional knowledge.
A particular type of open-world games is
represented by language games in which word
meanings play a central role (like crosswords)
Based on the previous related works, the linguistic resources involved in this project are: • The italian Wikipedia, only titles, downloaded via WikiExtractor (Attardi, 2012).
Wiktionary, downloaded via • The italian
WikiExtractor. • The italian
WikiExtractor.
Wikiquote, downloaded via
• The “Dizionario delle Collocazioni” (Tiberi,
2018) containing 200.000 combinations of
words in Italian.
• A collection of 369 italian proverbs
These corpora was preprocessed, using tokenization (single words only) and punctuation removing, obtaining a unique corpus to feed the Glove algorithm. 3
The system can be described in 6 steps: 1. Glove training: the corpus is used to train a Glove model that represents the words in corpus in a compact vector space. The best parameters used to train the algorithm are empirically obtained: Vector size 600, Vocab min count 200, Window 10, Iteration 50, Xmax 10, Alpha 0.75, Eta 0.05. They proved to be the best parameters for the Evalita training dataset. (a) The Vocab min count setted to 200 corresponds to a vocabulary of 28873 unique words represented. 2. Setting search space, ‘looking into neighbors’: starting from the clues, a list of 5 M solution candidates is built finding the M most similar words to each clue in order of cosine similarity. The result search space is significantly smaller than the entire vocabulary. This solution gives faster and more accurate results than the exhaustive search on the vocabulary.
dates list is filtered by: (a) removing all words except Nouns and Adjective (verbs and conjunctions are never solutions for the game). (b) removing Adjectives too, if one of the clues is already an adjective. (c) removing words that are present in a custom blacklist and not present in a custom whitelist. The blacklist contains lists of non-ambiguous proper nouns, cities names, foreign words, etc. 4. Reordering, the cosine based score function: the filtered list is reordered in descending order based on the following formula: (a) F (t) = (Pin=1(cos(s;ci) nIDF (ci))) N
1+ (b) The first part of the formula are two arbitrary weights that can be manually set up in order to give more importance to the weighted mean of the cosines or the standard deviation. (c) The second part of the formula has: as a numerator, the weighted mean of the cosines between the solution candidate and clues. The weight is the normalized Inverse Document Frequency of the clue in the corpus. This gives a boost to the solutions that are correlated to the most rare clues, starting with the assumption that a rare clue has less possible meaningful combination in the corpus, so a candidate solution highly correlated with that may be corresponding to the solution of the game. As a denominator, there is the standard deviation of the cosines (not weighted). This is intended to give a boost to the solutions that are correlated with all the clues in a balanced way, avoiding such solutions that are very highly correlated to a clue but not to the others. (d) A cosine threshold can be set in order to discard cosines that are lower than that, penalizing those that are too low. In this case, the cosines lower than zero are penalized automatically to 1 (the lower bound of the cosine similarity function), avoiding solutions that have opposite meaning compared to the clues. 5. Solution certainty: if the difference between the first and the second score result is more than a Solution certainty threshold, the first candidate is proposed as a solution for the game. If not, the candidate list is reordered again using the Pointwise Mutual Information (pmi),calculated on the corpus proposed, as the third multiplied part of the formula F (t). This helps in the situation in which the real solution is between the first three/four results before the final reordering. 6. Solution proposed: the first candidate of the reorder list is proposed as a solution for the game. 4
The system is entirely implemented in Python 3.7.
The principal libraries used are:
• gensim
The Glove algorithm
The table 1 shows the results obtained by GUL.LE.VER on the Evalita-GhigliottinAI Dev dataset and Test dataset.
Set Dev Test Dev* Test*
Size Precision R@5 R@10 R@100 300 pt 0,32 0,44 0,51 0,69 350 pt 0,27 0,38 0,46 0,62 300 pt 0,32 0,37 0,44 0,68 350 pt 0,28 0,40 0,48 0,65
The 5% difference in the Precision between the Dev set and the Test set is in part due to a blacklist overfitted on the dev set. 10 solutions are found to be erroneously in the blacklist. Putting them in the whitelist gives a more balanced result, slightly higher for the Test dataset and a little lower for the Dev dataset, as shown by the Dev* and Test* rows. The system seems biased by solutions that are very frequent in corpus: it responded ‘uno’ 23 times and none of them were the correct solution. Another example: it responded ‘senza’ 9 times, only one time guessing the correct solution. An important point to underline is that almost half of the solutions are found in the first 10 proposed results, with approximately 40% of them in the first 5, with 57% and 56% in the first 20 for Test and Dev set respectively (not reported in Table 1). This seems very promising for future upgrading, finding a better way to clean the candidates list and/or fine tuning the reorder function.
The last point of analysis is a brief comparison between GUL.LE.VER and ‘Il Mago della Ghigliottina’. Selecting only the resolved guillotines from the Test Set and submitting them to the Telegram version of ‘Il Mago della Ghigliottina’, 18 guillotines were not resolved by Sangati et al., 2018 system. These guillotines (in table 2) represent 4.8% of the total test guillotines and can be resolved only by the proposed solution.
Clue1 Clue2 Clue3 fazzoletto alto allungare studio vestire notte paradiso bordo sud vecchio cavallo end mettere moto collo mamma scena scuola volo dare mezzi idee bocca isola finestra vestire volto pari pace sosta cura pietre alto acqua onda capo citta` tv vita bandiera coltelli caponi dare camera consiglio regola parole alberi leggero barba togliere
Clue4 braccio povero nino soda baffi re ente sottomarino chiara motivo azzurro sempre oggi marx misura perfetto viso
Clue5 Gullever Mago osso collo naso montalbano giovane panni
casa benvenuti angolo conquista west polenta brutta piega giro crudo nudo gonna intervento assistenza pronto spock vulcano porto chiaro scuro luna famiglia senza apparente occhi sole cielo essere verde andata gioco ragazzi frenetico italia fratelli regno stato sicurezza deciso fa tre quadrato inganno trucco velo
In this paper is described GUL.LE.VER, an artificial player to solve the game “La Ghigliottina”, based on the Glove word vector algorithm, whose power is its co-occurrence matrix reduction. An hybrid pmi approach is proposed as fallback in case of uncertainty. The system achieved good performance in the Evalita2020 task, with results comparable to humans. A comparison made with the solutions proposed by the best system, the Sangati et al., 2018 ‘Il Mago della Ghigliottina’, suggests that the proposed approach is capable of solving different kinds of guillotines compared to the first one. As future work, a even more hybrid solution between these two kinds of approaches should be implemented, hoping it will be result in a boost in this field of research.