This paper describes the design of an implemented software system intended to accomplish a speci c natural language processing task. The targeted task is a challenge of the Evaluation Campaign of Natural Language Processing and Speech Tools for Italian proposed in 2020. The challenge is to design and implement an arti cial player for the closing game of a popular Italian television show. Given ve words, the goal of the player is to nd a word related to, but also di erent from, the given words. The design of the proposed arti cial player is discussed by presenting the dataset used to acquire su cient linguistic knowledge and by brie y describing the algorithm used to play the game. A preliminary experimental evaluation of the arti cial player is also discussed.
Natural Language Processing (NLP ) is an interdisciplinary research eld that
overlaps computer science, arti cial intelligence, and linguistics. The grand goal
of NLP is to make computers able to process and understand human languages
(e.g., [
Logic programming has been playing a relevant role in NLP since the very
rst studies related to computational linguistics (e.g., [
As a general-purpose logic programming language, Prolog is normally
considered an appropriate option to deal with NLP problems, and it has been e ectively
used to develop complex NLP systems (e.g., [
It is worth noting that inductive logic programming (e.g., [
The rst studies on NLP date back to the 1950s, but the interest on the topic is still high and rapidly increasing because of the large assortment of possible application contexts for NLP. Traditional application contexts for NLP include machine translation, text classi cation, and question answering. In recent years, the advent of mobile technologies and the massive use of social networking services led to the rise of new application contexts, such as sentiment analysis for brand monitoring or for social media monitoring.
The accurate analysis of the targeted application context is crucial for the design and implementation of e ective NLP systems. Actually, it is common opinion that di erent NLP tasks can be best accomplished using di erent approaches. A method to tackle a task typically achieves better performance in that task than in any other task, even if the tasks are closely related.
The software system discussed in this paper is speci cally designed to
accomplish an NLP task related to a popular word game called La Ghigliottina
(Italian for The Guillotine), which is the closing game of one of the most
popular Italian television shows. Given ve words, the goal of the player is to nd
a sixth word related to, but also di erent from, the given ve words. Possible
relationships between the sixth word and each one of the given words include:
being synonyms, being antonyms, or being used in the lyrics of a popular song.
The goal of the NLP system discussed in this paper is to play this game in the
attempt to nd the sixth word related to a given set of ve words. The
challenge to design and implement arti cial players for this game was included as
a task called Ghigliottin-AI in the Evaluation Campaign of Natural Language
Processing and Speech Tools for Italian (EVALITA) [
This paper is organized as follows. Section 2 describes the procedure followed to collect and process the texts used to acquire the needed linguistic knowledge. Section 3 outlines the design of the proposed arti cial player. Section 4 shows and comments some experimental results. Section 5 concludes the paper and discusses planned developments of the arti cial player.
The rst step to implement the arti cial player for the considered word game regarded the preparation of a dataset to acquire su cient linguistic knowledge. The dataset contains texts that were properly cleaned to remove punctuation marks and words that are not used in the game, such as articles and prepositions. After the initial cleaning phase, a set of pairs of words was constructed by considering words that are close to each other in the cleaned texts. For each pair of words, the number of occurrences in the cleaned texts was counted. The collected pairs of words and their number of occurrences are used to play the game, as brie y discussed in Section 3. The remaining of this section describes the initial cleaning phase and the construction of the set of pairs of words. 2.1
The initial cleaning phase is intended to remove, from all considered texts, punctuation marks and words that are not useful to play the game. To this aim, a set of stop words was de ned. The considered stop words are Italian words that are not used in the game, and they are mainly articles and prepositions. All occurrences of stop words were removed by parsing input texts to generate cleaned texts. For each input text, a new cleaned text is produced after the initial cleaning phase. The processing of input texts to remove stop words was also used to replace all punctuation marks with an uncommon symbol, namely $, that is conventionally used to break sentences. Note that, in order to speed up the initial cleaning phase, all input texts were split into separate text les with sizes limited to 1 MB.
The considered word game uses Italian words only, and therefore several texts written in Italian were collected to acquire su cient linguistic knowledge. Various types of texts were chosen from di erent sources to ensure that the words required to play the game were actually contained in the considered texts. Note that some texts were written by Italian authors, while others are professional translations from other languages.
Thirteen freely available books were downloaded from e-book platforms and
cleaned. They are mainly narrative books, and they include Pinocchio, Zeno's
Conscience, Don Quixote, Alice's Adventures in Wonderland, and The Little
Prince. A part of Corpus Paisa [
The titles of all articles included in the Italian edition of Wikipedia were downloaded and cleaned. In addition, 150 complete articles included in the Italian edition of Wikipedia were downloaded and cleaned. The complete articles concern various topics, such as cooking, music, and travels. The articles are all about general knowledge topics because the considered game makes no assumptions on the education level of players.
Several texts containing lists of common compound words were downloaded and cleaned. In Italian, a compound word is a word that is composed of two other words, and the meaning of the compound word is not immediately related to the meanings of the two constituents. For example, sempreverde (Italian for evergreen) is a compound word composed of the two words sempre (Italian for ever ) and verde (Italian for green). Note that a compound word is a regular word, and its two constituents are normally regular words. Therefore, besides considering the compound word sempreverde, the two words sempre and verde can also be considered as two separate words. It is worth noting that the division of compound words into theirs constituents is very useful to play the considered game. Actually, it is common that one of the constituents of a compound word is included in the ve words given to the player, and the sixth word that the player should guess is the second constituent of the compound word. The compound word often represents the only relationships between the two words, and the player is expected to take compound words into account to play the game. Other examples of compound words in Italian are: girasole (Italian for sun ower ), that is composed of the two words gira (Italian for turn) and sole (Italian for sun); lancia amme (Italian for amethrower ), that is composed of the two words lancia (Italian for throw ) and amme (Italian for ames).
In addition to compound words, the considered texts also include lists of idiomatic phrases. Idiomatic phrases are phrases composed of few words that exhibit a speci c semantic cohesion. Idiomatic phrases can belong to various lexical categories, such as nouns, adjectives, and adverbs. For instance, gatto delle nevi (Italian for snowcat ) is used to indicate a vehicle designed to move on snow. This idiomatic phrase sets up a very unusual relationship between the word gatto (Italian for cat ) and the word nevi (Italian for snow ), and such a relationship is very useful to play the considered game. It is common that one of the words of an idiomatic phrase is included in the ve words given to the player, and the sixth word that the player should guess is another word of the idiomatic phrase. Other examples of idiomatic phrases in Italian are: di male in peggio (Italian for from bad to worse); meglio tardi che mai (Italian for better late than never ); and nervi a or di pelle (Italian for nerves on edge).
Finally, the considered texts also include a list of Italian proverbs, which are often used informally and can be very useful to play the considered game. Examples of proverbs include: l'erba del vicino e sempre piu verde (Italian for the grass is always greener on the other side of the fence ); non piangere sul latte versato (Italian for do not cry over spilled milk ); and non dire gatto se non ce l'hai nel sacco (Italian for don't count your chickens before they hatch ). Proverbs create relationships among words that are not found in other contexts. Therefore, the inclusion of a list of proverbs is useful when playing the considered game to take into account common sentences of the everyday language.
Note that the inclusion of compound words, idiomatic phrases, and proverbs is very helpful to play the considered game. Preliminary empirical observations suggest that, on average, at least one of the ve words given to the player is related to a compound word, an idiomatic phrase, or a proverb. 2.2
The player of the considered game is expected to nd relationships among words. Actually, the player is expected to nd a relationship between the guessed word and each one of the given words. For this reason, the texts obtained after the initial cleaning phase are further processed to obtain a set of pairs of words. Such pairs of words are obtained by parsing all cleaned texts and by considering two consecutive words in the same sentence as a pair.
In the remaining of this paper, the rst word of each pair is called token and the second word is called related token. Using this nomenclature, a generic pair of words is denoted as
h token; related token i: For each pair of words, the occurrence of the pair corresponds to the number of times in which the pair is found in the cleaned texts. Given a pair of words, its inverse is the pair of words obtained by swapping the token with the related token. The occurrence of the inverse of a pair equals the occurrence of the original pair. The algorithm to play the considered game outlined in Section 3 uses the available pairs of words and their occurrences. Each one of the given ve words is considered as a token, and the related tokens obtained by the available pairs of words are considered good guesses for the sixth word. The actual answer is chosen randomly among the related tokens with maximum occurrence.
The following example should clarify the roles of tokens, related tokens, and occurrences. Assume that the phrase parcheggiare la macchina (Italian for park the car ) is found in a text. During the cleaning process, the article (namely, la) is removed, so that the two words parcheggiare and macchina are close to each other in the cleaned text. Then, the pair
h parcheggiare; macchina i is created and added to the dataset, where parcheggiare is considered as token and macchina is considered as related token. Assuming that this pair of words is found 5 times in the cleaned texts, the occurrence of the pair is equal to 5. Since the two words should be considered as related regardless of which is the token and which is the related token, the inverse pair h macchina; parcheggiare i (3) is also created and added to the dataset. The occurrence of the inverse pair is equal to the occurrence of the direct pair, which is 5. The direct pair ensures that, if parcheggiare is given, then macchina is a valid guess for the sixth word. Similarly, the inverse pair guarantees that, if macchina is given, then parcheggiare is a good guess for the sixth word.
All pairs of words obtained from the cleaned texts described at the beginning of this section were persistently stored together with their respective occurrences to provide the needed dataset to the arti cial player. The current dataset contains more than 34;000 tokens, and each token is matched with a number of related tokens between 100 and 1;000. (1) (2)
This section outlines the algorithm that is currently implemented in the arti cial player for the considered word game. The algorithm works on a set of ve words, and it returns the chosen guess for the sixth word. A preliminary experimental evaluation of the performance of this algorithm is discussed in Section 4.
The algorithm can be brie y summarized as follows. Each one of the ve words is treated as a token of a word pair and it is searched in the dataset obtained using the method discussed in the previous section. To simplify the notation, it is assumed that all ve tokens are found in the dataset. The set of ve tokens is denoted as ftigi5=1, and, for each token ti, with 1 i 5, the set of its related tokens is denoted as Ri. All related tokens of the ve tokens are considered as valid guesses for the sixth word. Actually, the sixth word is searched in the following set In order to choose the returned sixth word among the related tokens in R, each related token in R is associated with two numeric values, called frequency and match. The values of frequency and match of each related token in R are used to choose the sixth word.
In order to properly de ne the frequency, let rj be a generic element of R. If the pair h ti; rj i is found in the dataset, then it is associated with oi;j, which equals the occurrence of the pair. Otherwise, the pair is conventionally associated with oi;j = 0. The frequency of the generic related token rj, denoted as fj, is evaluated as the sum of the occurrences (4) (5) Possible values for the frequency of a generic related token rj are positive inte5 ger numbers. Note that the frequency fj increases as the occurrences foi;jgi=1 increase. Hence, the chosen sixth word is expected to have a large frequency.
The match of the generic related token rj of R, denoted as mj, is the number of tokens for which rj is a related token. In other words, the match of the generic related token rj is computed as the count of the pairs of words h ti; rj i that found in the dataset. Possible values for the match of a generic related token rj are integer numbers from 1 to 5, where mj = 1 if rj is the related token of only one of the given words, and mj = 5 if rj is the related token of all given words.
Frequency and match are evaluated for each related token rj in R, and they are used to decide which related token should be selected as sixth word. First, the set of guesses for the sixth word is restricted to the related tokens with the largest match. Then, the sixth word is chosen among the related tokens with the largest frequency. If two ore more related tokens share the same frequency, then the sixth word is chosen at random among them.
The following example should explain the roles of the frequency and the match of a related token, and it should clarify the approach behind the algorithm used by the player. Given a set of ve words ftigi5=1, consider a simple dataset composed of the following pairs of words h t1; r1 i; h t1; r2 i; h t1; r3 i; h t1; r4 i h t2; r1 i; h t2; r3 i; h t2; r4 i h t3; r1 i; h t3; r2 i; h t3; r4 i h t4; r1 i; h t4; r3 i; h t4; r4 i; h t4; r5 i h t5; r1 i; h t5; r4 i; h t5; r6 i; h t5; r7 i; h t5; r8 i Note that only the pairs of words related to the input words are listed in order to simplify the discussion of the example. Normally, a useful dataset contains a lot of other pairs of words.
For each pair of words hti; rji in the dataset, with 1 i 5 and 1 j 8, assume that its occurrence oi;j has the following values o1;1 = 2; o1;2 = 1; o1;3 = 2; o1;4 = 1 o2;1 = 1; o2;3 = 2; o2;4 = 2 o3;1 = 5; o3;2 = 4; o3;4 = 8 o4;1 = 3; o4;3 = 3; o4;4 = 7; o4;5 = 1 o5;1 = 7; o5;4 = 8; o5;6 = 5; o5;7 = 1; o5;8 = 9 (7) (6) (9) Consider now, for example, the related token r1. The frequency f1 of the related token r1 is where o3;3 and o5;3 equal 0 because r3 is neither a related token of t3 nor of t5. Since r3 is a related token of three tokens, the match m3 of r3 equals 3. Finally, consider the related token r8. Since r8 is a related token of t5 only, the frequency f8 of r8 equals o5;8 = 9. For the same reason, the match m8 of r8 equals 1.
Among the eight related tokens considered in the example, r1 and r4 are those with the largest match. Actually, r1 and r4 are related tokens of each one of the ve tokens ftigi5=1, so that m1 = m4 = 5. Since the frequency of r1 is f1 = 18 and the frequency of r4 is f4 = 26, the sixth word guessed by a player that uses the discussed algorithm is r4.
Note that, in order to simplify the notation, the description of the algorithm summarized in this section assumes that all input words are actually found in the dataset. However, rare input words may not appear in the dataset in real situations. In this case, the proposed algorithm does not change signi cantly, and the rare words are simply removed from the set of input words.
In order to preliminary assess the performance of the algorithm brie y discussed in the previous section, 100 instances of the considered game were played by the implemented arti cial player. The considered instances were taken from the instances that were played in the television show. The success rate of the current version of the arti cial player over the considered instances was 24%.
The following is an example of an instance of the game in which the player found the correct sixth word. The given ve words are: { Chimico (Italian for chemical ) { Polizia (Italian for police) { Segreto (Italian for secret ) { Cambio (Italian for change) { Commercio (Italian for commerce) The correct sixth word, as found by the arti cial player, is agente (Italian for agent ). Actually, one can say in Italian: agente chimico (Italian for chemical agent ); agente di polizia (Italian for police o cer ); agente segreto (Italian for secret agent ); agente di cambio (Italian for stockbroker ); and agente di commercio (Italian for sales agent ).
The following is an example of an instance of the game in which the player did not nd the correct sixth word. The given ve words are: { Male (Italian for evil ) { Perdere (Italian for lose) { Ordine (Italian for order ) { Campo (Italian for eld ) { Natura (Italian for Nature) In this case, the correct sixth word is forza (Italian for force). Actually, in Italian one can say: forza del male (Italian for force of evil ); perdere forza (Italian for lose strength); forza dell'ordine (Italian for law enforcement ); forza in campo (Italian for ground force); and forza della natura (Italian for force of nature). Instead, the sixth word proposed by the arti cial player was gioco (Italian for game). Although the proposed sixth word is wrong, it is worth noting that it is strongly related to some of the ve words. Actually, one can say in Italian: perdere un gioco (Italian for loose a game); and campo di gioco (Italian for playing eld ).
Currently, the arti cial player can be interfaced using a Telegram chatbot that was speci cally created for the purpose. The user sends the message /start to the chatbot to start a new session. Then, the user can send to the chatbot commands or lists of ve words. Supported commands are: /myname, to have the chatbot reply with a short greeting message; and /modegame to have the chatbot reply with a short message explaining how to play the game. Messages that do not start with commands are interpreted as lists of ve words. When a list of ve words is received, the chatbot queries the arti cial player and replies to the user with the sixth word chosen by the arti cial player. Normally, the arti cial player chooses the sixth word in less than a second.
(a) (b)
Fig. 1 shows two screenshots of the Telegram chatbot. Fig. 1a shows an instance of the game in which the arti cial player found the correct sixth word. The ve words were: { Amore (Italian for love) { Fascia (Italian for sash) { Oro (Italian for gold ) { Tenera (Italian for tender ) { Maggiore (Italian for major ) The correct sixth word, as proposed by the arti cial player, was eta (Italian for age). As a matter of fact, one can say in Italian: eta dell'amore (Italian for age of love); fascia d'eta (Italian for age range); eta dell'oro (Italian for golden age); tenera eta (Italian for early age); and maggiore eta (Italian for age of majority ). { Entrare (Italian for enter ) { Auguri (Italian for wishes) { Netto (Italian for net ) { Pagamento (Italian for payment ) { Accademico (Italian for academic) In this case, the correct sixth word was ritardo (Italian for delay ). As a matter of fact, one can say in Italian: entrare in ritardo (Italian for enter late); auguri in ritardo (Italian for belated wishes ); in netto ritardo (Italian for in net delay ); pagamento in ritardo (Italian for late payment ); and ritardo accademico (Italian for academic quarter ). Instead, the sixth word proposed by the arti cial player was interesse (Italian for interest ). Although the proposed sixth word was wrong, it is worth noting that it is strongly related to some of the ve words. As a matter of fact, one can say in Italian: interesse netto (Italian for net interest ) and pagamento di interesse (Italian for interest payment ). 5
This paper discussed the design of an arti cial player for a word game that
has been used as closing game in a popular Italian television show since 2005.
Given ve words, the goal of the player is to nd a new word related to, but
also di erent from, the given ve words within a short period of time (normally,
one minute). The challenge to design and implement an arti cial player for this
game was proposed at EVALITA 2020 [
It is worth noting that human players often fail when they play the considered game. Hence, while a success rate of 24% seems low, it can be considered encouraging. Therefore, various developments have already been planned to improve the success rate of the discussed player. Future developments of the player include the extension of the dataset and the use of additional metrics to compare words. For example, the introduction of appropriate weighting factors is planned to give more relevance to the pairs of words obtained from compound words and idiomatic phrases. Finally, a detailed analysis of the game instances in which the player fails is planned for the near future to better understand the strengths and the weaknesses of the adopted approach.