Как правильно оценить шахматные позиции?

13

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

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

Например:

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

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

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

Чарльз Менгу
источник
Я думаю, что этот вопрос будет хорошо на StackOverflow. Там уже много вопросов по шахматному AI
xaisoft
3
Я думал опубликовать его на SO раньше, но я почти уверен, что он будет закрыт как неконструктивный или не реальный вопрос там. Может быть, если мне нужно больше внимания уделять самому коду, но я думаю, что для функции оценки требуется знание шахмат, а не столько кода или алгоритмов.
Чарльз Менгуй
Как точно. Единственный, абсолютно точный способ - выиграть, проиграть или сыграть вничью.
Эдвина Оливер

Ответы:

9

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

https://www.chessprogramming.org/Evaluation

Ева Фриман
источник
5

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

Пабло С. Оджал
источник
5

У меня такое чувство, что я немного опаздываю с этим ответом, но - я также нахожусь в процессе создания двигателя. Исходный код в Python (который довольно легко читать, даже если вы не знаете) и доступен здесь , если вы хотите , чтобы прочитать его. Список активных в данный момент «эвристики» (на момент публикации):

  • Чем дальше развиты (ближе к противоположной стороне) фигуры, тем лучше
  • Пешки ближе к раскрутке хороши
  • Короли оцениваются отдельно в зависимости от того, в какой фазе находится игра (дебют, мидлгейм, эндшпиль)
  • Если игрок имеет и епископ, что получает бонус
  • Если игрок выпал из замка, получите бонус
  • Отдельные пешки (пешки без них) не годятся
  • Двойные пешки (две пешки в одном файле без пропуска между ними) не годятся
  • Наличие всех 8 пешек не обязательно является хорошей вещью и наказывается (они загромождают доску и мешают)
  • Посмотрите на эту отличную функцию оценки, которая также используется
  • Епископы с большим количеством пешек на том же цветном квадрате, что и слон, наказываются (они не так хороши в людных ситуациях)
  • Пока не реализовано, но планируется: рыцари получают бонус в более людных ситуациях

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

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

Этот ответ мог быть длинным, запоздалым и не по теме, но я надеюсь, что он был полезен в любом случае.

mishaturnbull
источник
4

Удивительно, но оказывается, что механизм Minimax будет играть достаточно хорошо, когда функция оценки является случайной ; это называется эффектом Била и вытекает из того принципа, что позиции, которые дают вам больше опций, а оппоненту меньше опций, как правило, благоприятны. Один разумный способ последовательно и эффективно генерировать случайные оценки - это генерировать хеш-код Зобриста для позиции (используя коэффициенты, выбранные случайным образом в начале игры) и получать случайную оценку непосредственно из хеш-кода.

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

Если, с другой стороны, вы хотите разработать механизм анализа, чтобы помочь игрокам или комментаторам-людям понять нюансы позиции, возможно, стоит реализовать обычную функцию оценки с использованием установленных материальных ценностей и теории позиционирования . Хороший пример подает Эд Шредер « Inside Rebel» , документирующий основные конструктивные особенности уважаемого движка, используемого в нескольких шахматных компьютерах Mephisto. Возможно, вы захотите использовать определенную степень машинного обучения, чтобы определить относительную важность каждого элемента вашей функции оценки, а также выделить эти элементы по отдельности для представления в графическом интерфейсе.

Chromatix
источник
3

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

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

http://www.top-5000.nl/ZW_Rybka_Fruit.pdf http://danheisman.home.comcast.net/~danheisman/Articles/evaluation_of_material_imbalance.htm

Прохожий
источник
0

Эта ссылка - лучшая отправная точка ИМХО. Я использую это в качестве отправной точки для своей шахматной программы и считаю ее простой для понимания и полезной.

https://chessprogramming.wikispaces.com/Simplified+evaluation+function

techcraver
источник
2
Не могли бы вы кратко рассказать о содержании ссылки?
Пабло С. Оджал
Сайт Wikispaces больше не существует. Исправлена ​​ссылка на его новый дом: chessprogramming.org/Simplified_Evaluation_Function
Chromatix
0

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

  1. Определите параметры
  2. Дайте параметрам номинальные (стартовые) значения
  3. Запустите двигатель, чтобы увидеть, как он работает
  4. Настройте значения параметра, чтобы попытаться улучшить его производительность

Затем повторяйте шаги 3 и 4, пока не достигнете своей цели в производительности.

Обычный подход к этому - создать лабораторию, в которой двигатели сталкиваются на турнирах по двигателям. Используются несколько игр, в которых движок воспроизводит оба цвета. Основные интересные турниры включают в себя запуск двигателя со значением параметра A против того же двигателя со значением параметра B.

Как вы, вероятно, можете догадаться, результаты этого подхода сильно зависят от:

  • Параметры выбраны
  • Как указаны параметры
  • Как значения параметров меняются на протяжении всего тестирования
  • Как работают двигатели (ограниченная глубина слоя, ограниченное время, чувствительность и т. Д.)

Этот подход также занимает много времени.

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

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

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

В этом исследовательском проекте было использовано 36 параметров, включая все материальные значения фигур и многие из наиболее распространенных критериев стратегической оценки, таких как обратные пешки, слабые квадраты, слон и т.д. Однако исследователи добавили некоторые новые параметры, такие как «давление короля», значения «подвижности» для каждого вида фигуры, ладья на файле рядом с королем, ладья на полуоткрытом файле, ладья, атакующая короля на - / b- / g- / h-file, разделение между пройденной пешкой и защищающимся королем и многое другое.

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

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

* Протест о фазе подхода, исследователи использовали в порядке. В своем введении к Понимание шахматной ход за ходом , Джон Нанн выбрал «... трудно бороться игры между сильными гроссмейстерами ...» , чтобы проиллюстрировать свои темы. Затем он добавляет:

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

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

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

jaxter
источник