=Paper=
{{Paper
|id=Vol-2481/paper19
|storemode=property
|title=Robospierre, an Artificial Intelligence to Solve “La Ghigliottina”
|pdfUrl=https://ceur-ws.org/Vol-2481/paper19.pdf
|volume=Vol-2481
|authors=Nicola Cirillo,Chiara Pericolo,Pasquale Tufano
|dblpUrl=https://dblp.org/rec/conf/clic-it/CirilloPT19
}}
==Robospierre, an Artificial Intelligence to Solve “La Ghigliottina”==
https://ceur-ws.org/Vol-2481/paper19.pdf
Robospierre, an Artificial Intelligence to Solve “La Ghigliottina”
Nicola Cirillo Chiara Pericolo Pasquale Tufano
University of Salerno University of Salerno University of Salerno
Salerno, Italy Salerno, Italy Salerno, Italy
n.cirillo9@studenti c.pericolo@studenti p.tufano@studenti.u
.unisa.it .unisa.it nisa.it
nally, we tested the system on the game instances
Abstract collected and we compared it with other artificial
players of “La Ghigliottina”, especially UN-
This paper describes Robospierre a sys- IOR4NLP (Sangati, Pascucci and Monti, 2018),
tem developed to solve the language that obtained the best performance on this task at
game “La Ghigliottina” (the guillotine). Evalita 2018 (Basile et al., 2018).
To find the solution of a game instance, it
relies on MWEs automatically extracted 2 Related Works
through a lexicalized association rules al-
gorithm; on a list of proverbs; and on In the field of AI (Artificial Intelligence), games
some lists of titles. have ever provided challenging tasks that encour-
aged researchers to develop better and better sys-
1 Introduction tems (Yannakakis and Togelius, 2018). In regard
to language games, worth citing is the IBM Wat-
“La Ghigliottina” is the final game of “L’Eredità”, son system designed to play Jeopardy!TM (Ferrucci
an Italian quiz show. In this game, the player
et al., 2013). However, only recently, the task of
should find a word linked to a set of five clue
solving “La Ghigliottina” has attracted the atten-
words. For example, if these words are table,
tion of researchers. Besides a first attempt in 2009
works, watch, Premier League and police, the
(Semeraro et al., 2009), the research on this topic
player should give as solution the word calendar.
began in 2018 when this task was proposed at the
The link between a clue and the solution is usually
Evalita evaluation campaign (Basile et al., 2018).
the fact that both these words are part of an MWE
(Multi-Word Expression) e.g. table and calendar 2.1 Game Analysis
are linked because they are part of the MWE table
Sangati, Pascucci and Monti (2018) showed that
calendar. However, there can be also other kind of
“the words in the clues are typically nouns, verbs
links. For example, the two words can be both
or adjectives, while the ones in the solutions are
part of a proverb (e.g. bird and world in the prov-
typically nouns or adjectives (never verbs)”. They
erb “early bird catches the world”), of a film title
also stated that “in most cases each clue word is
(e.g. river and return in “River of No Return”) or
connected with the solution because they form an
they can be linked semantically (e.g. Suarez and
MWE”. However, MWEs are not the only possi-
bite because of the Suarez’s bite to Chiellini dur-
ble associations, some game instances require dif-
ing the 2014 World Cup). The task of solving this
ficult inferences in order to be solved. (Basile et
game was presented as the NLP4FUN task of
al., 2018).
Evalita 2018 (Basile et al., 2018).
To build our system, first, we collected and 2.2 Artificial Players
analyzed a corpus of 296 game instances: 146
The first artificial player of “La Ghigliottina” is
from the tv show and 150 from the board game.
OTTHO (Semeraro et al., 2009; Basile et al.,
Second, we built an association matrix launching
2016) which employs an association matrix that
a lexicalized association rules algorithm, devel-
uses a spreading activation model on a knowledge
oped by us, on Paisà (Lyding et al., 2014). Then,
repository to compute the degree of correlation
we collected from the web a list of titles of books,
between two terms (the repository was built using
films, plays and songs; and a list of proverbs. Fi-
web sources like Wikipedia). During Evalita 2018
Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International
(CC BY 4.0).
(Basile et al., 2018) two artificial players were quency. Conversely, with association rules, this
presented: UNIOR4NLP (Sangati, Pascucci and same link will be considered much stronger.
Monti, 2018) and the system developed by Another difference is that we produced a rule
Squadrone (2018). The first is based on MWEs. It for every MWE and then the link between two
employs an association-score matrix that was words is defined as the score of the rule that has
populated computing the PMI (Pointwise Mutual the highest score among all the rules in which one
Information) measure for each pair of words. In word appear in the consequent and the other in the
computing this measure, only co-occurrences in antecedent (see Subsection 4.1). On the other
specific patterns (that represents MWEs) were hand, Sangati, Pascucci and Monti (2018) com-
considered. The second system is based on an al- puted a single PMI value between two words con-
gorithm that works in two steps. First, the system sidering all the MWEs in which these words oc-
extracts a set of possible solutions from a cur. If the two systems compute the link between
knowledge base using the five clue words. Then, the words dare (to give) and mano (hand) and, in
the algorithm verifies the existence of proverbs, the corpus, these two words occur in the MWEs
aphorisms, and titles in which the possible solu- dare una mano (give a hand | to help) and dare la
tions and the clues co-occur. mano (hold hands). UNIOR4NLP will consider
both these MWEs in computing the PMI between
3 Our Approach dare (to give) and mano (hand) while our system
Our approach is quite similar to the approach of will generate two different rules: (una mano →
Sangati, Pascucci and Monti (2018) since it also dare) and (la mano → dare), then it will assign at
relies on MWEs and makes use of an association the link between dare and mano the highest score
matrix to find the solution of the game. However, between the scores of the two rules. This means
there are some differences between our approach that probably UNIOR4NLP will give at this link a
and theirs. higher score than our system.
First, we used MWEs only to find links be- The last difference is that Sangati, Pascucci and
tween two words in Italian corpora while UN- Monti (2018) prioritized the strength of the links
IOR4NLP used them also to find associations in over their number while we did the opposite. In
other resources like titles and proverbs (Sangati, fact, they considered all the words linked to each
Pascucci and Monti, 2018). We decided that, in a other with at least a minimum score. In this way, it
title and in a proverb, a simple co-occurrence is a is impossible to determine the number of clues to
valid link. In fact, there are game instances in which a word is linked because every word is al-
which a clue is linked to the solution because both ways linked with all the five clues. Conversely, in
appear in the same title or proverb, even if they do our system, a word is usually linked with only a
not form an MWE. For example, in a game in- subset of words. Given a game instance, our sys-
stance, the clue occasione (opportunity) is linked tem tends to answer with a word that is linked to
to the solution ladro (thief) because both appear in as many clues as possible.
the famous Italian proverb “l’occasione fa l’uomo
ladro” (opportunity makes a thief) even if they do 4 System Description
not form any MWE. Robospierre is composed of a scoring system and
In regard to the links extracted from Italian 7 linguistic resources: an association matrix, a
corpora, we used association rules (Agrawal and list of proverbs, 5 lists of titles and a list of com-
Srikant, 1994) instead of PMI. We decided to use pound words. This system takes in input a set of
this measure because, in MWEs, there is a head five clues that represents a game instance. For
and the rest of the expression depends on it. For each clue, it extracts from the resources all the
example, in the MWE pesca con la mosca (fly words that are linked to that clue. Then, a score
fishing), the word sequence con la mosca (with value is assigned to each word (it represents the
the fly) rarely appear without the noun pesca strength of that link). The words extracted in this
(fishing | peach). However, the noun pesca will way form the set of candidate solutions. This set
appear a lot of times without being followed by is then processed by the scorer that ranks each
the word sequence con la mosca. The PMI be- candidate solution according to the strength of
tween the terms pesca and mosca will be low be- the links between it and the five clues. Finally,
cause the noun pesca has a relatively high fre- the answer produced by the system is the candi-
date solution that has the highest rank.
4.1 Association Matrix Rules Position Lemmatize Example
N→N both False lupo → cane
The association matrix is an S-C matrix where S is A→ N both False intenzioni → buone
the set of candidate solutions and C is the set of PREP N → N backward False di vista → punto
possible clues. To list the possible clues, we took PREP DET N con la mosca →
backward False
→N pesca
the words whose lemma occurs in Paisà (Lyding CONG N →
backward False e gatti → cani
et al., 2014) at least 10 times. Then we performed N
the POS tagging on these lemmas with Nooj N → PREP backward False permesso → con
N→V backward True via → andare
(Silberztein, 2018) using as lexical resources DET N → V backward True la spugna → gettare
_Sdic_it.nod, Dnum.nom, tronche.nod, toponi- PREP N → V backward True con mano → toccare
mi.nod, ElisioniContrazioni.nod and as syntactic PREP DET N per i fondelli →
backward True
→V prendere
resources DNUM.nog (Vietri, 2014). From the list
obtained, we extracted only nouns, adjectives, Table 1: Parameters given to the genMWE function
verbs, and prepositions and then we inflected
them (with Nooj). On the other hand, the set of dence (1), the lift (2) and a score value (3) used to
candidate solutions is a subset of the set of possi- solve the game instances.
ble clues containing only nouns and adjectives.
To populate the matrix, we developed a lexical- (1)
ized association rules algorithm based on Apriori
(Agrawal and Srikant, 1994). In our algorithm, a (2)
rule is an implication A → B where A and B are
sequences of words. To generate the possible (3)
rules, our algorithm uses a function written by us:
We pruned the rules that disrespect one or more of
genMWE. This function takes five arguments: D,
the following constraints:
antecedent, consequent, position and lemmatize. D
• Count(wsi, wsj) > 1
is a text; antecedent and consequent are sequences
of POS tags that represent respectively the possi- • confr > 0.001
ble antecedents and the possible consequents of
the rules. The argument position tells the function • liftr > 1
where it must search for the consequent in relation
to the position of the antecedent. It can take the • scorer > 2
values forward, backward and both. The value
Once generated the rules, the score of a link in the
forward means that the consequent directly fol-
association matrix between a pair of words wi, wj
lows the antecedent in the text, the value back-
is defined in the following equation (4).
ward means that the consequent directly precedes
the antecedent and the value both means that the (4)
consequent can either follow or precede the ante-
cedent. The argument lemmatize can take a Bool- Where R1 is a subset of R containing all the rules
ean value. If it takes true, the antecedents of all in which the word sequence wsi includes the word
the rules will be lemmatized. For example, if we wi or the word wj and the word sequence wsj in-
run the function on a text with parameters ante- cludes the other word of the pair. If there are no
cedent = PREP N, consequent = N, position = rules with this feature, the two words wi, wj are not
backward and lemmatize = false; it will generate linked to each other.
rules such as (di credito → carta) (credit card), (di To populate the association matrix, we ran this
credito → carte) (credit cards), (da guardia → algorithm on the Paisà corpus (Lyding et al.,
cane) (watchdog), etc. Table 1 shows the parame- 2014).
ters used in our experiment. While the algorithm
is generating the candidate rules, it counts the oc- 4.2 Lists
currences of every rule (wsj → wsi) and the occur- To handle the links where the two words are part
rences of the word sequences wsj that match the of a proverb or of a title, we collected from the
pattern of POS tags given as consequent. Finally, web the following lists:
the algorithm computes, for every rule, the confi-
• Proverbs: A list of 2048 Italian proverbs To handle these links, we consider linked two
collected from Wikiquote.1 words that appear compounded in a noun listed in
the set of possible clues used in the association
• Films: A list of 13098 film titles collect- matrix (see Subsection 4.1). We assigned at this
ed from Film.it.2 links a fixed score value (see Subsection 5.1).
• Books: A list of 1633 book titles collect- 4.4 Scoring System
ed from Cultura&Svago.3
Given five clues (a game instance), our system
• Songs: A list of 984 Italian song titles uses the resources presented above to rank the
collected from various web sources.4 possible solutions and give an answer. This occurs
in six steps:
• Plays: A list of 739 play titles collected 1. For every clue c∈C, it generates a set of
from Wikipedia.5 candidate solutions S finding all the
words linked to c in the matrix, in the
We consider linked two words that appear in the lists, and in the compound words.
same element of one of these lists. We assigned at
these links a fixed score value (see Subsection 2. It generates, for every candidate solution
5.1). s∈S a set of scores Vs,c that contains a
score for every resource in which the
4.3 Compound Words clue c and the candidate solution s are
The link between a clue and the solution can be linked (5).
also the fact that both the words appear in a com-
pound word. For example, the words police and (5)
man are linked because they appear in the com- 3. From the set of scores of every candidate
pound word policeman. However, there are game solution, the system keeps only the high-
instances where the two words appear concatenat- est (6).
ed in a word that is not a compound. For example,
franco (frank) and forte (strong) can be linked
(6)
because of the word Francoforte (Frankfurt) alt-
hough this word is not a compound. 4. Then, it standardizes every score in an
interval (between 0 and 100) and adds to
1
the value obtained a bonus of 100 that
Wikiquote. Proverbi italiani.
https://it.wikiquote.org/wiki/proverbi_i represents the existence of a link be-
taliani tween that candidate solution and the
2
Film.it, Film A-Z. clue (7)(8)(9).
https://www.film.it/film/film-a-z/
3
Cultura&Svago, Mille titoli letteratura mondiale.
https://www.culturaesvago.com/mille- (7)
titoli-letteratura-mondiale/
4
Il blog di Alessandro Paldo, Le 1000 canzoni italiane più (8)
belle di sempre.
http://alessandro-
paldo.blogspot.com/2013/10/1-10- (9)
1.html?m=1
Panorama, Le 100 canzoni italiane più belle del ventunesi-
5. Once completed the steps 1-4 for all the
mo secolo (fino ad ora...).
https://www.panorama.it/musica/le-100- clues in the game instance, the system
canzoni-italiane-piu-belle-del- sums all the scores of that candidate so-
ventunesimo-secolo/ lution to produce its final score fs (10).
Le Canzoni d’Amore, Canzoni d’amore Italiane: una lista di
brani tra i più belli di sempre.
http://www.lecanzonidamore.it/canzoni-d- (10)
amore-italiane/classifiche-italiane/250-
canzoni-d-amore-italiane-una-lista-di- 6. The answer given by the system is the
brani-tra-i-piu-belli-di-sempre.html candidate solution that obtains the high-
5
Wikipedia, Elenco di opere teatrali. est final score value (11).
https://it.wikipedia.org/wiki/Progetto:T
eatro/Elenco_di_opere_teatrali
fect the performance, we tested different version
(11)
of our system: one with only the association ma-
trix; one with the association matrix and the com-
5 System Evaluation pound words; and one with the matrix, the com-
To evaluate the artificial players of “La Ghigliot- pound words and the lists of titles that represents
tina” Basile et al. (2018) made use of the MRR the full system.
(Mean Reciprocal Rank) measure weighted by a Finally, in order to compare our system to UN-
function that lower the score according to the time IOR4NLP (Sangati, Pascucci and Monti, 2018),
taken by the system to provide the answer (12). we submitted the same game instances to the Tel-
egram bot version of UNIOR4NLP and then we
(12)
computed the precision-k (13) of the two systems
for k = 1 (since the UNIOR4NLP bot provides
In this equation, G is the set of game instances, rg only one answer).
is the rank that the solution of the game g has in
5.1 Parameters Used in the Tests
the set of answers produced by the system, and tg
is the time (in minutes) that the system takes to We assigned to the links in the compound words
provide the set of answers (Basile et al., 2018). (see Subsection 4.3) a score of 100 since these
The first 100 answers that the system provides links seemed very reliable associations.
are considered in computing the MRR and a game To the links in the lists of titles (see Subsection
instance is considered solved when the solution is 4.2), we assigned a score of 5 because higher val-
among these 100 answers. According to this eval- ues seemed to worsen the performance of the sys-
uation, UNIOR4NLP (Sangati, Pascucci and tem and, with lower values, the full model (matrix
Monti, 2018) obtained an MRR of 0.6428 and + compound + titles) gives the same answers of
solved the 81.90% of the game instances while the previous one (matrix + compound).
Squadrone (2018) obtained an MRR of 0.0134
and solved the 25.71% of the game instances. 5.2 Analysis of the Results
Basile et al. (2016) evaluated OTTHO using The result of the first test are displayed in Table 2.
the precision-k measure. A game is considered k- Our system obtained a quite good result if com-
solved if the solution has rank k or higher in the pared to the other systems. It was also able to pro-
set of answers provided by the system (13). vide the answer always in the first minute as UN-
IOR4NLP did (Basile et al., 2018). It performed
(13) better on the tv games than on the board games.
Maybe because in the tv games, the links are more
With k = 1, the best model of OTTHO obtained a often based on MWEs while in the board game,
precision of about 0.25 on tv games and about there are more links based on titles, proverbs and
0.30 on board games. With k = 100, it obtained a semantic associations and our system does not
precision of about 0.50 on tv games and about treat these links as good as it treats the links based
0.70 on board games (Basile et al., 2016). on MWEs (the links based on semantic associa-
In order to evaluate our system, we collected tions are not even treated). This hypothesis is con-
294 game instances where the solution was pro- firmed by the fact that the list of proverbs and the
vided: 146 from the tv show and 150 from the lists of titles worsen the performance of the sys-
board game. Then, we submitted them to the sys- tem (see Table 3).
tem and computed the MRR (12) considering only We suppose that this problem is caused by the
the first 100 candidates solutions ranked accord-
ing to their final scores (10). Precision-1
Models
To see how the different linguistic resources af- All Tv Board game
Matrix 0.3480 0.4014 0.2933
Matrix + compounds 0.3514 0.4178 0.3067
All Tv Board game Matrix + compounds
0.3446 0.4178 0.3000
MRR 0.4140 0.4794 0.3660 + titles
Correct UNIOR4NLP 0.5608 0.6643 0.4600
72.30% 80.82% 64.00%
Answers Tot (296) Tot (146) Tot (150)
Table 2: Result of first test Table 3: Result of second and third tests
fact that we assigned at every link in the lists the the link between proiettili and the clue cowboy
same score. However, there are titles and proverbs while it underestimated the link between this clue
that are more likely to produce reliable links and and the word cappello. We believe that this hap-
some others that are not. The more an element is pened because cappello occurs in more contexts
known, the more the links in it must be reliable. than proiettili. On the other hand, our system gave
Maybe, assigning at every element in the lists a the correct answer cappello because it was strong-
score that represents how much that element is ly linked with the word sequence da cowboy (like
known, might lead to an improvement of system cowboys) since this sequence almost always oc-
performance. This score might be based on the curs in the MWE cappello da cowboy (cowboy
number of results retrieved when that element is hat).
searched with a search engine like Google. The last game instances that we will analyze is
The result of the third test are displayed in Ta- the following:
ble 3. As the result show, our system was not able
to reach the performance of UNIOR4NLP. How- CLUES: andare; musica; oc-
ever, we found among the game instances 20 chi; mano; buona
games to which our system answered correctly ANSWER: palla
while UNIOR4NLP did not. We will analyze
To this game instance, our system answered palla
some of these instances that are of particular in-
(ball) and UNIOR4NLP answered pallino (cue
terest.
ball | dot). We suppose that this error is caused by
The first is the following:
the MWE andare a pallino (right on cue) that ap-
CLUES: cravatta; neve; S. pear in the online dictionary “Il Nuovo De Mau-
Martino; pizza; altare ro” (De Mauro, 2016) which was employed by
ANSWER: pala UNIOR4NLP as linguistic resource. UNIOR4NLP
considered a co-occurrence in this dictionary as
Our system gave to this game instance the correct strong as 200 co-occurrences in the Italian corpora
answer pala (shovel | blade | altarpiece) while so this link obtained a higher PMI than that be-
UNIOR4NLP gave the answer bianca (white). We tween andare and palla but, actually, the MWE
suppose that UNIOR4NLP gave this answer be- andare in palla (be confused) is much more
cause, sometimes, it overestimates the strength of common than andare a pallino.
a link and ignores the other links. We believe that
the answer bianca is mainly due to the clue neve 6 Conclusions
(snow) since UNIOR4NLP considered both the We described and tested Robospierre, a system
compound noun Biancaneve (Snow-white) and developed to solve the word game “La Ghigliotti-
the frequent co-occurrence between the adjective na” (the guillotine). The result of the tests showed
bianca and the noun neve to compute the PMI that, even if its result were below state-of-the-art,
between these two terms. On the other hand, our it was able to solve some game instances that the
system found three weak links: between pala and state-of-the-art system did not solved.
neve; between pala and pizza and between pala In the future, we plan to improve the extraction
and altare (altar). These links were sufficient to of the links in the MWEs extracting them from a
assign to this word the highest rank among the bigger corpus. We also intend to assign at every
candidate answers produced. element in the list of proverbs and in the lists of
Another interesting game instance is the fol- titles a score that represents how much that ele-
lowing: ment is known.
CLUES: introduzione; cowboy;
fungo; 23; fare tanto Reference
ANSWER: cappello Agrawal Rakesh and Srikant Ramakrishnan. 1994.
“Fast algorithms for mining association rules.”
UNIOR4NLP gave to this game instance, the an- Proc. 20th int. conf. very large data bases, VLDB.
swer proiettili (bullets). Our system gave the cor- Vol. 1215.
rect answer cappello (hat). Maybe, the answer of Basile Pierpaolo, de Gemmis Marco, Lops Pasquale,
UNIOR4NLP was due to the overestimation of and Semeraro Giovanni. 2016. “Solving a complex
language game by using knowledge-based word Yannakakis Georgios N. and Togelius Julian. 2018.
associations discovery”. IEEE Transactions on Artificial Intelligence and Games. Springer.
Computational Intelligence and AI in Games 8(1),
pages 13–26.
Basile Pierpaolo, de Gemmis Marco, Siciliani Lucia,
and Semeraro Giovanni. 2018. “Overview of the
evalita 2018 solving language games (nlp4fun)
task.” In Caselli Tommaso, Novielli Nicole, Patti
Viviana, and Rosso Paolo, editors, Proceedings of
the 6th evaluation campaign of Natural Language
Processing and Speech tools for Italian
(EVALITA’18), CEUR.org, Turin, Italy.
De Mauro Tullio. 2016. Il Nuovo De Mauro (Online).
Available at: dizionario.internazionale.it.
Ferrucci David A., Levas Anthony, Bagchi Sugato,
Gondek David, and Mueller Erik T. 2013. “Wat-
son: Beyond jeopardy!” In Artif. Intell., 199 pages
93–105.
Lyding Verena, Stemle Egon, Borghetti Claudia, Bru-
nello Marco, Castagnoli Sara, Dell’Orletta Felice,
Dittmann Henrik, Lenci Alessandro, and Pirrelli
Vito. 2014. “The PAISÀ corpus of italian web
texts.” In Proceedings of the 9th Web as Corpus
Workshop (WaC-9), pages 36–43. Association for
Computational Linguistics, Gothenburg, Sweden.
Sangati Federico, Pascucci Antonio, and Monti Jo-
hanna. 2018. “Exploiting multiword expressions to
solve ‘La Ghigliottina’”. In Caselli Tommaso,
Novielli Nicole, Patti Viviana, and Rosso Paolo,
editors, editors, Proceedings of the 6th evaluation
campaign of Natural Language Processing and
Speech tools for Italian (EVALITA’18), Turin, Ita-
ly. CEUR.org.B.
Semeraro Giovanni, Lops Pasquale, Basile Pierpaolo,
and De Gemmis Marco. 2009. “On the tip of my
thought: playing the guillotine game.” In Proceed-
ings of the 21st International Jont Conference on
Artifical Intelligence, IJCAI’09, pages 1543–1548.
Morgan Kaufmann Publishers Inc., San Francisco,
CA, USA.
Silberztein Max. 2018. NooJ Manual, Available for
download at: www.nooj4nlp.net
Squadrone Luca. 2018. “Computer challenges guillo-
tine: how an artificial player can solve a complex
language tv game with web data analysis.” In Ca-
selli Tommaso, Novielli Nicole, Patti Viviana, and
Rosso Paolo, editors, Proceedings of the 6th evalu-
ation campaign of Natural Language Processing
and Speech tools for Italian (EVALITA’18), Turin,
Italy. CEUR.org.H.
Vietri Simonetta. 2014. “The italian module for nooj.”
In Proceedings of the First Italian Conference on
Computational Linguistics, CLiC-it 2014. Pisa
University Press.