ИИ сам научился собирать кубик Рубика



    Компьютерные программы уже давно умеют играть в шахматы, относительно недавно специализированную платформу от Deep Mind даже обучили профессионально играть в го. Настолько профессионально, что игроков среди людей, равных компьютеру, сейчас нет, и скорее всего, не будет.

    На днях стало известно, что машина самостоятельно научилась решать еще одну сложную головоломку — кубик Рубика. Причем при обучении ей не демонстрировали, как правильно собирать кубик, программная платформа, созданная учеными из США, всему научилась самостоятельно. Некоторые специалисты считают, что перед машинами пал еще один «бастион, считавшийся владением человека».

    Кубик Рубика, вернее, алгоритм его сборки, сложен тем, что каждое действие при сборке несет определенные последствия, но предугадать их влияние на общий процесс сборки достаточно сложно. Даже для машины. Люди обычно учатся собирать кубик по ранее разработанным алгоритмам, позволяющим решить головоломку в кратчайшие сроки.

    Некоторые из обучившихся делают просто удивительные успехи на этом поприще. Так, в мае этого года был установлен очередной рекорд по сборке кубика Рубика двумя руками. Чемпион, 22-летний австралиец по имени Феликс Земдегс, смог собрать кубик всего за 4,22 секунды. Он начал тренироваться с 12 лет, просмотрев записи сборки на YouTube.


    Что касается машины, то роботы собирают кубик еще быстрее. В этом году рекорд был поставлен за 0,38 секунды. Можно было бы и быстрее, но может не выдержать механика самого кубика. В попытках поставить рекорд разработчикам пришлось усиливать конструкцию кубика, иначе он просто разваливался от слишком быстрых манипуляций машины.


    В случае платформы, о которой идет речь выше, работа ведется по заранее введенным в память системы алгоритмам. Но ученые из МИТ смогли обучить собственную систему собирать Кубик самостоятельно.



    При создании самого кубика его изобретателем наиболее интересной задачей была разработка способа решить головоломку из любого положения. Инженеру Рубику удалось это сделать за месяц. В дальнейшем алгоритм сборки неоднократно совершенствовался.

    С недавних пор специалисты по ИИ начали искать способ научить машину складывать кубик. В ход шло глубокое машинное обучение. Системе давали задачу и объясняли правила. Далее робот должен был действовать уже самостоятельно. В случае прогресса машина получала награду — примерно так и обучают слабые формы ИИ. Ведь компьютер должен знать, что движется в правильном направлении. И ему дают это понять благодаря системе наград. Все это помогает машине обучаться.

    В случае с кубиком Рубика это несколько сложнее, чем в обычном случае. Дело в том, что до определенного момента нельзя понять, правильно или нет действует система. А награждать за случайный поворот грани, не приносящий результата, смысла нет. В шахматах все проще — там уже со второго-третьего хода можно понять, в каком направлении движется партия и хорошо или нет действует машина. Соответственно, есть за что награждать.

    Для того, чтобы научить компьютер складывать кубик Рубика, была использована специализированная технология глубокого обучения, которая получила название «автодидактическая итерация». Эта технология позволяет «раскручивать» уже собранный кубик, чтобы добиться конфигурации, которая похожа на текущую. Получается нечто вроде реверс-инжиниринга, если этот термин применим к обучению машин. Создается специализированное «дерево решений», которое машина использует для вычисления шагов к каждой конфигурации.

    Результат получился впечатляющим. По словам самих разработчиков, алгоритм может решить головоломку примерно в 30 ходов. Причем машина собирает кубик в 100% случаев, какой бы вариант разобранной головоломки ей бы ни попался. В целом, для того, чтобы собрать хорошо фрагментированную головоломку, необходимо от 19 до 23 шагов. Некоторые решения приводят к желаемому результату быстрее, чем прочие. Наиболее быстрый алгоритм сборки состоит из 21 шага.

    Платформа, разработанная инженерами МИТ, получила название DeepCube. «Наша платформа в состоянии самообучаться в условиях сложного окружения, получая всего одну награду за весь процесс работы», — говорится в отчете специалистов.

    Сейчас эта же команда ученых работает над реализацией своего метода обучения к решению других сложных комбинаторных задач. В числе прочих — предсказание третичной структуры белка.
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 21
    • 0
      В целом, для того, чтобы собрать хорошо фрагментированную головоломку, необходимо от 19 до 23 шагов.

      Какие-то устаревшие данные. Число бога ведь уже точно установлено равным 20. А в остальном трудно, конечно, считать это каким-то выдающимся достижением, после го и шахмат. Для кубика Рубика настоящим вызовом для ИИ было бы научится решать все варианты алгоритмом бога.
      • –1

        Может быть такого алгоритма нет, и необходимо только знать все решения — кратчайшие пути сборки, чтобы получить собранный кубик именно кратчайшими путями.

        • –1
          Это конечная задача, так что такой алгоритм гарантированно есть. И даже «число бога» давно известно.
          • +5
            давно известно

            Ещё с 1980-х годов:


            В N-ском университете разработано практическое доказательство того, что кубик Рубика может быть приведен в исходное состояние не более чем за 6 ходов. При доказательстве использовались широкая кисть и набор из 6 красок.
    • 0

      (del)

      • +1
        Не понятно. А если этой платформе дать 4ех, 5ти, 6ти размерные кубики?

        Собрать любой из них очень просто (человеку сложно только удержать внимание), когда понимаешь что если крутить ЛЮБУЮ не случайную циклическую трансформацию достаточно долго то она переходит саму в себя. И это надо использовать для поиска нужных трансформаций «частично меняющих комбинацию» (не получилось — крути дальше — что означает — вернешься назад — начинай сначала). И на самом деле, даже, унивресальная трансформация «быстро» находится таким способом (меняющая три кубика местами — когда все остальные остаются на месте). И потом этой универсальной можно складывать кубики. А можно искать «узкозаточенные» приемчики.

        Т.е. решением задачи должно считаться когда одна и таже обученная нейронка сможет складывать кубик-рубик любой размерности без переобучения. Видимо тогда за ней придется признать понимание «топологии кубика» на уровне человеческих (моих по крайней мере) представлений.
        • +1
          Причем машина собирает кубик в 100% случаев, какой бы вариант разобранной головоломки ей бы ни попался.

          Вы не поверите, но человек тоже собирает кубик в 100% случаев, какой бы скрамбл не был, за исключением механической разборки и неправильной сборки.
          • +1
            Я ни разу не собрал. Специально не изучал алгоритм, хотелось все самому — не судьба…
            • 0
              Речь не о частном случае, а о том, что из любого скрамбла КР имеет решения, не являющиеся реверсом скрамбла. )

              Способы, которыми решает головоломку человек, совершенно не зависят от «варианта разобраной головоломки».
          • 0
            > Кубик Рубика, вернее, алгоритм его сборки, сложен тем, что каждое действие при сборке несет определенные последствия, но предугадать их влияние на общий процесс сборки достаточно сложно.

            Нет, это не так. Всё не так плохо, иначе не было бы 4.22 сек.

            > Люди обычно учатся собирать кубик по ранее разработанным алгоритмам

            Если брать два основных «послойных» способа сборки — «новичковый» и CFOP — первые два слоя собираются интуитивно, без всяких алгоритмов. Третий слой, да, для скорости заучивают до механической памяти комбинации для всех возможных случаев (около 80 формул), а на самом деле чтобы собрать третий слой КР достаточно «рыбки», «лямбды», «треугольника» сторон и «креста» сторон, т.е. 4 формулы.
            • 0

              А ещё есть чисто интуитивно методы, где все необходимые алгоритмы сводятся к элементарных трехходовкам. Например, метод В.Морозова, где сначала ориентируются углы, а потом собираются ребра.

              • 0
                А ещё есть чисто интуитивно методы

                О чем и речь, в статье что-то перебор с неточными заявлениями.
            • 0
              Если правильно понял для того что бы её обучить ей после каждого шага сообщают до правильного решения осталось N шагов? Ну имхо это не очень похоже на «сам научился».
              • 0
                Да, это читерство какое-то. Честнее была бы наивная «человеческая оценка» — чем больше граней на своих местах, тем лучше. Может их нейросеть не умеет справляться с локальными максимумами? ;)
              • 0
                Австралиец крут… Мой рекорд 35 секунд, но тупо по алгоритмам. А австралиец видимо просчитал сразу все ходы.
                • 0
                  была использована специализированная технология глубокого обучения, которая получила название «автодидактическая итерация». Эта технология позволяет «раскручивать» уже собранный кубик, чтобы добиться конфигурации, которая похожа на текущую. Получается нечто вроде реверс-инжиниринга, если этот термин применим к обучению машин. Создается специализированное «дерево решений», которое машина использует для вычисления шагов к каждой конфигурации.

                  Хм. То есть дали дерево развертки кубика, комп нашел в нем текущий лист и прошел до корня? И это нынче называется машинным обучением?

                  • 0
                    Тоже смутил этот момент. Если есть «коробка» которая в каждый момент времени говорит на сколько текущий шаг приближает к успеху, то уже не так всё интересно.
                  • 0
                    del

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое