Neuronovou sítí na sudoku
Programy na luštění sudoku jsou úspěšné i bez umělé inteligence. Móda hlubokého učení a neuronových sítí však nyní vedla i k implementaci tohoto přístupu.
Rasmus Berg Palm z Dánské technické univerzity nyní podle článku publikovaného na ArXiv využil rekurentní relační sítě z technologie DeepMind. Příslušná neuronová sítě považuje mřížku sudoku 9 x 9 za graf a číslice v políčkách odpovídají uzlům. Celkem 81 uzlů je připojeno hranami k uzlům ve stejném čtverci, řádku a sloupci, tj. každý uzel ke 24 dalším. Rekurentní relační síť se pak školí přenášením zpráv mezi uzly („jsem číslice 7, takže...“). Zajímavé je, že v rámci výpočtu se prý pracuje s distribucí pravděpodobnosti, kterou mají jednotlivé číslice pro umístění na daném políčku (poznámka: některé číslice jsou vyloučeny, mají pravděpodobnost 0, ale i u povolených se zřejmě stanoví různé pravděpodobnosti?).
K vyškolení sítě bylo použito 216 000 zadání sudoku, ta nejtěžší jen se 17 předvyplněnými číslicemi (poznámka: i když vztah mezi obtížností řešení – alespoň pro člověka - a počtem zadaných číslic není zdaleka jednoznačný). Úlohy byly rozděleny na tréninkové, validační a kontrolní. Vyškolená síť dokázala úspěšně vyřešit 97 % těch nejtěžších hádanek, lehčí ve 100 % případů. Samozřejmě by se úspěšnost dala dále zvyšovat.
Podle R. B. Palma nejde ani tak o samotné sudoku, tam máme k dispozici i „normální“ algoritmy, které ta nejtěžší sudoku řeší rozhodně úspěšněji než na 97 %. Popsaný přístup využívající distribuce pravděpodobnosti určitých událostí a vazeb mezi nimi se však prý může uplatnit u samořízených aut a příslušné rekurentní relační sítě se také hodí pro porozumění přirozenému jazyku.
Zdroj: The Register a další
