En maskin har funnet ut Rubiks kube helt av seg selv

Nok en bastion av menneskelig dyktighet og intelligens har falt for maskinenes angrep. En ny type dyplæringsmaskin har lært seg å løse en Rubiks kube uten menneskelig hjelp.

Milepælen er betydelig fordi den nye tilnærmingen takler et viktig problem innen informatikk – hvordan løse komplekse problemer når hjelpen er minimal.

Først litt bakgrunn. Rubiks kube er et tredimensjonalt puslespill utviklet i 1974 av den ungarske oppfinneren Erno Rubik, og målet er å justere alle firkanter av samme farge på samme side av kuben. Det ble et internasjonalt bestselgende leketøy og solgte over 350 millioner enheter.

Puslespillet har også tiltrukket seg betydelig interesse fra informatikere og matematikere. Et spørsmål som har fascinert dem er det minste antallet trekk som trengs for å løse det fra en hvilken som helst posisjon . Svaret, bevist i 2014, viser seg å være 26.

En annen vanlig utfordring er å designe algoritmer som kan løse kuben fra hvilken som helst posisjon. Rubik selv, innen en måned etter å ha funnet opp leken, kom opp med en algoritme som kunne gjøre dette.

Men forsøk på å automatisere prosessen har alle basert seg på algoritmer som er håndlaget av mennesker.

Nylig har informatikere forsøkt å finne måter maskiner kan løse problemet på selv. En idé er å bruke samme type tilnærming som har vært så vellykket med spill som sjakk og Go.

I disse scenariene får en dyplæringsmaskin spillereglene og spiller deretter mot seg selv. Det er avgjørende at det belønnes på hvert trinn i henhold til hvordan det presterer. Denne belønningsprosessen er enormt viktig fordi den hjelper maskinen til å skille godt spill fra dårlig spill. Med andre ord hjelper det maskinen å lære.

Men dette fungerer ikke i mange virkelige situasjoner, fordi belønninger ofte er sjeldne eller vanskelige å bestemme.

For eksempel kan tilfeldige svinger av en Rubiks kube ikke lett belønnes, siden det er vanskelig å bedømme om den nye konfigurasjonen er nærmere en løsning. Og en sekvens av tilfeldige svinger kan fortsette i lang tid uten å nå en løsning, så sluttstatsbelønningen kan bare tilbys sjelden.

I sjakk er det derimot et relativt stort søkerom, men hvert trekk kan evalueres og belønnes deretter. Det er bare ikke tilfellet for Rubik's Cube.

Skriv inn Stephen McAleer og kolleger fra University of California, Irvine. Disse gutta har utviklet en ny type dyplæringsteknikk, kalt autodidaktisk iterasjon, som kan lære seg selv å løse en Rubiks kube uten menneskelig hjelp. Trikset som McAleer og co har mestret er å finne en måte for maskinen å lage sitt eget belønningssystem.

Slik fungerer det. Gitt en uløst kube, må maskinen bestemme om et spesifikt trekk er en forbedring av den eksisterende konfigurasjonen. For å gjøre dette må den kunne evaluere flyttingen.

Autodidaktisk iterasjon gjør dette ved å starte med den ferdige kuben og jobbe bakover for å finne en konfigurasjon som ligner på det foreslåtte trekket. Denne prosessen er ikke perfekt, men dyp læring hjelper systemet med å finne ut hvilke bevegelser som generelt er bedre enn andre.

Etter å ha blitt opplært, bruker nettverket deretter et standard søketre for å lete etter foreslåtte trekk for hver konfigurasjon.

Resultatet er en algoritme som yter bemerkelsesverdig godt. Algoritmen vår er i stand til å løse 100 % av tilfeldig krypterte kuber samtidig som den oppnår en median løsningslengde på 30 trekk – mindre enn eller lik løsere som bruker kunnskap om menneskelig domene, sier McAleer og co.

Det er interessant fordi det har implikasjoner for en rekke andre oppgaver som dyp læring har slitt med, inkludert oppgaver som Sokoban, spill som Montezumas Revenge og problemer som primtallsfaktorisering.

Faktisk har McAleer og co andre mål i kikkerten: Vi jobber med å utvide denne metoden for å finne omtrentlige løsninger på andre kombinatoriske optimaliseringsproblemer som forutsigelse av protein tertiær struktur.

Hvorvidt disse problemene vil være like mottagelige for denne tilnærmingen er ikke klart. De har vanligvis ikke nytte av et bevis på at de kan løses i et lite antall trekk, slik Rubiks kube-problemet gjør. Det fungerte utvilsomt i lagets favør her.

McAleer og co hevder at deres tilnærming er en form for resonnement om problemer. De påpeker at en definisjon av resonnement er: algebraisk manipulering av tidligere ervervet kunnskap for å svare på et nytt spørsmål.

De sier at dette er nøyaktig hva algoritmen deres – kalt DeepCube – gjør. Derimot gjenkjenner konvensjonelle dyplæringsmaskiner ganske enkelt visse mønstre. DeepCube er i stand til å lære seg selv å resonnere for å løse et komplekst miljø med kun én belønningstilstand ved å bruke ren forsterkende læring, sier de.

Kanskje. Den virkelige testen vil selvfølgelig være hvordan denne tilnærmingen takler mer komplekse problemer som proteinfolding. Vi følger med for å se hvordan det fungerer.

Ref: arxiv.org/abs/1805.07470 : Løse Rubiks kube uten menneskelig kunnskap

gjemme seg