Dr. Fill
| Utvecklare | Matt Ginsberg |
|---|---|
| Typ | Korsord programvara |
| Hemsida |
Dr.Fill är ett datorprogram som löser korsord i amerikansk stil . Den utvecklades av Matt Ginsberg och beskrivs av Ginsberg i en artikel i Journal of Artificial Intelligence Research . Ginsberg hävdar i den artikeln att Dr.Fill är bland de femtio bästa korsordslösarna i världen.
Som beskrivits av Ginsberg fungerar Dr.Fill genom att konvertera ett korsord till ett viktat problem med tillfredsställelse av begränsningar och sedan försöka maximera sannolikheten för att fyllningen är korrekt. Sannolikheter för enskilda ord eller fraser i pusslet beräknas med relativt enkla statistiska tekniker baserade på funktioner som tidigare förekomster av ledtråden, antal Google-träffar för fyllningen och så vidare. Genom att göra detta försöker Dr.Fill lösa ett problem som liknar det som hanteras av Jeopardy! -spelar programmet Watson ; Dr.Fill körs på en bärbar dator istället för en superdator och Ginsberg påpekar att Watson är mycket effektivare än Dr.Fill när det gäller att lösa denna del av problemet. Istället för beräkningshästkrafter förlitar sig Dr.Fill på begränsningarna genom att korsa ord för att förfina sina svar.
En mängd olika tekniker från artificiell intelligens används för att försöka hitta den mest sannolika fyllningen. Dessa inkluderar en liten mängd framåtblick , begränsad avvikelsesökning och efterbearbetning. Ginsberg påpekar att efterbehandling valdes framför gren och bunden eftersom de två teknikerna är ömsesidigt inkompatibla och efterbearbetning visade sig vara mer effektiv inom denna domän.
Dr.Fill deltog i den amerikanska korsordsturneringen 2012 och slutade på 141:a plats av cirka 650 deltagare med en totalpoäng på drygt 10 000 poäng. Framträdandet ledde till en mängd olika beskrivningar av Dr.Fill i den populära pressen, inklusive The Economist , San Francisco Chronicle och Gizmodo . En beskrivning av Dr.Fill dök upp på förstasidan av New York Times den 17 mars 2012 .
Dr.Fills poäng 2013 förbättrades till 10 550, vilket skulle ha gett den en 92:a plats. Videor av programmet som löser problemen från turneringen finns tillgängliga på YouTube . Poängen 2014 förbättrades ytterligare till 10 790, vilket skulle ha hamnat på 67:e plats. En video av programmet som löser de första sex pusslen från den turneringen, tillsammans med ett föredrag från Ginsberg som beskriver dess prestation, finns på YouTube.
Dr.Fill har i stort sett fortsatt att förbättras sedan evenemanget 2014. 2015 fick den 10 920 poäng och slutade på 55:e plats. 2016 fick den 11 205 poäng och slutade på 41:a plats. 2017 fick den 11 795 poäng och slutade på 11:e plats. Under 2018 fick den 10 740 poäng och sjönk till 78:e plats. Dr.Fill återgick till "formen" 2019, fick återigen 11 795 poäng och slutade på 14:e plats.
ACPT 2020 ställdes in på grund av COVID-19 och Dr.Fill deltog som icke-tävlande i Boswords-turneringen istället. Programmet överträffade människorna och fick 11 218 poäng (snabba löser med totalt ett misstag) medan den bästa poängen fick 10 994 poäng (långsammare löser men inga misstag).
2021 års ACPT var virtuell, återigen på grund av COVID-19. Dr.Fill-insatsen fick sällskap av Berkeley NLP Group, som skapade ett hybridsystem vid namn Berkeley Crossword Solver , och Dr.Fill vann huvudeventet och fick 12 825 poäng med Erik Agard, den mest poänggivande människan, som fick 12 810 poäng. Turneringen vanns av Tyler Hinman (12 760 poäng), som fullbordade mästerskapspusslet perfekt på tre minuter. Dr.Fill klarade också det pusslet perfekt, men på 49 sekunder.
Efter att ha vunnit turneringen meddelade Ginsberg den 8 augusti 2021 att både han och Dr.Fill skulle dra sig tillbaka från korsord.