This paper describes Robospierre a system developed to solve the language game “La Ghigliottina” (the guillotine). To find the solution of a game instance, it relies on MWEs automatically extracted through a lexicalized association rules algorithm; on a list of proverbs; and on some lists of titles.
“La Ghigliottina” is the final game of “L’Eredità”,
an Italian quiz show. In this game, the player
should find a word linked to a set of five clue
words. For example, if these words are table,
works, watch, Premier League and police, the
player should give as solution the word calendar.
The link between a clue and the solution is usually
the fact that both these words are part of an MWE
(Multi-Word Expression) e.g. table and calendar
are linked because they are part of the MWE table
calendar. However, there can be also other kind of
links. For example, the two words can be both
part of a proverb (e.g. bird and world in the
proverb “early bird catches the world”), of a film title
(e.g. river and return in “River of No Return”) or
they can be linked semantically
To build our system, first, we collected and
analyzed a corpus of 296 game instances: 146
from the tv show and 150 from the board game.
Second, we built an association matrix launching
a lexicalized association rules algorithm,
developed by us, on Paisà
In the field of AI (Artificial Intelligence), games
have ever provided challenging tasks that
encouraged researchers to develop better and better
systems
Sangati, Pascucci and Monti (2018) showed that
“the words in the clues are typically nouns, verbs
or adjectives, while the ones in the solutions are
typically nouns or adjectives (never verbs)”. They
also stated that “in most cases each clue word is
connected with the solution because they form an
MWE”. However, MWEs are not the only
possible associations, some game instances require
difficult inferences in order to be solved.
The first artificial player of “La Ghigliottina” is
OTTHO
Our approach is quite similar to the approach of Sangati, Pascucci and Monti (2018) since it also relies on MWEs and makes use of an association matrix to find the solution of the game. However, there are some differences between our approach and theirs.
First, we used MWEs only to find links
between two words in Italian corpora while
UNIOR4NLP used them also to find associations in
other resources like titles and proverbs
In regard to the links extracted from Italian
corpora, we used association rules
Another difference is that we produced a rule for every MWE and then the link between two words is defined as the score of the rule that has the highest score among all the rules in which one word appear in the consequent and the other in the antecedent (see Subsection 4.1). On the other hand, Sangati, Pascucci and Monti (2018) computed a single PMI value between two words considering all the MWEs in which these words occur. If the two systems compute the link between the words dare (to give) and mano (hand) and, in the corpus, these two words occur in the MWEs dare una mano (give a hand | to help) and dare la mano (hold hands). UNIOR4NLP will consider both these MWEs in computing the PMI between dare (to give) and mano (hand) while our system will generate two different rules: (una mano → dare) and (la mano → dare), then it will assign at the link between dare and mano the highest score between the scores of the two rules. This means that probably UNIOR4NLP will give at this link a higher score than our system.
The last difference is that Sangati, Pascucci and Monti (2018) prioritized the strength of the links over their number while we did the opposite. In fact, they considered all the words linked to each other with at least a minimum score. In this way, it is impossible to determine the number of clues to which a word is linked because every word is always linked with all the five clues. Conversely, in our system, a word is usually linked with only a subset of words. Given a game instance, our system tends to answer with a word that is linked to as many clues as possible. 4
Robospierre is composed of a scoring system and
7 linguistic resources: an association matrix, a
list of proverbs, 5 lists of titles and a list of
compound words. This system takes in input a set of
five clues that represents a game instance. For
each clue, it extracts from the resources all the
words that are linked to that clue. Then, a score
value is assigned to each word (it represents the
strength of that link). The words extracted in this
way form the set of candidate solutions. This set
is then processed by the scorer that ranks each
candidate solution according to the strength of
the links between it and the five clues. Finally,
the answer produced by the system is the
candidate solution that has the highest rank.
4.1
The association matrix is an S-C matrix where S is
the set of candidate solutions and C is the set of
possible clues. To list the possible clues, we took
the words whose lemma occurs in Paisà
To populate the matrix, we developed a
lexicalized association rules algorithm based on Apriori
Where R1 is a subset of R containing all the rules in which the word sequence wsi includes the word wi or the word wj and the word sequence wsj includes the other word of the pair. If there are no rules with this feature, the two words wi, wj are not linked to each other.
To populate the association matrix, we ran this
algorithm on the Paisà corpus
To handle the links where the two words are part of a proverb or of a title, we collected from the web the following lists: Rules N → N A → N PREP N → N PREP DET N → N CONG N → N N → PREP N → V DET N → V PREP N → V PREP DET N → V
Position both both backward backward backward backward backward backward backward backward False False False True True True True
Example lupo → cane intenzioni → buone di vista → punto con la mosca → pesca e gatti → cani permesso → con via → andare la spugna → gettare con mano → toccare per i fondelli → prendere dence (1), the lift (2) and a score value (3) used to solve the game instances. (1) (2) (3) (4) We pruned the rules that disrespect one or more of the following constraints: • Count(wsi, wsj) > 1 • • • confr > 0.001 liftr > 1 scorer > 2 • • • • •
Proverbs: A list of 2048 Italian proverbs collected from Wikiquote.1 Films: A list of 13098 film titles collected from Film.it.2 Books: A list of 1633 book titles collected from Cultura&Svago.3 Songs: A list of 984 Italian song titles collected from various web sources.4 Plays: A list of 739 play titles collected from Wikipedia.5 We consider linked two words that appear in the same element of one of these lists. We assigned at these links a fixed score value (see Subsection 5.1). 4.3
The link between a clue and the solution can be also the fact that both the words appear in a compound word. For example, the words police and man are linked because they appear in the compound word policeman. However, there are game instances where the two words appear concatenated in a word that is not a compound. For example, franco (frank) and forte (strong) can be linked because of the word Francoforte (Frankfurt) although this word is not a compound. 1 Wikiquote. Proverbi italiani. https://it.wikiquote.org/wiki/proverbi_i taliani 2 Film.it, Film A-Z. https://www.film.it/film/film-a-z/ 3 Cultura&Svago, Mille titoli letteratura mondiale. https://www.culturaesvago.com/milletitoli-letteratura-mondiale/ 4Il blog di Alessandro Paldo, Le 1000 canzoni italiane più belle di sempre. http://alessandropaldo.blogspot.com/2013/10/1-101.html?m=1 Panorama, Le 100 canzoni italiane più belle del ventunesimo secolo (fino ad ora...). https://www.panorama.it/musica/le-100canzoni-italiane-piu-belle-delventunesimo-secolo/ Le Canzoni d’Amore, Canzoni d’amore Italiane: una lista di brani tra i più belli di sempre. http://www.lecanzonidamore.it/canzoni-damore-italiane/classifiche-italiane/250canzoni-d-amore-italiane-una-lista-dibrani-tra-i-piu-belli-di-sempre.html 5Wikipedia, Elenco di opere teatrali. https://it.wikipedia.org/wiki/Progetto:T eatro/Elenco_di_opere_teatrali 5. Once completed the steps 1-4 for all the clues in the game instance, the system sums all the scores of that candidate solution to produce its final score fs (10). 6. The answer given by the system is the candidate solution that obtains the highest final score value (11).
To handle these links, we consider linked two words that appear compounded in a noun listed in the set of possible clues used in the association matrix (see Subsection 4.1). We assigned at this links a fixed score value (see Subsection 5.1). 4.4
Given five clues (a game instance), our system uses the resources presented above to rank the possible solutions and give an answer. This occurs in six steps: 1. For every clue c∈C, it generates a set of candidate solutions S finding all the words linked to c in the matrix, in the lists, and in the compound words. 2. It generates, for every candidate solution s∈S a set of scores Vs,c that contains a score for every resource in which the clue c and the candidate solution s are linked (5). (5) (6) (7) (8) (9) (10) 3. From the set of scores of every candidate solution, the system keeps only the highest (6). 4. Then, it standardizes every score in an interval (between 0 and 100) and adds to the value obtained a bonus of 100 that represents the existence of a link between that candidate solution and the clue (7)(8)(9). 5
To evaluate the artificial players of “La
Ghigliottina”
The first 100 answers that the system provides
are considered in computing the MRR and a game
instance is considered solved when the solution is
among these 100 answers. According to this
evaluation, UNIOR4NLP
In order to evaluate our system, we collected 294 game instances where the solution was provided: 146 from the tv show and 150 from the board game. Then, we submitted them to the system and computed the MRR (12) considering only the first 100 candidates solutions ranked according to their final scores (10).
To see how the different linguistic resources affect the performance, we tested different version of our system: one with only the association matrix; one with the association matrix and the compound words; and one with the matrix, the compound words and the lists of titles that represents the full system.
Finally, in order to compare our system to
UNIOR4NLP
We assigned to the links in the compound words (see Subsection 4.3) a score of 100 since these links seemed very reliable associations.
To the links in the lists of titles (see Subsection 4.2), we assigned a score of 5 because higher values seemed to worsen the performance of the system and, with lower values, the full model (matrix + compound + titles) gives the same answers of the previous one (matrix + compound). 5.2
The result of the first test are displayed in Table 2.
Our system obtained a quite good result if
compared to the other systems. It was also able to
provide the answer always in the first minute as
UNIOR4NLP did
Maybe because in the tv games, the links are more often based on MWEs while in the board game, there are more links based on titles, proverbs and semantic associations and our system does not treat these links as good as it treats the links based on MWEs (the links based on semantic associations are not even treated). This hypothesis is confirmed by the fact that the list of proverbs and the lists of titles worsen the performance of the system (see Table 3).
We suppose that this problem is caused by the Models
Matrix Matrix + compounds Matrix + compounds
+ titles UNIOR4NLP fact that we assigned at every link in the lists the same score. However, there are titles and proverbs that are more likely to produce reliable links and some others that are not. The more an element is known, the more the links in it must be reliable. Maybe, assigning at every element in the lists a score that represents how much that element is known, might lead to an improvement of system performance. This score might be based on the number of results retrieved when that element is searched with a search engine like Google.
The result of the third test are displayed in Table 3. As the result show, our system was not able to reach the performance of UNIOR4NLP. However, we found among the game instances 20 games to which our system answered correctly while UNIOR4NLP did not. We will analyze some of these instances that are of particular interest.
The first is the following: CLUES: cravatta; neve; S.
Martino; pizza; altare
ANSWER: pala Our system gave to this game instance the correct answer pala (shovel | blade | altarpiece) while UNIOR4NLP gave the answer bianca (white). We suppose that UNIOR4NLP gave this answer because, sometimes, it overestimates the strength of a link and ignores the other links. We believe that the answer bianca is mainly due to the clue neve (snow) since UNIOR4NLP considered both the compound noun Biancaneve (Snow-white) and the frequent co-occurrence between the adjective bianca and the noun neve to compute the PMI between these two terms. On the other hand, our system found three weak links: between pala and neve; between pala and pizza and between pala and altare (altar). These links were sufficient to assign to this word the highest rank among the candidate answers produced.
Another interesting game instance is the following:
CLUES: introduzione; cowboy; fungo; 23; fare tanto
ANSWER: cappello UNIOR4NLP gave to this game instance, the answer proiettili (bullets). Our system gave the correct answer cappello (hat). Maybe, the answer of UNIOR4NLP was due to the overestimation of the link between proiettili and the clue cowboy while it underestimated the link between this clue and the word cappello. We believe that this happened because cappello occurs in more contexts than proiettili. On the other hand, our system gave the correct answer cappello because it was strongly linked with the word sequence da cowboy (like cowboys) since this sequence almost always occurs in the MWE cappello da cowboy (cowboy hat).
The last game instances that we will analyze is the following:
CLUES: andare; musica; occhi; mano; buona
ANSWER: palla
To this game instance, our system answered palla
(ball) and UNIOR4NLP answered pallino (cue
ball | dot). We suppose that this error is caused by
the MWE andare a pallino (right on cue) that
appear in the online dictionary “Il Nuovo De
Mauro”
We described and tested Robospierre, a system developed to solve the word game “La Ghigliottina” (the guillotine). The result of the tests showed that, even if its result were below state-of-the-art, it was able to solve some game instances that the state-of-the-art system did not solved.
In the future, we plan to improve the extraction of the links in the MWEs extracting them from a bigger corpus. We also intend to assign at every element in the list of proverbs and in the lists of titles a score that represents how much that element is known.