A keresztrejtvények rengeteg ember számára jelentenek szórakozást: a koncepciót valószínűleg mindenki ismeri, rácsban elrendezett, egymással átfedésben levő szavakat kell megfejteni azokra való utalások alapján. Az ilyen feladványok kapcsán az emberi agy a legutóbbi időkig jelentősen jobbnak bizonyult a gépeknél.
A változás azonban már pár éve megindult. 2017-ben egy Dr Fill nevű gépi algoritmus több mint 600 emberi induló között 11. helyet ért el az amerikai keresztrejtvényfejtők legnagyobb versenyén. Tavaly pedig ugyanezen program továbbfejlesztett változata megnyerte az évente tartott vetélkedést. Az új program, a Berkeley Crossword Solver Eric Wallace, a Kaliforniai Egyetem kutatója és Matt Ginsberg, a Dr Fill program eredeti fejlesztőjének közös munkája.
A 2021-es verseny megnyerése az első alkalom, hogy számítógépes rendszer nyert ezen a vetélkedésen, mondják a fejlesztők, hozzátéve, hogy a program 1100 emberi versenyzőt előzött meg, akik a legjobb amerikai rejtvényfejtők közé tartoznak. A gépi rendszerek számára a rejtvényfejtés legnagyobb nehézségét az adja, hogy a megfejtendő szavakra való utalások nagyon eltérő típusúak lehetnek, és a különböző típusú feladványokat eltérő megközelítéssel lehet megoldani.
Vannak például tudásalapú utalások, amelyekhez a történelem vagy a popkultúra ismerete szükséges. Ilyen például a következő: Az ÉNEKEK ÉNEKE UTÁNI KÖNYV, megfejtés: IZAJÁS. Vannak aztán szójátékok, amikor a hangalakra utal a megfejtés valamilyen módon, pl. PINCE oldalai: PE. És egyebek mellett vannak olyan utalások, amik ellentétes vagy rokonértelmű szóra, esetleg asszociatív kapcsolatra építenek, pl. CSOMÓ: BOG, TALÁL: LEL. A megfejtés ráadásul sokszor többféle lehet mindegyik típus esetében, pl. NINCS NÉLKÜLE IGE: lehet az IGE bármelyik betűje, vagy NEMESFÉM: ebből is többféle van.
A Berkeley Crossword Solver megközelítése a következő. Egy neurális kérdés-válasz algoritmus minden utalásra javasol egy választ egy pontszámmal együtt, ami a megoldás várható helyességét értékeli. Ezt az algoritmust előzőleg egy több mint 6 millió kérdés-válasz párosból álló adatbázison edzették, amelynek bejegyzései az elmúlt 70 év keresztrejtvényeiből származnak. A rendszer egy nyílt forráskódú természetes nyelvfeldolgozót is használ, ami a szavak szegmentálásában segít.
A következő fázisban a rendszer feltölti a javasolt válaszokkal a rácsot. Tökéletes válaszok hiányában ez trükkös folyamat, hiszen több helyen ellentmondások alakulnak ki, amiknél dönteni kell, hogy az ütköző válaszjavaslatok közül melyik a helyes. Ehhez egy olyan eljárást alkalmaz a rendszer, ami a legjobb átfedést biztosító megoldásverziókat helyezi előtérbe a pontszámok alapján való puszta értékelés helyett. A végeredmény általában nagyon közel van a tökéleteshez, bár lehetnek kisebb hibák. A végső szakaszban ezeket javítja ki a program, a rács problémás részein alternatív válaszokat mérlegelve, majd ezeket bepróbálgatva a megoldások közé.
A fejlesztők és a tapasztalatok szerint a rendszer nagyon hatékonyan képes megoldani nagyon változatos keresztrejtvényeket, túlszárnyalva a legjobb emberi fejtőket is. Ez ugyanakkor nem igaz minden keresztrejtvénytípusra. A rendszert ugyanis a New York Timesban megjelenőhöz hasonló keresztrejtvényekre optimalizálták, amiket valóban nagy pontossággal és gyorsan képes megfejteni.
Sokkal rosszabbul boldogul ugyanakkor a például a briteknél népszerű, úgynevezett kriptikus rejtvényekkel, amelyekben minden utalás egy-egy találós kérdésre vagy metanyelvi utalásra épül (pl. Angol keverék egy Izrael melletti magaslat: GOLAN). Vagyis bár a gépek egyre jobbak ebben is, vannak gondolkodási formák, amik még nehezen mennek nekik. Hogy meddig lesz ez így, az ugyanakkor nagy kérdés.
