Исследователи обучили алгоритм CRAM решать сложные судоку всего за 42 миллисекунды. На проверке он справился с 99,996% головоломок, а при поиске решений потребовал как минимум в 282 раза меньше вычислений, чем современные циклические модели искусственного интеллекта.
Разработку представили Бенджамин Гувер, Хью Блейни и Джеймс Уиттингтон из британской компании Prefrontal. В опубликованном исследовании авторы сравнили CRAM с семью существующими моделями, предназначенными для решения логических задач. Новый метод обучался как минимум в 1000 раз быстрее конкурентов и показал более высокую точность на двух основных наборах испытаний.
Проверку проводили на Sudoku-Extreme и Maze-Unique. Первый набор содержит особенно сложные судоку размером 9 на 9 клеток, второй состоит из лабиринтов размером 30 на 30 клеток. CRAM правильно решила 99,996% из 412 786 проверочных судоку и все 1000 лабиринтов. Для обучения на видеокарте NVIDIA H200 потребовалось соответственно 42 и 132 миллисекунды. Указанное время относится именно к обучению модели, а не к решению отдельной головоломки.
Секрет эффективности заключается в способе поиска ответа. Современные циклические модели многократно пропускают информацию через одни и те же вычислительные блоки, постепенно уточняя результат. CRAM использует математическую функцию, которая присваивает каждому возможному решению условную стоимость, называемую энергией. Правильные комбинации должны иметь низкую стоимость, а нарушающие правила головоломки получают штраф.
Во время обучения система изучает готовые решения и запоминает, какие сочетания допустимы. Затем CRAM получает новую головоломку, сохраняет исходные подсказки и начинает менять значения в незаполненных клетках, стараясь уменьшить общую стоимость. Для судоку алгоритм запускает четыре независимых поиска со случайными начальными комбинациями. Как только один из них достигает установленного порога, вычисления прекращаются.
Такой подход позволяет расходовать вычислительные ресурсы в зависимости от сложности задания. На простых судоку CRAM останавливается сравнительно быстро, а на трудных продолжает поиск. Между самыми лёгкими и наиболее сложными группами головоломок медианное количество вычислений различалось в 22 раза. При этом во время испытаний система ни разу не остановилась на неправильном решении, хотя иногда исчерпывала допустимое число попыток.
Особенно заметной оказалась разница с моделью Energy-Based Reasoners (EBR). При одинаковой точности 99,86% на выборке из 10 000 судоку CRAM выполняла в среднем 1,9 миллиарда арифметических операций против 540 миллиардов у EBR. Разница составила 282 раза. В сравнении с некоторыми другими архитектурами преимущество достигало 128 000 раз. Однако количество операций нельзя напрямую приравнивать к скорости работы или расходу электроэнергии на конкретном оборудовании.
Ещё одно преимущество связано с объёмом обучающих данных. Для достижения точности 98% на судоку CRAM хватило 30 различных головоломок, тогда как EBR потребовалось около 700. Исследователи также обнаружили, что модель самостоятельно восстановила основные правила судоку. Хотя расположение строк, столбцов и квадратов ей заранее не объясняли, после обучения алгоритм начал штрафовать одинаковые цифры именно в тех 810 парах клеток, где повторения запрещены.
Основой CRAM стала идея, предложенная Джоном Хопфилдом и Дэвидом Танком ещё в 1980-х годах. В классических сетях Хопфилда информация хранится в виде устойчивых состояний, к которым система стремится при обработке неполных данных. Авторы CRAM переработали старый подход, позволив алгоритму самостоятельно изучать необходимые связи вместо ручного задания всех правил.
При этом разработчики не ограничились судоку и лабиринтами. CRAM проверили на задаче расстановки ферзей на шахматной доске и раскраске графов, где связанные вершины должны получать разные цвета. Алгоритм показал результаты, сопоставимые с лучшими циклическими моделями, при значительно меньших затратах на обучение. Для расстановки ферзей обучение занимало несколько секунд вместо часов, а для небольших графов укладывалось в доли секунды или секунды.
Однако сравнение имеет существенные ограничения. Замеры обучения CRAM проводились после первоначальной загрузки и подготовки вычислительной среды, тогда как конкурирующие модели запускались с нуля. Авторы раскрыли разницу в методике измерений. Кроме того, при ручном задании правил CRAM решала все проверочные задачи и иногда требовала ещё меньше операций, чем обученная версия. Следовательно, высокая точность на подобных испытаниях сама по себе не доказывает способность модели к сложным рассуждениям.
Исследователи прямо предупреждают, что судоку, лабиринты и другие использованные задачи допускают компактное математическое описание. Полученные результаты нельзя автоматически переносить на программирование, математические доказательства или задачи, где алгоритму приходится самостоятельно открывать новые закономерности. Тем не менее эксперимент показывает, что для некоторых классов логических задач сложные нейросетевые архитектуры могут быть избыточными, а методы сорокалетней давности после доработки способны работать значительно экономнее.