Есть ряд хороших статей, объясняющих, что такое генетические алгоритмы (например, эта). Главное, что следует отметить из этой статьи, это

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

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

который выводит:

The best solution found:
 [0. 0. 0.]

 Objective function:
 0.0

Если мы разберем это, то мы увидим следующее:

  • У нас есть функция f(X), которая принимает массив из 3 целых чисел.
  • Все эти целые числа находятся в диапазоне от 0 до 10 включительно.
  • Наша цель — минимизировать функцию f(X)
  • Поскольку f(X) просто суммирует 3 целых числа, лучшим решением будет, если все они равны 0.

Насколько сложной может быть наша функция?

Сложение трех чисел — это круто и все такое, но давайте попробуем что-нибудь посложнее.

И это работает довольно легко. Также стоит противопоставить эту функцию вот этой:

Эти две функции имеют одно и то же лучшее решение, но вторая иногда дает сбой (используя параметры по умолчанию), а первая — нет. Если вы подумаете о том, как может работать наш черный ящик model.run(), вы, вероятно, поймете, почему это происходит.

В нашей первой функции решения, близкие к [3, 1, 10], имеют более низкие значения, чем решения, расположенные дальше от [3, 1, 10]. Во второй функции наш алгоритм практически не получает обратной связи, пока мы не получим [3, 1, 10]. Вы можете увидеть это на полученных графиках:

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

Моделирование шахмат

Однако наша функция довольно произвольна — кто сказал, что она должна представлять какую-то математическую функцию.

Что, если мы сгенерируем 64 целых числа — по одному на каждую шахматную позицию. И целые числа будут между 0 и 12, представляя пустой квадрат или кусок.

Мы можем использовать библиотеку Python python-chess для создания объекта шахматной доски. Это позволит нам проверить больше свойств доски — например, допустимая ли это позиция, нет ли в данный момент патовой ситуации и т. д.

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

Нам также нужно изменить наши ограничения, чтобы включить 64 целых числа:

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

Наконец, давайте запустим наш код и распечатаем строковое представление нашей лучшей доски:

Вы можете визуализировать строку FEN на Lichess, и вы увидите:

Это должно соответствовать тому, что вы ожидаете. Чтобы позиция была «действительной», она должна включать в себя белого и черного короля. Ему не нужны никакие другие фигуры, так что это на самом деле оптимальное решение нашей задачи — правильная шахматная доска с наименьшим количеством возможных фигур!

Использование Stockfish для создания шахматных головоломок

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

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

Как мы можем знать, что есть ровно один хороший ход? Мы можем использовать шахматный движок Stockfish с открытым исходным кодом. Наша библиотека python-chess на самом деле имеет поддержку взаимодействия с движком вроде Stockfish. Это означает, что получить подробный анализ позиции так же просто, как:

info содержит много полей, но два самых важных:

score говорит нам, что Stockfish думает о позиции, которая является матом в одном.

pv (сокращение от основной вариант) сообщает нам последовательность ходов, которую движок ожидает выполнить. В этом случае он говорит, что ожидает, что белые переместят своего ферзя с f8 на g7, что означает мат.

Давайте используем их оба в функции, которая генерирует головоломки mate in three, то есть головоломки, в которых белые могут выиграть ровно за три хода.

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

  • Мат в 4 головоломки лучше, чем мат в 7 головоломки
  • Неверная позиция сильно наказывается, как и в случаях, когда игра уже окончена.

Каждый раз вы будете получать разные результаты, но вот один пример:

6kr/7b/8/r6Q/8/B7/5K2/3R2b1 w - - 0 1

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

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

И когда мы запускаем это, мы получаем:

Так много рыцарей, и все же это все еще мат в 3 головоломки.

Небольшое отступление: можем ли мы создавать реалистичные головоломки?

Все головоломки, которые мы создали, немного сомнительны. Рыцарь, очевидно, недоступен в реальной игре. Это требует отдельного поста, но есть один забавный способ создавать реалистично выглядящие головоломки, включив в функцию «оценку реалистичности».

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

Зачем это делать?

Головоломки, которые вы получаете из реальных игр, абсолютно более высокого качества, чем то, что мы создали, однако я думаю об этом как о интересном доказательстве концепции.

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