Com fer perquè una màquina resolgui el cub de Rubik?
David Grossman va comentar que els científics de Califòrnia van treballant en tres dimensions amb un algoritme que pot esbrinar com resoldre un cub de Rubik. Aquest equip està al darrere d'un enfocament que va cridar l'atenció.
La solució del cub de Rubik sense coneixement humà és el títol del seu treball, que descriu la seva exploració.
Es presenta la iteració autodidàctica: un algoritme d'aprenentatge nou capaç d'ensenyar com resoldre el Cub de Rubik sense assistència humana. Les màquines normalment utilitzen un mètode d'autoaprenentatge basat en un sistema de recompenses. Els investigadors alimenten la màquina de les regles del joc i, a continuació, utilitzen un procés de recompenses per determinar si era bona o dolenta, tanmateix, per a molts entorns d'optimització combinatòria, les recompenses són escasses i els episodis no es garanteix que finalitzin.
Per resoldre el cub de Rubik utilitzant l'aprenentatge, cal que l'algoritme aprengui una política. La política determina quins passos adoptar en un estat determinat.
Donat un cub sense resoldre, la màquina ha de decidir si un moviment específic és una millora de la configuració existent. Per fer-ho, ha de poder avaluar el moviment. La iteració automàtica comença amb el cub acabat i treballa cap enrere per trobar una configuració similar a la proposta de moviment.
DeepCube va aprendre una quantitat notable de coneixement del cub de Rubik durant el seu procés de formació, incloent el coneixement de com utilitzar grups de permuta complexos i estratègies similars als millors cubs resolts per humans.
La seva màquina d'entrenament era un servidor Intel Xeon E5-2620 de 32 nuclis amb tres GPU NVIDIA Titan XP. To i que no és una solució perfecta per fer front al problema, és impecable en termes d'exactitud. L'algoritme és capaç de resoldre el 100% dels cubs remenats aleatòriament i aconseguir una mitjana de resolucions de 30 moviments.
A més de treballar amb el cub de Rubik, s'està treballant per estendre aquest mètode per trobar solucions aproximades a altres problemes d'optimització combinatòria, com ara la predicció de l'estructura terciària de proteïnes. Molts problemes d'optimització de combinatòria es poden considerar problemes de decisió seqüencials, en aquest cas podem utilitzar l'aprenentatge aplicat en el DeepCube. Aquest nou enfocament aborda un problema important en la informàtica, com resoldre problemes complexos quan l'ajuda és mínima.
Font: arXiv
