Нова система штучного інтелекту DeepCube самостійно за 44 години навчилася збирати кубик Рубіка. Тепер програма вирішує головоломку не гірше за системи, що спираються на знання людини, повідомляє Gizmodo.
Оновлено: у липні 2019 року стаття опублікована в.
Незважаючи на те, що кубик Рубіка був винайдений ще в 1974 році, головоломка досі користується великою популярністю. Регулярно проводяться змагання, в яких люди і роботи збирають кубик на швидкість. Вважається, що з цим завданням можна впоратися не більше ніж за 20 ходів - це нижня межа алгоритму Бога, який дозволяє отримати оптимальне рішення головоломки, починаючи з будь-якої конфігурації (при поворотах на 180 градусів).
Програмісти під керівництвом Стівена Макаліра (Stephen McAleer) створили систему штучного інтелекту, яка здатна зібрати кубик Рубіка в середньому за 30 ходів. Приблизно стільки ж рухів використовують люди, які професійно займаються спідкубінгом. В основі програми лежить глибоке навчання з підкріпленням - його суть полягає в тому, що керований алгоритмом агент знаходиться в середовищі і, виконуючи різні дії, може отримувати за них нагороду. Таким чином, методом проб і помилок він вчиться виконувати послідовність дій, що призводить до найбільшої нагороди і тим самим поступово наближається до потрібного творцям результату.
Коли DeepCube робить хід, система автоматично прораховує, до якого результату він призведе. Вона фактично «стрибає» до того стану, коли головоломка вирішена, а потім повертається назад до запропонованого руху. Це дозволяє програмі визначити середню довжину рішення, а також «силу» ходу. Після того, як алгоритм збирає необхідну кількість даних, він знаходить оптимальний набір дій, використовуючи метод дерева рішень - тобто перевіряючи кожен можливий рух, щоб визначити, який з них є найкращим. Все це відбувається без втручання людини.
У процесі навчання DeepCube за 44 години вирішила близько мільйонів кубиків Рубіка (включаючи повтори). Алгоритм використовував 32-ядерний сервер Intel Xeon E5-2620 з трьома відеокартами NVIDIA Titan XP. Система, як пишуть автори, отримала достатню кількість знань під час тренування: наприклад, вона самостійно знайшла стратегію, яку використовують просунуті спідкубери - зіставлення сторін і кутів головоломки перед тим, як їх перемістити в потрібну позицію. «Наш алгоритм здатний вирішити 100 кубиків з випадковою конфігурацією, досягнувши медіани в 30 кроків - це менший або майже такий же результат, як у алгоритмів, що використовують людські знання», - коментує Макалір.
Деякі конфігурації кубика Рубіка викликали труднощі у алгоритму, тому в майбутньому розробники сподіваються поліпшити його роботу. Крім того, зараз DeepCube використовувався для того, щоб вирішити головоломку 3 ст.13 ст.13, однак він може бути також навчений і для кубика 4 ст.14 ст.14.
Сьогоднішній рекорд зі швидкісної збірки кубика Рубіка належить австралійцю Феліксу Земдегсу, який у травні 2018 року зібрав головоломку за 4,22 секунди. Серед машин неофіційним чемпіоном вважається робот Бена Каца і Джареда Ді Карло, який здатний зібрати кубик Рубіка за 0,38 секунди.