De kubus van Rubik oplossen met leren en zoeken naar diepe versterking

De kubus van Rubik oplossen met leren en zoeken naar diepe versterking
Forest Agostinelli, Stephen McAleer, Alexander Shmakov en Pierre Baldi
Nature Machine Intelligence deel 1, pagina’s356-363 (2019) Citeer dit artikel

Abstract
De Rubiks kubus is een prototypische combinatorische puzzel met een grote toestandsruimte met een enkele doeltoestand. Het is onwaarschijnlijk dat toegang tot de doelstatus wordt verkregen met behulp van reeksen willekeurig gegenereerde bewegingen, wat unieke uitdagingen voor machine learning oplevert. We lossen de Rubik’s kubus op met DeepCubeA, een leerbenadering van diepe bekrachtiging die leert hoe we steeds moeilijkere toestanden kunnen oplossen in omgekeerde volgorde van de doeltoestand zonder enige specifieke domeinkennis. DeepCubeA lost 100% van alle testconfiguraties op en vindt 60,3% van de tijd een kortste pad naar de doeltoestand. DeepCubeA genereert generaties naar andere combinatorische puzzels en is in staat om de 15 puzzels, 24 puzzels, 35 puzzels, 48 ​​puzzels, Lights Out en Sokoban op te lossen en in de meeste verifieerbare gevallen een kortste pad te vinden.

Hoofd
De Rubiks kubus is een klassieke combinatorische puzzel die unieke en interessante uitdagingen biedt voor kunstmatige intelligentie en machine learning. Hoewel de toestandsruimte uitzonderlijk groot is (4,3 × 1019 verschillende toestanden), is er slechts één doeltoestand. Bovendien is de Rubiks kubus een spel voor één speler en het is onwaarschijnlijk dat een reeks willekeurige zetten, ongeacht hoe lang, zal eindigen in de doeltoestand. Het ontwikkelen van algoritmen voor machine learning om met deze eigenschap van de Rubiks kubus om te gaan, zou inzicht kunnen bieden in het leren oplossen van planningsproblemen met grote staatsruimten. Hoewel methoden voor machine learning eerder zijn toegepast op de kubus van Rubik, hebben deze methoden de kubus niet betrouwbaar opgelost1,2,3,4 of waren ze afhankelijk van specifieke domeinkennis5,6. Buiten de machine learning-methoden zijn methoden gebaseerd op patroondatabases (PDB’s) effectief geweest bij het oplossen van puzzels zoals de Rubiks kubus, de 15 puzzel en de 24 puzzel7,8, maar deze methoden kunnen geheugenintensief en puzzelspecifiek zijn.

Meer in het algemeen is een belangrijk doel van kunstmatige intelligentie het creëren van algoritmen die in staat zijn om te leren omgaan met verschillende omgevingen zonder te vertrouwen op domeinspecifieke menselijke kennis. De klassieke 3 × 3 × 3 Rubiks kubus is slechts één vertegenwoordiger van een grotere familie van mogelijke omgevingen die in grote lijnen de hierboven beschreven kenmerken delen, inclusief (1) kubussen met langere randen of hogere afmetingen (bijvoorbeeld 4 × 4 × 4 of 2 × 2 × 2 × 2), (2) schuifpuzzelpuzzels (bijvoorbeeld de 15 puzzel, 24 puzzel, 35 puzzel en 48 puzzel), (3) Lights Out en (4) Sokoban. Naarmate de omvang en afmetingen toenemen, neemt de complexiteit van de onderliggende combinatorische problemen snel toe. Bijvoorbeeld, terwijl het vinden van een optimale oplossing voor de puzzel van 15 op een moderne desktop minder dan een seconde duurt, kan het vinden van een optimale oplossing voor de puzzel van 24 dagen duren, en het vinden van een optimale oplossing voor de puzzel van 35 is over het algemeen onhandelbaar9. De bovengenoemde puzzels zijn niet alleen relevant als wiskundige spellen, maar ze kunnen ook worden gebruikt om planningsalgoritmen10 te testen en om te beoordelen hoe goed een machine learning-benadering kan generaliseren naar verschillende omgevingen. Bovendien, omdat de werking van de Rubiks kubus en andere combinatorische puzzels diep geworteld zijn in de groepentheorie, roepen deze puzzels ook bredere vragen op over de toepassing van machine learning-methoden op complexe symbolische systemen, waaronder wiskunde. Kortom, om al deze redenen vormt de Rubiks kubus interessante uitdagingen voor machine learning.

Om deze uitdagingen het hoofd te bieden, hebben we DeepCubeA ontwikkeld, dat diep leren11,12 combineert met klassiek leren van bekrachtiging13 (geschatte waarde-iteratie14,15,16) en methoden voor het vinden van paden (gewogen A * zoeken17,18). DeepCubeA kan combinatorische puzzels oplossen, zoals de Rubiks kubus, 15 puzzel, 24 puzzel, 35 puzzel, 48 puzzel, Lights Out en Sokoban (Fig. 1). DeepCubeA werkt met behulp van geschatte waarde-iteratie om een ​​diep neuraal netwerk (DNN) te trainen om een ​​functie te benaderen die de kosten oplevert om het doel te bereiken (ook bekend als de cost-to-go-functie). Aangezien het onwaarschijnlijk is dat willekeurig spelen eindigt in de doeltoestand, traint DeepCubeA op toestanden die worden verkregen door te beginnen vanuit de doeltoestand en willekeurig zetten in omgekeerde richting te nemen. Na de training wordt de aangeleerde cost-to-go-functie gebruikt als een heuristiek om de puzzels op te lossen met behulp van een gewogen A * -zoekopdracht17,18,19.

rubiks kubus