Először jött rá magától egy gép, hogyan kell kirakni a Rubik-kockát

Egészen mostanáig nem voltak képesek önállóan kirakni a Rubik-kockát a gépi tanulással dolgozó algoritmusok, a feladvány megoldása ugyanis sokkal összetettebb feladat a mesterséges intelligencia számára, mint például a megfelelő sakklépések kiszámolása. A Kaliforniai Egyetem (Irvine) kutatói azonban kidolgoztak egy új módszert a probléma megoldására.

Az új típusú gépi tanulási metódussal az algoritmus képes volt megtanítani magát a Rubik-kocka megoldására anélkül, hogy emberi segítségre szorult volna. Az új megközelítés jelentősége, hogy áthidal egy eddig megoldatlan informatikai problémát: hogyan oldjon meg a gép komplex feladatokat minimális emberi beavatkozással.

Rubik Ernő játéktervező 1974-ben alkotta meg a háromdimenziós kirakót, amely rövid időn belül világhírűvé vált, és több mint 350 millió darabot adtak el belőle. Nemcsak a nagyközönség, hanem az informatikus és matematikus társadalom figyelmét is egyből felkeltette, és az egyik legizgalmasabb kérdés az lett, hogy mennyi az a minimális lépésszám, amelyből a kocka kirakható. A kérdésre a válasz egy 2007-es bizonyítás szerint 26, egy évvel később ez 22-re csökkent, de a legfrissebb, 2010-es matematikai bizonyítás szerint mindössze 20 lépés kell hozzá, hogy bármely pozícióból kirakhassuk a kockát.

A másik népszerű tudományos kihívás az volt, hogy ki tud olyan algoritmust tervezni, amely képes bármilyen kezdőállapotból kirakni a kockát. Rubik Ernő maga is írt egy ilyen algoritmust nem sokkal az után, hogy feltalálta a játékot.

Eddig minden gépi megoldás ember írta algoritmuson alapult, de az utóbbi időben az informatikusokat inkább az izgatta, hogyan lehet a probléma önálló megoldására képessé tenni a gépet. Az egyik megközelítés a sakkautomatákéhoz hasonló módszerből indult ki: a gépi tanulással dolgozó algoritmus megkapja a játékszabályokat, aztán önmaga ellen játszik. A folyamatban döntő a jutalmazás is, mivel az teszi képessé a gépet, hogy megkülönböztesse a jó lépést a rossztól, azaz segít a gépnek a tanulásban.

Ez a módszer azonban nem működik jól életszerű helyzetekben, mert nehezen meghatározható, mikor jár a jutalom. A Rubik-kockánál például a véletlenszerű forgatásoknál nehéz megítélni, hogy egy-egy átfordítás közelebb visz-e a megoldáshoz. A random fordulatok sokáig követhetik egymást anélkül, hogy eljutnánk a megoldásig, így a végcélért járó jutalmat csak ritkán lehet kiosztani.

A sakkban ezzel szemben viszonylag nagy terük van a döntéseknek, de minden lépés könnyen értékelhető a végcél szempontjából, és így jutalmazható is. A Rubik-kocka esetében azonban nem ez a helyzet.

Autodidakta ismételgetés vezet a sikerhez

Stephen McAleer és munkatársai a Kaliforniai Egyetemről „autodidakta iterációnak” (iteráció: egy eljárás egyre pontosabb értéket adó ismételgetése) nevezték el gépi tanulási módszerüket, amely emberi közreműködés nélkül képes rájönni, hogy kell kirakni Rubik találmányát. Némileg hasonló ez ahhoz a tavalyi áttöréshez, amikor Elon Musk OpenAI algoritmusa némi kezdeti botladozás után maga tanulta ki, hogyan boldoguljon egyre jobban a Dota 2-ben, míg annyira kifinomult nem lett, hogy a profi humán játékosokat is megverte.

A DeepCube-nak nevezett eljárásban az volt a nagy trükk, hogy kitalálták, hogyan jutalmazza a gép saját magát a Rubik-kocka kirakása közben.

Az összekevert kockával szemben álló gépnek először el kell döntenie, hogy egy bizonyos forgatás vajon közelebb áll-e a megoldáshoz, mint az adott konfiguráció. Ehhez képesnek kell lennie a forgatás értékelésére. Az autodidakta iterációval ez úgy működik, hogy a gép a megoldott kockából indul ki, majd visszafelé haladva fejti le azt a kombinációt, amely hasonlít a tervezett mozdulathoz. Ez a folyamat nem tökéletes, de a gépi tanulás segít a rendszernek megállapítani, hogy általában mely forgatások célravezetőbbek a többinél. A kiképzett gép aztán standard keresőalgoritmussal dönti el, melyik kombinációban mi az ajánlott forgatás.

Az eredmény egy figyelemreméltóan jól teljesítő algoritmus, amely az összes random összekevert Rubik-kockát képes volt saját erőből megoldani, átlagosan 30 mozdulatból, ami nagyjából megegyezik, vagy inkább kevesebb, mint az emberi tudáson alapuló algoritmusok megoldáshoz szükséges legkisebb lépésszáma.

McAleerék módszere segíthet abban, hogy a gépi tanulás megbirkózzon olyan, eddig számára nehéz feladatokkal, mint a Sokoban, a Montezuma’s Revenge című játék, illetve a számok prímtényezőkre bontása. McAller és társai most azon dolgoznak, hogy kiterjesszék a kockánál bevált metódust, hogy további kombinatorikai optimalizációs problémák megoldására is szülessenek gépi módszerek.