Часть 2. Построение алгоритма поиска лучшего хода

Поскольку было задействовано много шагов, для простоты чтения я разделил это обсуждение на 2 части. Здесь, в Части 2, я обсуждаю использование специально созданной функции статической оценки для поиска лучшего следующего хода среди будущих ходов (и досок). Если вы хотите прочитать о том, как была построена функция статической оценки, вернитесь назад и прочитайте часть 1, которая содержит шаги 1 и 2: создание функций статической оценки и построение модели статической оценки.

Теперь мы продолжаем шаг 3!

Шаг 3: Минимакс

Создать Minimax было достаточно просто. Идея относительно проста, и ее псевдокод существует повсюду (я использовал статьи Википедии о Minimax и сокращении альфа-бета).

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

Альфа-бета-обрезка — это оптимизация Minimax, которая просто отслеживает лучшие ходы Макса и Мина, чтобы исключить (или «урезать») некоторые параметры поиска, что на практике значительно ускоряет поиск, потому что Minimax сам по себе ищет с экспоненциально возрастающей скоростью. в зависимости от того, сколько шагов в будущее вы хотите найти. (пример: поиск всех вариантов для хода 1 дает 20 вариантов, но поиск всех вариантов для хода 1, а затем ход 2 дает 20 * 20 = 400 вариантов; отсюда рост только ухудшается).

Шаг 4: Перенесите заказ

Оказывается, эффективность альфа-бета-отсечения сильно зависит от порядка, в котором просматриваются ходы, и оптимальные поиски происходят, когда сначала просматриваются «лучшие» ходы, что на практике помогает исключить больше некачественных ходов по сравнению с некачественными. вместо этого сначала рассматривались ходы.

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

Я сузил некоторые определяющие характеристики того, что делает ход «хорошим» и что делает ход «плохим». Например, превратить пешку в ферзя? Обычно отличный ход (при условии, что мы не теряем ферзя сразу после этого). Бесплатно повесить ладью? Наверное, ужасный поступок.

В целом, признаки, которые я использовал для определения силы движения, были следующими:

  • значение чека: если мы даем чек, это часто является форсирующим ходом, заслуживающим бонуса.
  • ценность продвижения: если мы продвигаем пешку, это часто очень хорошо для нашего материального баланса. Хотя конь технически возможен (в то время как ладьи/слоны обычно не подходят, потому что ферзь, по сути, представляет собой комбинацию ладьи и слона), для простоты я позволил своему движку превратиться только в ферзя.
  • позиционное значение: используя таблицы квадратов фигур, давайте бонусы / штрафы в зависимости от изменения позиции. (Пример: перемещение короля в центр в миттельшпиле влечет за собой штраф, тогда как развитие коня дает бонус).
  • стоимость захвата: даем бонус, если мы выигрываем материал от захвата, и даем штраф, если мы теряем материал после обмена захватом.
  • Висячие значения: дайте штраф, если после этого хода мы вешаем материал.

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

Шаг 5: Хэширование табуляции

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

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

Чтобы сэкономить на вычислениях, каждый раз, когда оценивалась доска, сначала вычислялся хэш (в частности, хэш «zobrist»). Затем, используя справочную таблицу, движок попытается увидеть, выполнил ли он уже оценку платы, и если да, то вернет уже вычисленный результат. В противном случае он продолжит и выполнит оценку, а затем сохранит ее для следующего раза.

Хотя это потребовало бы больше памяти, экономия времени стоила 100%, особенно учитывая экспоненциальный характер Minimax.

Шаг 6: Сокращение поздних ходов/отсечение нулевых ходов

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

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

Другая идея известна как отсечение нулевого хода или нулевая эвристика. Идея здесь звучит следующим образом:

Допустим, мы белые. Что произойдет, если мы просто откажемся от своего хода (то есть сделаем «нулевой» ход)? Если черные получают свободный ход, но ВСЕ ЕЩЕ не могут нас догнать, то, безусловно, мы полностью доминируем. Это было бы похоже на то, если бы мы дали другой футбольной команде штрафной гол, а у нас все еще было бы 2 гола.

Здесь, как часть нулевой эвристики, мы также уменьшаем нашу глубину поиска, так как если черные с их преимуществом в свободном темпе не могут догнать нас, скажем, за 3 хода, то, конечно, с нашим доминирующим преимуществом мы можем сделать так, чтобы черные тоже не может догнать нас в 5 ходов.

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

Шаг 7: Молитесь, чтобы Stockwish победил ботов chess.com

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

Честно говоря, на протяжении большей части этого процесса я думал, что мой бот обречен. Это были глупые грубые ошибки, такие как отказ от ферзей в пользу слонов или даже просто отказ от ферзей бесплатно. В более ранней итерации он даже поставил в тупик бота Мартина (рейтинг 250), даже после того, как у него было 3 ферзя, 2 из которых были потеряны.

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

На момент написания этой статьи лучшим ботом, против которого я играл и которого я победил с помощью Stockwish, был бот Zara от chess.com с рейтингом 850 (в будущем я буду тестировать более сложных ботов, мне просто лень). Примечательно, что в целях скорости я использовал только глубину поиска 4, что означает, что он будет смотреть только на 2 полных хода вперед (мой ход, затем их, затем мой, затем их). Теоретически, с большей глубиной поиска он, вероятно, мог бы превзойти даже лучших ботов!

Я попробую еще, но я очень доволен этим результатом! По крайней мере, мой бот не Мартин (известный как ужасный бот для новичков на chess.com).

Размышления

Это был довольно забавный проект (хотя временами довольно сложный)!

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

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

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

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