I helgen fikk et dataprogram, «Dr. Fill», lov til å prøve seg i USAs største kryssordturnering, American Crossword Puzzle Tournament, mot USAs antatt 600 beste kryssordløsere.
Dr. Fill er utviklet av Matt Ginsberg, til daglig toppsjef i On Time Systems som leverer ruteoptimaliseringsløsninger til blant annet USAs luftforsvar. Ginsberg har en doktorgrad innen kunstig intelligens, og har tidligere undervist ved prestisjeuniversitetet Stanford.
Forskere innen kunstig intelligens har i liten grad vært opptatt av kryssord, i motsetning til for eksempel sjakk og spørrekonkurranser. Ifølge Boston Globe ble et program kalt Proverb utviklet ved Duke University i 1999 for å løse kryssord, og ville ha oppnådd plassering nummer 147 av 255 deltakere dersom den hadde deltatt i USAs kryssordturnering det året.
Dr. Fill ble ikke anerkjent som offisiell deltaker i helgens kryssordkonkurranse, men ville ha oppnådd en 141. plass. Ginsberg hadde på forhånd håpet på en plass blant de 50 beste, men garanterte at han ville havne blant de 150 beste av 600. Det greide han altså, så vidt.
Ginsberg har beskrevet hvordan Dr. Fill virker i en artikkel i Journal of Artificial Intelligence Research: Crosswords and an Implemented Solver for Singly Weighted CSPs (pdf, 36 sider). CSP står for «constraint satisfaction problems», det vil utfordringer («problem») som må løses ved å tilfredsstille («satisfaction») bestemte begrensninger («constraint»).
Dr. Fill prøver ikke å løse kryssord på menneskelig vis. Programmet har en database som blant annet omfatter alle amerikanske kryssord siden 1990, med stikkord og løsninger, samt ordbøker. Algoritmen går gjennom databasen på jakt etter ord som svarer til «begrensningene» gitt av kryssordoppgaven, det vil si stikkord, ordlengde og pålagte bokstaver som følge av allerede løste stikkord. Med andre ord: Massiv prøving og feiling, og diverse sannsynlighetsbaserte utvalgskriterier. I motsetning til sjakkprogrammer og «Watson» – IBMs Jeopardy-vinnende superklynge – er det ingen innebygget læring av erfaring.
Etter turneringen sa Ginsburg til New York Times at Dr. Fill, i tillegg til kjente problemer med å forstå humor – amerikanske kryssord kan ha ordspill som svar, for eksempel «Bunny and Clyde» – også lot seg vippe av pinnen av utradisjonelle løsninger. Dette skjedde i oppgavene 2 og 5 (av 6) på lørdag: Oppgave 2 hadde et stort antall ord som skulle staves baklengs, mens oppgave 3 også hadde løsningsord som gikk på skrå. Selv om Dr. Fill søndag morgen greide en perfekt løsning på oppgave 7, var den samlede prestasjonen altfor svak til å bli med i finalen, som for tredje år på rad ble vunnet av Dan Feyer.
