En maskin har räknat ut Rubiks kub helt av sig själv

Ännu en bastion av mänsklig skicklighet och intelligens har fallit för maskinernas angrepp. En ny typ av djupinlärningsmaskin har lärt sig att lösa en Rubiks kub utan mänsklig hjälp.

Milstolpen är betydande eftersom det nya tillvägagångssättet tar itu med ett viktigt problem inom datavetenskap – hur man löser komplexa problem när hjälpen är minimal.

Först lite bakgrund. Rubiks kub är ett tredimensionellt pussel utvecklat 1974 av den ungerske uppfinnaren Erno Rubik, med syftet att rikta in alla rutor av samma färg på samma yta av kuben. Den blev en internationell bästsäljande leksak och sålde över 350 miljoner enheter.

Pusslet har också väckt stort intresse från datavetare och matematiker. En fråga som har fascinerat dem är det minsta antalet drag som behövs för att lösa det från valfri position . Svaret, bevisat 2014, visar sig vara 26.

En annan vanlig utmaning är att designa algoritmer som kan lösa kuben från vilken position som helst. Rubik själv, inom en månad efter att ha uppfunnit leksaken, kom på en algoritm som kunde göra detta.

Men försök att automatisera processen har alla förlitat sig på algoritmer som har tillverkats för hand av människor.

På senare tid har datavetare försökt hitta sätt för maskiner att själva lösa problemet. En idé är att använda samma typ av tillvägagångssätt som har varit så framgångsrik med spel som schack och Go.

I dessa scenarier får en maskin för djupinlärning spelets regler och spelar sedan mot sig själv. Avgörande är att den belönas vid varje steg efter hur den presterar. Denna belöningsprocess är oerhört viktig eftersom den hjälper maskinen att skilja bra spel från dåligt spel. Med andra ord, det hjälper maskinen att lära sig.

Men detta fungerar inte i många verkliga situationer, eftersom belöningar ofta är sällsynta eller svåra att avgöra.

Till exempel kan slumpmässiga varv av en Rubiks kub inte lätt belönas, eftersom det är svårt att bedöma om den nya konfigurationen är närmare en lösning. Och en sekvens av slumpmässiga vändningar kan pågå under lång tid utan att nå en lösning, så sluttillståndsbelöningen kan bara erbjudas sällan.

I schack, däremot, finns det ett relativt stort sökutrymme men varje drag kan utvärderas och belönas därefter. Det är bara inte fallet för Rubik's Cube.

Ange Stephen McAleer och kollegor från University of California, Irvine. Dessa killar har banat väg för en ny typ av djupinlärningsteknik, kallad autodidaktisk iteration, som kan lära sig att lösa en Rubiks kub utan mänsklig hjälp. Knepet som McAleer och co har bemästrat är att hitta ett sätt för maskinen att skapa sitt eget belöningssystem.

Så här fungerar det. Med tanke på en olöst kub måste maskinen avgöra om ett specifikt drag är en förbättring av den befintliga konfigurationen. För att göra detta måste den kunna utvärdera flytten.

Autodidaktisk iteration gör detta genom att börja med den färdiga kuben och arbeta baklänges för att hitta en konfiguration som liknar det föreslagna draget. Denna process är inte perfekt, men djupinlärning hjälper systemet att ta reda på vilka rörelser som generellt är bättre än andra.

Efter att ha tränats använder nätverket sedan ett standardsökträd för att leta efter föreslagna drag för varje konfiguration.

Resultatet är en algoritm som fungerar anmärkningsvärt bra. Vår algoritm kan lösa 100 % av slumpmässigt förvrängda kuber samtidigt som den uppnår en medianlösningslängd på 30 drag – mindre än eller lika med lösare som använder kunskap om mänskliga domäner, säger McAleer och co.

Det är intressant eftersom det har konsekvenser för en mängd andra uppgifter som djupinlärning har kämpat med, inklusive pussel som Sokoban, spel som Montezumas Revenge och problem som primtalsfaktorisering.

Faktum är att McAleer och co har andra mål i sikte: Vi arbetar på att utöka denna metod för att hitta ungefärliga lösningar på andra kombinatoriska optimeringsproblem, såsom förutsägelse av protein tertiär struktur.

Huruvida dessa problem kommer att vara lika mottagliga för detta tillvägagångssätt är inte klart. De tjänar i allmänhet inte på ett bevis på att de kan lösas i ett litet antal drag, som Rubiks kub-problemet gör. Det fungerade utan tvekan till lagets fördel här.

McAleer och co hävdar att deras tillvägagångssätt är en form av resonemang om problem. De påpekar att en definition av resonemang är: algebraiskt manipulera tidigare förvärvad kunskap för att svara på en ny fråga.

De säger att det är precis vad deras algoritm – kallad DeepCube – gör. Däremot känner konventionella djupinlärningsmaskiner helt enkelt igen vissa mönster. DeepCube kan lära sig själv hur man resonerar för att lösa en komplex miljö med bara ett belöningstillstånd med hjälp av ren förstärkningsinlärning, säger de.

Kanske. Det verkliga testet kommer naturligtvis att vara hur detta tillvägagångssätt hanterar mer komplexa problem som proteinveckning. Vi kommer att titta för att se hur det går.

Ref: arxiv.org/abs/1805.07470 : Att lösa Rubiks kub utan mänsklig kunskap

Dölj