Solving Crosswords - Databeers Tuscany

Conoscenza

Logica

Intuizione

Risoluzione automatica di giochi• Scacchi

Gianni Barlacchi Pisa, 12 Gennaio 2017

Febbraio 1996

IBM DeepBlue batte il campione assoluto di scacchi Garry Kasparov!

Febbraio 2011

IBM Watson batte i campioni del gioco Jennings & Rutter!

• Jeopardy!

Risoluzione automatica di giochi• GO

Gennaio 2016

GoogleDeep Mind AlphaGo batte il campione Lee Sedol! Gianni Barlacchi Pisa, 12 Gennaio 2017

RISOLVERE I CRUCIVERBA CON

L’INTELLIGENZA ARTIFICIALE

Gianni Barlacchi, Massimo Nicosia, Alessandro Moschitti

Databeers Tuscany, 12 Gennaio 2017

Il gioco del cruciverbaVerticali1. Pontefice2. Nome di donna3. Lega di rame e zinco4. “è” in Latino5. Città della Florida7. Nè mia nè tua9. Fiore12. In nessun tempo

Orizzontali1. Grosso serpente5. Tribunale regionale8. Dischiusi10. Uomo in inglese11. Impronta, traccia13. Malattia14. Desiderio poetico

Per risolvere un cruciverba è necessario avere buone anche abilità logiche!


Risolutori automatici

• PROVERB Primo sistema ideato per la risoluzione automatica

di cruciverba.

• DR. FILL Apparso pubblicamente nel 2012, ad oggi è il più

evoluto risolutore automatico di cruciverba.


Risolutori automatici

• WEBCROW

Ideato e sviluppato nel 2005 dall’Universitàdegli Studi di Siena è stato sponsorizzato da Google

Interroga il web e utilizza vecchi cruciverba per trovare le risposte

Non è riuscito a battere i massimi esperti del gioco.


Inside WebCrow


Trovare le risposte

Risoluzione automatica del cruciverba

• Trovare le risposte

Task particolare di Question Answering

Occorre utilizzare tecniche di Information Retrieval e Natural Language Processing• Recupero di documenti rilevanti• Elaborazione del testo ed estrazione della risposta


Machine Learning per NLP

• Machine learning

Algoritmi che apprendono funzioni da esempi• Ordinare una lista di possibili risposte

Esistono vari approcci• Alberi di decisione• Reti neurali• Metodi Kernel



Recupero della risposta da web

Luogo infuocato (7) : inferno


Recupero della risposta da web

Ci si va al buio (6) : cinema


• Recupero da database di cruciverba risolti

L’esperienza di gioco nella risoluzione di un cruciverba è fondamentale

Con alta frequenza è possibile incontrare clues identiche o simili• <<Un luogo al buio (6): cinema>>• <<Ci si vede i film al buio (6): cinema>>


Inside WebCrow


Trovare le risposte

Compilarela griglia

Vuoi saperne di più?

• Webcrow: A web-based system for crossword solving. M. Ernandes, G. Angelini, M. Gori - AAAI Press. 2005

• Learning to rank answer candidates for automatic resolution of crossword puzzlesG. Barlacchi, M. Nicosia, A. Moschitti - CoNLL 2014

• A Retrieval Model for Automatic Resolution of Crossword Puzzles in Italian LanguageG Barlacchi, M Nicosia, A Moschitti - CLiC-it 2014

• Learning to Rank Aggregated Answers for Crossword PuzzlesM Nicosia, G Barlacchi, A Moschitti - ECIR 2015

• SACRY: Syntax-based Automatic Crossword Puzzle Resolution sYstemG Barlacchi, M Nicosia, A Moschitti - ACL 2015

• Distributional Neural Netrworks for Automatic Resolution of Crosswor PuzzlesA Severyn, M Nicosia, G Barlacchi, A Moschitti - ACL 2015


Che cruciverbista sei?

• Si dice al cameriere (6):

• Simbolo Matematico (3):

• Nota musicale (2):

• E’ la virtù dei forti (8):

G R A Z I E

P E R

L A

P A Z I E N Z A



• Recupero della risposta da web

Il web è una fonte di informazione potenzialmente infinita

La risposta può essere trovata elaborando documenti e snippets recuperati dal motore di ricerca



• Compilare la griglia

II gioco viene formalizzato come un Probabilistic Constraint Satisfaction Problem (Shazeer, 1999)

La griglia viene riempita con la soluzione a massima probabilità.


Le clue possono riguardare qualsiasi argomento• Occorre comprendere la semantica delle parole

La forma della clue è spesso non interrogativa• << Pontefice (4): papa >>

Le clues sono create per essere ambigue• << Luogo infuocato (7) : inferno >>

Il tema può essere fattuale o non fattuale• << Ci si va al buio (6) : cinema >>


Il gioco del cruciverba

Solving Crosswords - Databeers Tuscany

Data & Analytics

Transcript of Solving Crosswords - Databeers Tuscany