Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie

Algoritme leert zelf Rubiks kubus oplossen

Robots die Rubiks kubus kunnen oplossen, zijn er al langer, maar onderzoekers hebben nu een algoritme ontwikkeld dat zichzelf aanleert hoe de klus moet worden geklaard zonder inbreng van de mens. DeepCube maakt hiervoor zijn eigen beloningssysteem.

Bij het inzetten van deep learning voor bijvoorbeeld schaken of go kunnen systemen leren winnen met alleen kennis van de spelregels, door een beloningssysteem. Bij elke zet evalueren algoritmes de invloed op het spel en op basis van waarderingen kunnen machines zo goed leren spelen.

Bij Rubiks kubus is het voor een algoritme lastig te bepalen of een willekeurige handeling het dichter bij de oplossing brengt of niet, schrijft Technology Review. Onderzoekers van de Universiteit van Californië in Irvine maken daarom gebruik van een deeplearningtechniek met de naam 'autodidactische iteraties'. Hierbij begint het algoritme met een al opgeloste kubus en werkt het terug naar andere configuraties om een idee te krijgen welke handelingen naar de oplossing toewerken en welke niet.

Na training kan het honderd procent van de willekeurig geconfigureerde kubussen oplossen, in gemiddeld dertig handelingen. Volgens de onderzoekers kan hun werk behulpzaam zijn bij het zelf laten oplossen door systemen van bijvoorbeeld puzzelspel Sokoban en het spel Montezuma’s Revenge, maar ook voor het ontbinden in factoren. Daarnaast hopen ze hun techniek te kunnen inzetten voor complexere problemen, zoals het voorspellen van de tertiaire structuur van eiwitten.

De wetenschappers beschrijven hun onderzoek in de paper Solving the Rubik's Cube Without Human Knowledge.

Door Olaf van Miltenburg

Nieuwscoördinator

15-06-2018 • 17:06

38 Linkedin Google+

Reacties (38)

Wijzig sortering
Wat een gaaf artikel! Maar toch zie je dat het bewezen minimum van 20 bewegingen wordt overschreden. Dus het is nog niet het meest efficient in de te maken bewegingen, maar damn... met maar een factor 2 overschreiding een probleem met >1019 mogelijkheden en 1 oplossing, oplossen geeft wel aan dat dit als methode heel krachtig kan zijn. De mediaan van de oplosssnelheid ligt op 1 kubus 10 min-1. Ik denk dat eiwitten nog wel een brug te ver zijn met de huidige setup, maar de gebruikte methode is echt wel vernieuwend.
Het leert zelf dus het begin is er. Daarnaast met toenemende cpu kracht zal de leersnelheid ook omhoog gaan.
De training vond plaats op een machine met een 32-core Intel Xeon E5-2620 met 3 Titan XPs, en duurde 44 uur. Bron: de gelinkte paper.
Er is ook een officiële wedstrijd om een 3x3x3 met zo min mogelijk stappen op te lossen, het record van een gemiddelde van 3 is 24 stappen. Met een gemiddelde van 30 zou DeepCube op een gedeelde 105e plek komen.
https://www.worldcubeasso...2BPersons&average=Average
Ik vind het altijd zo vreemd om te lezen "zonder inbreng van de mens". Het gehele algoritme waarvan de AI leert, werd door mensen geschreven. Elke software is dan instaat zonder menselijke inbreng zijn taak te voltooien: het werd in het verleden geprogrammeerd en voert nu uit wat het moet doen.
Het gaat bij dit soort zaken vooral waar de trainings dataset vandaan komt. In dit geval bedoelen ze zonder menselijke inbreng dat de trainings dataset volledig wordt gevult door het algoritme zelf en daarmee een reward systeem ontwikkeld waarmee vervolgens "nieuwe" problemen kunnen worden opgelost. (unsupervised learning)

Wat meestal wordt gedaan is dat trainingsdata afkomstig is van mensen die een vergelijkbaar probleem hebben opgelost met een bijhorende uitkomst + reward (supervised learning)
Volgensmij werken een hoop van die andere rubikscube solvers ook gewoon zonder inbreng van de mens.
Zijn gebaseerd op tabellen die aangeven hoe bepaalde translaties gerealiseerd moeten worden. Die tabellen zijn gegenereerd door algoritmes die door mensen zijn beschreven. Het pad naar de oplossing is dus door de mens beschreven. Dat is hier niet het geval.
Is het erg dat ik er nog nooit een heb kunnen oplossen? :o
Toch schijnt er een set bewegingen te zijn waarmee elke kubus ongeacht de beginstadium op te lossen is. Maximaal 26 stappen geloof ik.
Ik geloof dat ik je niet begrijp. Natuurlijk kun je iedere kubus oplossen. Al is het maar door alle stappen die zijn genomen om hem in die beginpositie te krijgen terug te lopen.

De set bewegingen die je nodig hebt kan beschreven worden als een combinatie van
links/rechts/voor/achter/boven/onder + 90/180/270 graden, waarbij er discussie is of 180 graden telt als twee keer 90 of 270.

Het maximum aantal bewegingen dat nodig is uit een willekeurige beginpositie is 20 (als 180 als 1 beweging telt) of 26 (als 180 telt als 2x 90 graden). Voor beide aantallen bestaat er ook een beginpositie die dit aantal minimaal nodig heeft, dus 20/26 is niet te verbeteren.

http://www.cube20.org/
Natuurlijk kun je iedere kubus oplossen.
Alle legale kubussen zijn op te lossen. Indien ik bv één hoeksteentje loshaal, een kwart slag draai en weer terug duw kan het niet meer opgelost worden. Heb ik bij mijn broer regelmatig gedaan, raakte hij heel gefrustreerd door :D
https://youtu.be/svvhWkUGLNw

Ik zag t hier, nog niet getest eerlijk gezegd.
Grappig. Belangrijk om op te merken is dat je met die serie van stappen door de oplossing geen gaat (je moet dus stoppen zodra de kubus is opgelost), en je er soms met die 25 nog niet bent, en dan moet je van begin af aan weer beginnen (en in een zeldzaam geval soms nog een derde keer).

Waar het feitelijk dus op neerkomt is dat je met deze herhaling van zetten door alle mogelijkheden heen gaat.

.edit: als ik dit lees is het onzin. Je gaat maar door max 864 verschillende states, bij lange na niet alle mogelijkheden van de kubus.

Ik heb het inmiddels ook geprobeerd, en hij lost mijn scramble niet op 8)7

[Reactie gewijzigd door .oisyn op 15 juni 2018 21:40]

Allicht moet je stoppen als de kubus klaar is :-) maar uit verschillende bronnen blijkt dat er een maximum van 26 (of iets meer of minder) bewegingen nodig zijn om elke kubus van 3x3x3 op te lossen.
Nee, het klopt gewoon niet. Het algoritme heeft een order van 36, met 24 moves is dat dus max 864 posities. Niet echt bepaald het maximum aantal posities dat een kubus kan hebben.

Maar klopt, elke kubus is op te lossen in 26 (quarter turn metric) of 20 (half turn metric) moves. Fun fact, er is maar 1 positie (en wat symmetrische varianten ervan) die daadwerkelijk 26 quarter turns nodig heeft, de four-spot superflip, dit kun je zien als de "omgekeerde" versie van een opgeloste kubus.

[Reactie gewijzigd door .oisyn op 16 juni 2018 00:12]

Vergeet niet dat het middelpunt altijd stilstaat en onveranderlijk is he...

Wil t nog wel eens proberen eigenlijk.
Het aantal mogelijke permutaties van Rubik's cube is ongeveer 4,3 * 1019 https://en.wikipedia.org/wiki/Rubik%27s_Cube#Permutations.
Hoewel het mogelijk is om vanuit iedere positie in slechts 26 bewegingen bij de oplossing te komen, kan dit nooit voor iedere positie dezelfde zijn. Het is heel eenvoudig te controleren: doe die zesentwintig bewegingen in tegengestelde richting vanuit de oplossing en je hebt één begin positie die je ermee oplost. Neem nu de eerste 25 bewegingen in tegengestelde richting vanuit de oplossing en je hebt er nog één. Herhaal dit 26 keer, dat zijn alle begin posities die je ermee oplost.
(Dit is de reden waarom ik wiskunde in mavo 4 heb laten vallen)
Compleet fake, dit werkt niet en kan niet werken. Pure clickbait van die gast.
Dat kan toch niet? Als je die set bewegingen in omgekeerde volgorde uitvoert vanuit de opgeloste positie, kom je altijd op hetzelfde patroon uit.
Het is niet dat je de oplossing krijgt na exact die hoeveelheid stappen, maar dat je na een willekeurig aantal stappen de oplossing bereikt (en als je dat nog niet hebt gedaan dan moet je de stappen herhalen)
20 = God's Number
https://www.youtube.com/watch?v=yF2J39Xny4Q

Mooie omgekeerde aanpak:
Om het minimale aantal draaiingen te vinden om elk van de 43 252 003 274 489 856 000 verschillende gehusselde posities op te kunnen lossen, bedenk je het aantal draaiingen om alle verschillende gehusselde posities te kunnen maken vanuit de opgeloste toestand.

[Reactie gewijzigd door GeeBee op 15 juni 2018 18:14]

heb je de handleiding geprobeerd? Zonder is bijna niet te doen (kan wel maar dan moet je voor alle moves het wiel opnieuw gaan uitvinden).
Ik kwam er idd ook niet uit zonder enige begeleiding 8)7. Ik heb toevallig 2 weken terug een speedcube gekocht (een Valk 3). Ik heb het beginnersalgoritme aardig onder de knie en kan 'm inmiddels wel oplossen binnen 3 minuten, met wat zelf uitgevonden shortcuts hier en daar door goed te bestuderen wat al die moves nou precies doen.

Mijn doel is binnen een minuut, maar ik heb alleen niet zo'n zin om al die OLL en PLL tabellen uit mijn hoofd te gaan zitten leren. ;)
Kijk eens naar de 2-look oll's en 2-look pll's...10 algoritmes voor oll ipv 57(?) en slechts 3 algoritmes voor pll.

Is iets langzamer maar dat is voor een niet-westrijd geen issue.
Ja die staan als volgende op mijn todo lijst :). Eerst mijn f2l nog perfectioneren, ik moet nog wat meer leren de corners en middle layer edges tegelijk te doen.
Misschien word je net als ik dan hier wel blij van.

https://www.kickstarter.c...classic-puzzle-reinvented
OMG wel een hoog Tweaker gehalte maar moet het serieus weer iets met een beeldscherm zijn om interessant te zijn? :P
Dat komt omdat je waarschijnlijk het algoritme niet bestudeerd hebt of zoals ik een te korte spanningsboog hebt voor dit soort dingen 8)7
Is het erg dat ik er nog nooit een heb vast gehad?
Schroevendraaier ertussen en 'm weer in elkaar zetten. Kwam wel steeds meer speling in.
Oh, nee hoor. Het is in principe een heel stom ding. Het is helemaal niet moeilijk om het op te lossen, je moet enkel met heel veel geduld leren hoe je bepaalde resultaten kan behalen (hoe beweeg ik x naar y), of gewoon op het internet opzoeken.
Interessant artikel, maar nu hoop ik toch dat we alles wel gehad hebben over de 3x3x3. De wereld zit nu te wachten op wat serieuze programma's om de 4x4x4, de 5x5x5 en nog hogere varianten op te lossen, want daar is een schrijnend tekort aan (een paar onontwarbare command-line tools niet meegerekend). Ik bedoel dus een programma met een gui zoals Cube Explorer, maar dan voor de varianten met meer dan 3 lagen. Echt bizar dat niemand zich daartoe geroepen schijnt te voelen.
Heeft te maken met de schaalbaarheid van het probleem. Met 3x3x3 het je al een heel groot aantal mogelijkheden en een oplostijd van ongeveer 10 minuten. 4x4x4 gaat je over het aligortime niets nieuws leren, alleen doordat het aantal mogelijke bewegingen enorm toeneemt, explodeert ook je oplossingstijd. Dat is niet direct gerelateerd aan het aantal mogelijk posities, was dat groeit maar iets meer dan een decade, maar met het aantal vrijheidsgraden waarmee het model rekening mag gaan houden.
Ik denk dat jij nochtans degene bent die zich er eerst even in moet verdiepen voordat je met dit soort claims komt 8)7. Het is juist geen brute force algoritme, maar een deep learning systeem dat de kubus "intuïtief" leert op te lossen zoals wij mensen dat doen.

Door te spelen met moves komt het erachter wat het precies doet, en hoe je dat vervolgens kunt gebruiken om stapje voor stapje dichter bij de oplossing te komen.

[Reactie gewijzigd door .oisyn op 15 juni 2018 21:06]

Mensen zonder goed getalsmatig bevattingsvermogen hebben wat moeite zich te realiseren dan een dataset met 1019 posities gevolgd door een serie van 20 draai-instructies helemaal geen efficiënte oplossing is, omdat je alleen al stuk zou gaan op je lookup.
Dit is echter geen gemakkelijk te lezen informatie, omdat er in de notatie al zoveel kennis verwerkt zit
Toch lijkt het niet helemaal zelfontdekte regels, om divergentie in het proces tegen te gaan is er een correctie toegevoegd om aan te geven hoe ver een sample van een oplossing afzat. Ik ben niet goed genoeg thuis in de gebruikte wiskunde om daar conclusies over het leerproces aan toe te kennen.
Weighted samples
During testing, we found that the learning algorithm sometimes either converged to a degenerate
solution or diverged completely. To counteract this, we assigned a higher training weight to samples
that are closer to the solved cube compared to samples that are further away from solution. We assign
a loss weight to each sample xi, W(xi) = 1
D(xi) . We didn’t see divergent behavior after this addition

Op dit item kan niet meer gereageerd worden.


Apple iPhone XS Red Dead Redemption 2 LG W7 Google Pixel 3 XL OnePlus 6T FIFA 19 Samsung Galaxy S10 Google Pixel 3

Tweakers vormt samen met Tweakers Elect, Hardware.Info, Autotrack, Nationale Vacaturebank en Intermediair de Persgroep Online Services B.V.
Alle rechten voorbehouden © 1998 - 2018 Hosting door True