En maskine har fundet ud af Rubiks terning helt af sig selv

Endnu en bastion af menneskelig dygtighed og intelligens er faldet for maskinernes angreb. En ny slags dyb-læringsmaskine har lært sig selv at løse en Rubiks terning uden menneskelig hjælp.

Milepælen er vigtig, fordi den nye tilgang tackler et vigtigt problem inden for datalogi - hvordan man løser komplekse problemer, når hjælpen er minimal.

Først lidt baggrund. Rubiks terning er et tredimensionelt puslespil udviklet i 1974 af den ungarske opfinder Erno Rubik, hvor formålet er at justere alle firkanter af samme farve på den samme flade af terningen. Det blev et internationalt bedst sælgende legetøj og solgte over 350 millioner enheder.

Puslespillet har også tiltrukket sig betydelig interesse fra dataloger og matematikere. Et spørgsmål, der har fascineret dem, er det mindste antal træk, der er nødvendigt for at løse det fra enhver position . Svaret, bevist i 2014, viser sig at være 26.

En anden almindelig udfordring er at designe algoritmer, der kan løse kuben fra enhver position. Rubik selv kom inden for en måned efter at have opfundet legetøjet med en algoritme, der kunne gøre dette.

Men forsøg på at automatisere processen har alle været afhængige af algoritmer, der er blevet håndlavet af mennesker.

For nylig har dataloger forsøgt at finde måder, hvorpå maskiner selv kan løse problemet. En idé er at bruge den samme slags tilgang, som har været så vellykket med spil som skak og Go.

I disse scenarier får en dyb-læringsmaskine spillets regler og spiller derefter mod sig selv. Det er afgørende, at det belønnes ved hvert trin efter, hvordan det præsterer. Denne belønningsproces er enormt vigtig, fordi den hjælper maskinen med at skelne godt spil fra dårligt spil. Det hjælper med andre ord maskinen til at lære.

Men dette virker ikke i mange situationer i den virkelige verden, fordi belønninger ofte er sjældne eller svære at bestemme.

For eksempel kan tilfældige drejninger af en Rubik's Cube ikke let belønnes, da det er svært at bedømme, om den nye konfiguration er tættere på en løsning. Og en sekvens af tilfældige vendinger kan fortsætte i lang tid uden at nå frem til en løsning, så slutstatsbelønningen kan kun tilbydes sjældent.

I skak er der derimod et relativt stort søgerum, men hvert træk kan evalueres og belønnes i overensstemmelse hermed. Det er bare ikke tilfældet for Rubik's Cube.

Indtast Stephen McAleer og kolleger fra University of California, Irvine. Disse fyre har været banebrydende for en ny form for dyb-læringsteknik, kaldet autodidaktisk iteration, der kan lære sig selv at løse en Rubiks terning uden menneskelig hjælp. Det trick, som McAleer og co har mestret, er at finde en måde, hvorpå maskinen kan skabe sit eget belønningssystem.

Sådan fungerer det. Givet en uløst terning, skal maskinen beslutte, om et specifikt træk er en forbedring af den eksisterende konfiguration. For at gøre dette skal den være i stand til at evaluere flytningen.

Autodidaktisk iteration gør dette ved at starte med den færdige terning og arbejde baglæns for at finde en konfiguration, der ligner det foreslåede træk. Denne proces er ikke perfekt, men dyb læring hjælper systemet med at finde ud af, hvilke bevægelser der generelt er bedre end andre.

Efter at være blevet trænet, bruger netværket derefter et standard søgetræ til at jage efter foreslåede træk for hver konfiguration.

Resultatet er en algoritme, der fungerer bemærkelsesværdigt godt. Vores algoritme er i stand til at løse 100 % af tilfældigt kodede terninger, mens den opnår en median løsningslængde på 30 træk – mindre end eller lig med løsere, der anvender viden om menneskeligt domæne, siger McAleer og co.

Det er interessant, fordi det har implikationer for en række andre opgaver, som deep learning har kæmpet med, herunder gåder som Sokoban, spil som Montezumas hævn og problemer som primtalsfaktorisering.

Faktisk har McAleer og co andre mål i kikkerten: Vi arbejder på at udvide denne metode til at finde omtrentlige løsninger på andre kombinatoriske optimeringsproblemer såsom forudsigelse af protein tertiær struktur.

Hvorvidt disse problemer vil være lige så modtagelige for denne tilgang, er ikke klart. De har generelt ikke gavn af et bevis på, at de kan løses i et lille antal træk, som Rubik's Cube-problemet gør. Det virkede uden tvivl til holdets fordel her.

McAleer og co hævder, at deres tilgang er en form for ræsonnement om problemer. De påpeger, at en definition af ræsonnement er: algebraisk manipulation af tidligere erhvervet viden for at besvare et nyt spørgsmål.

De siger, at det er præcis, hvad deres algoritme - kaldet DeepCube - gør. I modsætning hertil genkender konventionelle deep learning-maskiner ganske enkelt bestemte mønstre. DeepCube er i stand til at lære sig selv at ræsonnere for at løse et komplekst miljø med kun én belønningstilstand ved hjælp af ren forstærkningslæring, siger de.

Måske. Den virkelige test vil selvfølgelig være, hvordan denne tilgang håndterer mere komplekse problemer såsom proteinfoldning. Vi vil se for at se, hvordan det gør.

Ref: arxiv.org/abs/1805.07470 : Løsning af Rubiks terning uden menneskelig viden

skjule