Mašina sama složila Rubikovu kocku

Za razliku od poteza u šahu, promene položaja delova Rubikove kocke teško je proceniti i predvideti zbog čega je mašinama zasnovanim na dubokom učenju bilo teško da je same slože. Sve do sada. Možemo reći da je još jedan bastion ljudske veštine i inteligencije pao pod napadom mašina. Nova vrsta mašine zasnovane na dubokom učenju sama je naučila da složi Rubikovu kocku bez bilo kakve pomoći ljudi. Takva prekretnica je izuzetno značajna jer se odnosi na važan problem u računarskoj nauci – kako rešiti kompleksne probleme kad je pomoć minimalna. Prvo da kažemo nešto o istorijatu igračke. Rubikova kocka je trodimenzionalna zagonetka koju je 1974. godine razvio mađarski pronalazač Erno Rubik. Cilj je složiti sve delove iste boje na istoj strani kocke. Ubrzo je postala najpopularnija igračka na svetu i prodato je preko 350 miliona primeraka. Privukla je i izuzetnu pažnju računarskih stručnjaka i matematičara. Svi su bili zainteresovani da odgovore na jedno pitanje, a to je: Koliki je najmanji broj poteza koji su potrebni da bi se kocka složila bez obzira na prvobitni položaj delova od kojih se kocka sastoji. Do odgovora se došlo 2014. godine – najmanji broj poteza je 26.

Drugi izazov sa kojim su se suočili stručnjaci je stvaranje algoritma koji bi složio kocku bez obzira na polazni položaj delova. Posle mesec dana od stvaranja igračke, i njen tvorac Rubik je pronašao takav algoritam. Međutim, svi pokušaji da se proces automatizuje oslanjali su se na algoritme koje su prethodno stvorili ljudi. Stručnjaci u računarskoj nauci nedavno su pokušali da pronađu metode pomoću kojih bi mašine mogle same da rešavaju probleme. Prva zamisao je bila da se iskoristi isti pristup koji je vrlo uspešno primenjen u slučaju šaha i igre „ Go“.

U ta dva slučaja, mašinama zasnovanim na dubokom učenju data su pravila igre, posle čega su one igrale same protiv sebe. Najvažnije je spomenuti da je svaki njihov korak nagrađivan u zavisnosti od uspešnosti. Taj proces nagrađivanja je izuzetno važan jer pomaže mašinama da naprave razliku između dobrih i loših poteza. Drugim rečima, taj proces je mašinama olakšavao učenje.

Međutim, postupak nagrađivanja ne funkcioniše u mnogim životnim prilikama jer je retko kad или vrlo teško odrediti da li nešto treba nagraditi или ne.
Na primer, nasumična okretanja Rubikove kocke ne mogu se tako lako nagraditi jer je vrlo teško ustanoviti da li je nov položaj delova bliži konačnom rešenju. Štaviše, niz nasumičnih pomeranja delova može se obavljati izvesno vreme, a da nismo ništa bliži konačnom rešenju, tako da se proces nagrađivanja do konačnog cilja može retko kad primeniti.

Za razliku od Rubikove kocke, u šahu postoji široko polje delovanja, ali svaki pokret može biti odmah procenjen i prema tome nagrađen. Međutim, to nije slučaj sa Rubikovom kockom.

Stiv Makalir je sa kolegama sa Kalifornijskog univerziteta uspeo da stvori novu tehniku dubokog učenja, nazvanu „autodidaktičko ponavljanje“, koja mašinama omogućava da same, bez pomoći ljudi, nauče kako da slože Rubikovu kocku. Naime, Makalir je sa kolegama uspeo da pronađe postupak koji bi omogućio mašinama da same stvore sistem nagrađivanja.

Evo kako proces funkcioniše. Kad mašini date da složi kocku, ona sama mora da odluči da li je njen potez pri slaganju dovodi bliže rešenju. Da bi to mogla da uradi, mora da bude sposobna da proceni potez.

Autodidaktičko ponavljanje zbog toga počinje od složene kocke i kreće se unazad da bi pronašlo konfiguraciju koja je slična predloženom potezu. Proces nije savršen, ali duboko učenje pomaže sistemu da shvati koji su potezi bolji od nekih drugih.

Pošto mreža prođe takvu obuku, počinje da koristi standardno stablo pretraživanja u potrazi za predloženim potezima za svaku konfiguraciju.
Rezultat takvog postupka je algoritam koji izuzetno dobro funkcioniše. „Naš algoritam je 100% uspešan u rešavanju svih nasumičnih rasporeda delova kocke, a prosečni broj poteza je 30, dakle manje или isto onoliko koliko je potrebno ljudima“, rekao je Makalir.

Njihovo dostignuće je vrlo zanimljivo jer može da pomogne pri rešavanju mnogih problema koje duboko učenje pokušava da reši, uključujući zagonetke kao što su „Sokoban“, igrice kao što je „Osveta Montezume“ или faktorizaciju prostih brojeva.

Zapravo, Makalir i njegove kolege imali su sasvim drugačije namere i ciljeve: „Radimo na proširivanju metoda da bismo pronašli približna rešenja za ostale probleme kombinatoričke optimizacije kao što je predviđanje tercijarne strukture proteina.“

Nije sasvim jasno da li će problemi moći da budu rešeni pomoću takvog pristupa jer kod njih nije glavni cilj smanjiti broj poteza kao što je to slučaj kod Rubikove kocke, ali, svakako, ide u prilog Makalirovom timu.

Kako tvrde, njihov pristup je oblik rasuđivanja o problemima. Ističu da jedna od definicija rasuđivanja glasi: algebarsko upravljanje prethodno stečenim znanjem da bi se dobio odgovor na pitanje sa kojim se do tada nismo susretali.

U stvari, to je ono što njihov algoritam, nazvan DeepCube, radi. S druge strane, konvencionalne mašine zasnovane na dubokom učenju prepoznaju utvrđene šablone. „DeepCube može sam sebe da nauči kako da rasuđuje da bi rešio kompleksno okruženje uz samo jednu nagradu koristeći obično pojačano učenje“, izjavili su.

Recimo da je tako. Pravi test će biti kad takav pristup budu koristili za rešavanje kompleksnijih problema, kao što je proteinsko savijanje. Videćemo koliko će algoritam, u tom slučaju, biti uspešan.

4923-masina-sama-slozila-rubikovu-kocku