Судоку, спросим у интернета и нейросетей.
Для интереса спросил у нейросети (естественно по английски): "Решить судоку используя ...".
Спрашивал у deepseek-coder-v2:16b Это GPT4-Turbo которую типа научили программировать. Хотя если честно мне она больше напоминает "экспертную систему", которая запомнила интернет по данному вопросу.
Если спросить "Решить судоку используя С++", то она выдаёт вполне корректное решение начального уровня, которое будет работать. Причём вполне корректно преобразует программу, если попросить "Вместо std::vector> data используй int8_t data[9][9]"
На более сложных кейсах уже начинает лажать. Если дополнительно попросить "Напиши функцию isValid на SSE", то она пишет мусорный, нерабочий код на SSE. Функция isValid это функция, которая проверяет, что цифры по полю расставлены корректно, по правилам судоку. В базовом рекурсивном решателе судоку она 99% времени выполнения занимает. Если попростить "Напиши функцию isValid на NEON", то нейросетка выдаёт программу, в которой функция isValid пустая. И перед этой функцией комментарий "Писать на NEON очень сложно, но вот вам пример программы, впишите функцию на NEON в это место."
Дальше спросил "Решить судоку используя pytorch". Т.е. по умолчанию предполагаем, что она напишет нейросетку, которая как-то обучится и сможет судоку решать. Естественно пытался и другие запросы ей задать, типа "Класс нейросети nn.Module для pytorch решающий судоку". Результаты были похожие. Опишу пожалуй результат с кодом. Весь код приводить не буду, там более 100 строк и на экран не влазит.
Прежде всего - что на C++, что на python всегда как пример одно и то-же судоку:
хотя если попросить "другое судоку", то она таки выдаёт другой пример.
А вот при помощи какой нейросетки оно предлагает это решать.
Тут есть фактическая ошибка. Вместо 64*2*2 должно быть 64*5*5. Но не суть. Нейросеть подобной конфигурации просто физически не способна обучиться решению судоку. Слишком простая конфигурация. Максимум, на что она способна - научиться предсказывать одну цифирку следующую, на уровне новичка. Такие нейросети писали на заре интереса к нейросетям, лет эдак 15 назад.
Что-ж на этом перестал мучать нейросетку, и спросил тот-же вопрос у интернета. У нас жеж есть "всемирные кладези знаний" в лице stackoverflow и github. Stackoverflow он больше по коротеньким вопросам, поэтому остаётся github.
Первым делом наткнулся на репозиторий sampan-s-nayak в котором нейросетка уж больно похожая по конфигурации на то, что выдаёт deepseek-coder. Впринципе оно и понятно "хорошая копипаста борозды не испортит". Если бы нейросетки ещё и выдавали ссылки, откуда они скописастили свой код - от них было-бы сильно больше проку. Понятно, что такая нейросетка может решить судоку только простейшие и только при многократном её применении к судоку.
Другой репозиторий, на который наткнулая, это sudoku-solver.pytorch Этот код даже написан по какой-то статейке из stanford.edu. Впрочем как и статейка так и код низкокачественные. Суть такая - а давайте возьмём много-много примеров и большую-большую нейросеть и применим стандартные подходы. Нейросетка огромная. torch summary для неё пишет "Total mult-adds (G): 2.78". Я этот кода таки запустил. 3 часа училось. В результате оно умеет решать 92% ужасно простых судоку со скоростью 7.6 судоку в секунду.
Для сравнения. Такие судоку черезвычайно простые, и для них достаточно 4-х итераций моего решателя судоку. Он их решает со скоростью 11405313 судоку в секунду. 11 милллионов за секунду! Причем решает безошибочно, на 100%. Т.е. разница в скорости в миллион раз.
Сделаю выводы из вышесказанного.
Сами по себе нейросетки имеют смысл только на современном железе, которое терафлопы в секунду перемалывать умеет. И конфигурация сети очень важна (так-же как и процесс обучения). Если отключить мозг и пользоваться стандартными способами решения, но ничего путного не выйдет.
Ещё интересный момент - за последние десяток лет произошёл просто огромный скачок в развитии нейросетей. Дальше идут уже мои спекуляции, тестирования ещё не проводил. Если использовать стандартную darknet в качестве базового кирпичика, то можно сделать на порядок более быструю нейросеть, чем если пользоваться стандартными подходами.
Очень важно представление данных. Т.е. если вхоные выходные данные будут в виде матрицы 9x9x9, где в каждой из ячеек может быть либо 0 либо 1. Например единичка по индексу [1,3,7] будет означать, что число 2 (потому как 1 преобразуется в 0) в строчке 3 в колонке 7 может находиться в этой ячейке. Так можно будет сделать значительно более подробную loss function. Такую, что-бы она могла замечать даже незначительные успехи нейросети. Это и процесс обучения улучшит и нейросети будет в сложных случаях проще догадаться, что она идёт в верном направлении.
И самое интересное - в нейросетях есть огромное поле для оптимизации. Как в процессе обучения, так и в процессе конфигурации нейросети.
Спрашивал у deepseek-coder-v2:16b Это GPT4-Turbo которую типа научили программировать. Хотя если честно мне она больше напоминает "экспертную систему", которая запомнила интернет по данному вопросу.
Если спросить "Решить судоку используя С++", то она выдаёт вполне корректное решение начального уровня, которое будет работать. Причём вполне корректно преобразует программу, если попросить "Вместо std::vector> data используй int8_t data[9][9]"
На более сложных кейсах уже начинает лажать. Если дополнительно попросить "Напиши функцию isValid на SSE", то она пишет мусорный, нерабочий код на SSE. Функция isValid это функция, которая проверяет, что цифры по полю расставлены корректно, по правилам судоку. В базовом рекурсивном решателе судоку она 99% времени выполнения занимает. Если попростить "Напиши функцию isValid на NEON", то нейросетка выдаёт программу, в которой функция isValid пустая. И перед этой функцией комментарий "Писать на NEON очень сложно, но вот вам пример программы, впишите функцию на NEON в это место."
Дальше спросил "Решить судоку используя pytorch". Т.е. по умолчанию предполагаем, что она напишет нейросетку, которая как-то обучится и сможет судоку решать. Естественно пытался и другие запросы ей задать, типа "Класс нейросети nn.Module для pytorch решающий судоку". Результаты были похожие. Опишу пожалуй результат с кодом. Весь код приводить не буду, там более 100 строк и на экран не влазит.
Прежде всего - что на C++, что на python всегда как пример одно и то-же судоку:
хотя если попросить "другое судоку", то она таки выдаёт другой пример.
А вот при помощи какой нейросетки оно предлагает это решать.
Тут есть фактическая ошибка. Вместо 64*2*2 должно быть 64*5*5. Но не суть. Нейросеть подобной конфигурации просто физически не способна обучиться решению судоку. Слишком простая конфигурация. Максимум, на что она способна - научиться предсказывать одну цифирку следующую, на уровне новичка. Такие нейросети писали на заре интереса к нейросетям, лет эдак 15 назад.
Что-ж на этом перестал мучать нейросетку, и спросил тот-же вопрос у интернета. У нас жеж есть "всемирные кладези знаний" в лице stackoverflow и github. Stackoverflow он больше по коротеньким вопросам, поэтому остаётся github.
Первым делом наткнулся на репозиторий sampan-s-nayak в котором нейросетка уж больно похожая по конфигурации на то, что выдаёт deepseek-coder. Впринципе оно и понятно "хорошая копипаста борозды не испортит". Если бы нейросетки ещё и выдавали ссылки, откуда они скописастили свой код - от них было-бы сильно больше проку. Понятно, что такая нейросетка может решить судоку только простейшие и только при многократном её применении к судоку.
Другой репозиторий, на который наткнулая, это sudoku-solver.pytorch Этот код даже написан по какой-то статейке из stanford.edu. Впрочем как и статейка так и код низкокачественные. Суть такая - а давайте возьмём много-много примеров и большую-большую нейросеть и применим стандартные подходы. Нейросетка огромная. torch summary для неё пишет "Total mult-adds (G): 2.78". Я этот кода таки запустил. 3 часа училось. В результате оно умеет решать 92% ужасно простых судоку со скоростью 7.6 судоку в секунду.
Для сравнения. Такие судоку черезвычайно простые, и для них достаточно 4-х итераций моего решателя судоку. Он их решает со скоростью 11405313 судоку в секунду. 11 милллионов за секунду! Причем решает безошибочно, на 100%. Т.е. разница в скорости в миллион раз.
Сделаю выводы из вышесказанного.
Сами по себе нейросетки имеют смысл только на современном железе, которое терафлопы в секунду перемалывать умеет. И конфигурация сети очень важна (так-же как и процесс обучения). Если отключить мозг и пользоваться стандартными способами решения, но ничего путного не выйдет.
Ещё интересный момент - за последние десяток лет произошёл просто огромный скачок в развитии нейросетей. Дальше идут уже мои спекуляции, тестирования ещё не проводил. Если использовать стандартную darknet в качестве базового кирпичика, то можно сделать на порядок более быструю нейросеть, чем если пользоваться стандартными подходами.
Очень важно представление данных. Т.е. если вхоные выходные данные будут в виде матрицы 9x9x9, где в каждой из ячеек может быть либо 0 либо 1. Например единичка по индексу [1,3,7] будет означать, что число 2 (потому как 1 преобразуется в 0) в строчке 3 в колонке 7 может находиться в этой ячейке. Так можно будет сделать значительно более подробную loss function. Такую, что-бы она могла замечать даже незначительные успехи нейросети. Это и процесс обучения улучшит и нейросети будет в сложных случаях проще догадаться, что она идёт в верном направлении.
И самое интересное - в нейросетях есть огромное поле для оптимизации. Как в процессе обучения, так и в процессе конфигурации нейросети.