Een diepgaand leeralgoritme dat de Rubik’s Cube en andere combinatorische puzzels kan oplossen, wordt deze week gepubliceerd in Nature Machine Intelligence. Het oplossen van puzzels met een groot aantal combinaties kan inzicht geven in hoe wetenschappelijke problemen worden opgelost, zoals het vouwen van eiwitten.

Het vinden van de kortste oplossing voor een combinatorische puzzel is moeilijk. Oplossingen voor dergelijke puzzels kunnen over het algemeen niet worden gevonden door willekeurige bewegingen te maken. Traditionele algoritmen kunnen combinatorische puzzels oplossen, maar hun reken- en geheugenvereisten maken ze onpraktisch voor grote puzzels.

Pierre Baldi en collega’s hebben DeepCubeA ontwikkeld vanuit hun eerdere project DeepCube. DeepCubeA vertrekt vanuit de staat van het doel en werkt achteruit met een combinatie van versterkingsleren en methoden voor het zoeken naar paden om de puzzels op te lossen. DeepCubeA kan in de meeste gevallen het kortste pad voor puzzels identificeren en kan dit doen met minder geheugen dan traditionele algoritmen. De auteurs laten zien dat het de Rubik’s Cube, Lights Out, Sokoban en grotere problemen kan oplossen, inclusief een schuifpuzzel met 48 tegels.

De auteurs suggereren dat het brede scala aan games dat met dezelfde aanpak is opgelost, betekent dat het bij grotere problemen kan worden gebruikt om bijna optimale oplossingen te vinden.

rubiks kubus