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

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

В проекте судоку три стратегии устранения использованных решений были следующими:

  • прямое исключение — найти поля, которые решены, а затем удалить значение этого поля из его сверстников (строк, столбцов, квадратов)
  • единственный выбор - учитывая поле с несколькими возможными цифрами, для каждой из этих цифр посмотрите, отсутствует ли оно в других единицах этого поля, что делает это число единственным жизнеспособным выбором для ящика.
  • Голые близнецы — иногда у вас есть единицы, у которых есть два квадрата с одинаковыми возможными решениями, а это означает, что эти два квадрата будут иметь одну из этих цифр. Таким образом, эти цифры могут быть исключены из других единиц поля. Существуют вариации этого, называемые голыми тройняшками и так далее. Близнецы оказались наиболее эффективными.

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

Что теперь? Ну и поиск грубой силы. Выберите нерешенную коробку и повторяйте ее решения, в каждом проходе применяя последовательность устранения ограничений, пока вы либо не решите проблему, либо не остановитесь. Если вы остановитесь — изначально выбранное решение не является хорошим выбором, переходите к следующему, пока решение не будет найдено.

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

Вот скриншот агента ИИ в действии:

Обобщая идею: когда у вас есть функция, которая имеет набор возможных решений на выбор — идите вперед и подумайте, как вы могли бы ограничить возможные решения, чтобы уменьшить пространство поиска. Затем грубым перебором просматривайте каждый, пока не будет найден ответ.

Помимо отличного знакомства с поиском, первый проект также дал мне отличное введение в Anaconda, «Ведущая открытая платформа для научных исследований на базе Python». Думайте об этом как о среде Python, загруженной библиотеками и инструментами для обработки данных. Если этого недостаточно, он может «контейнеризировать» ваши среды Python, которые полностью изолированы и загружаются между машинами/платформами. Вы можете настроить среду Python 2 и среду Python 3, загрузить их на одну и ту же машину, и ни одна из них не повлияет друг на друга. И снова, не говоря уже о том, что Anaconda поставляется с предустановленными пакетами, связанными с данными/мл.

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