211service.com
Een machine heeft Rubik's Cube helemaal zelf bedacht
Nog een ander bastion van menselijke vaardigheden en intelligentie is gevallen door de aanval van de machines. Een nieuw soort deep-learning machine heeft zichzelf geleerd om een Rubik's Cube op te lossen zonder menselijke hulp.
De mijlpaal is belangrijk omdat de nieuwe aanpak een belangrijk probleem in de informatica aanpakt: hoe complexe problemen op te lossen als de hulp minimaal is.
Eerst wat achtergrond. De Rubik's Cube is een driedimensionale puzzel ontwikkeld in 1974 door de Hongaarse uitvinder Erno Rubik, met als doel alle vierkanten van dezelfde kleur op dezelfde zijde van de kubus uit te lijnen. Het werd een internationaal bestverkocht speelgoed en er werden meer dan 350 miljoen stuks van verkocht.
De puzzel heeft ook veel belangstelling getrokken van computerwetenschappers en wiskundigen. Een vraag die hen heeft geïntrigeerd is: het kleinste aantal zetten dat nodig is om het vanuit elke positie op te lossen . Het antwoord, bewezen in 2014, blijkt 26 te zijn.
Een andere veelvoorkomende uitdaging is het ontwerpen van algoritmen die de kubus vanuit elke positie kunnen oplossen. Rubik zelf bedacht binnen een maand na het uitvinden van het speelgoed een algoritme dat dit kon.
Maar pogingen om het proces te automatiseren, zijn allemaal gebaseerd op algoritmen die met de hand zijn gemaakt door mensen.
Meer recentelijk hebben computerwetenschappers geprobeerd manieren te vinden waarop machines het probleem zelf kunnen oplossen. Een idee is om dezelfde soort aanpak te gebruiken die zo succesvol is geweest bij spellen als schaken en Go.
In deze scenario's krijgt een dieplerende machine de regels van het spel en speelt vervolgens tegen zichzelf. Cruciaal is dat het bij elke stap wordt beloond op basis van hoe het presteert. Dit beloningsproces is enorm belangrijk omdat het de machine helpt om goed spel van slecht spel te onderscheiden. Met andere woorden, het helpt de machine te leren.
Maar dit werkt niet in veel situaties in de echte wereld, omdat beloningen vaak zeldzaam of moeilijk te bepalen zijn.
Het willekeurig draaien van een Rubik's Cube kan bijvoorbeeld niet zomaar worden beloond, omdat het moeilijk te beoordelen is of de nieuwe configuratie dichter bij een oplossing komt. En een reeks willekeurige beurten kan lange tijd doorgaan zonder een oplossing te bereiken, dus de beloning in de eindtoestand kan slechts zelden worden aangeboden.
Bij schaken daarentegen is er een relatief grote zoekruimte, maar elke zet kan dienovereenkomstig worden geëvalueerd en beloond. Dat is gewoon niet het geval voor de Rubik's Cube.
Voer Stephen McAleer en collega's van de Universiteit van Californië, Irvine in. Deze jongens hebben een nieuw soort diepgaande leertechniek ontwikkeld, autodidactische iteratie genaamd, die zichzelf kan leren een Rubik's Cube op te lossen zonder menselijke hulp. De truc die McAleer en co onder de knie hebben, is om een manier te vinden waarop de machine zijn eigen beloningssysteem kan creëren.
Dit is hoe het werkt. Bij een onopgeloste kubus moet de machine beslissen of een bepaalde zet een verbetering is ten opzichte van de bestaande configuratie. Om dit te doen, moet het in staat zijn om de verhuizing te evalueren.
Autodidactische iteratie doet dit door te beginnen met de voltooide kubus en achteruit te werken om een configuratie te vinden die vergelijkbaar is met de voorgestelde zet. Dit proces is niet perfect, maar deep learning helpt het systeem erachter te komen welke bewegingen over het algemeen beter zijn dan andere.
Na getraind te zijn, gebruikt het netwerk vervolgens een standaard zoekboom om te zoeken naar voorgestelde zetten voor elke configuratie.
Het resultaat is een algoritme dat opmerkelijk goed presteert. Ons algoritme is in staat om 100% van willekeurig gecodeerde kubussen op te lossen en een mediane oploslengte van 30 zetten te bereiken - minder dan of gelijk aan oplossers die gebruik maken van menselijke domeinkennis, zeggen McAleer en co.
Dat is interessant omdat het implicaties heeft voor een aantal andere taken waarmee deep learning worstelde, waaronder puzzels zoals Sokoban, games zoals Montezuma's Revenge en problemen zoals ontbinden in priemgetallen.
McAleer en co hebben inderdaad andere doelen voor ogen: we werken aan het uitbreiden van deze methode om benaderende oplossingen te vinden voor andere combinatorische optimalisatieproblemen zoals de voorspelling van de tertiaire eiwitstructuur.
Of deze problemen net zo vatbaar zijn voor deze aanpak, is niet duidelijk. Ze profiteren over het algemeen niet van een bewijs dat ze in een klein aantal zetten kunnen worden opgelost, zoals het Rubik's Cube-probleem doet. Dat werkte hier ongetwijfeld in het voordeel van het team.
McAleer en co stellen dat hun aanpak een vorm van redeneren over problemen is. Ze wijzen erop dat een definitie van redeneren is: het algebraïsch manipuleren van eerder verworven kennis om een nieuwe vraag te beantwoorden.
Ze zeggen dat dit precies is wat hun algoritme, DeepCube genaamd, doet. Conventionele deep-learningmachines herkennen daarentegen gewoon bepaalde patronen. DeepCube kan zichzelf leren redeneren om een complexe omgeving met slechts één beloningstoestand op te lossen met behulp van pure versterkingsleer, zeggen ze.
Misschien. De echte test zal natuurlijk zijn hoe deze benadering omgaat met complexere problemen zoals eiwitvouwing. We zullen kijken om te zien hoe het werkt.
Referentie: arxiv.org/abs/1805.07470 : De Rubiks kubus oplossen zonder menselijke kennis