Некоторое время меня интересовали алгоритмы компьютерного шахматного ИИ (и я получил возможность поработать над ним в какой-то момент), например, Minimax , и в качестве основного компонента этих алгоритмов используется так называемая функция оценки для определения того, что является хорошая конфигурация платы, а что плохая .
Другими словами, учитывая конфигурацию вашей шахматной доски, как вы определяете, что это в ваших интересах и с какой степенью уверенности?
Например:
- Если вы владеете центром, это довольно выгодно.
- Если у вас больше фигур, чем у вашего противника, это довольно выгодно.
- Если вы потеряли свою королеву, это скорее не выгодно.
- Если у вас есть пешка, близкая к продвижению, это выгодно.
- ...
Поэтому я хотел бы попросить несколько советов о том, как создать хорошую функцию оценки, основываясь на некоторых экспертных знаниях об игре в шахматы в целом. И, если возможно, степень благоприятности (скажем, от 1 до очень неблагоприятного, до 100 - от исключительно благоприятного).
Идея в конце состоит в том, чтобы иметь возможность создать алгоритм, который будет смотреть в дерево возможностей до определенной глубины и оценивать, какая конфигурация наиболее благоприятна для следующего хода (с учетом нескольких шагов в будущем), основываясь на том, что выгоден игроку и не выгоден противнику. Но без хорошей оценочной функции алгоритм ничего не даст.
источник
Ответы:
Вот хорошая отправная точка. Сравнение материалов является ключевым (и простым), тогда вы можете настроить его так, чтобы учитывать позиционные аспекты, такие как открытые ряды / файлы / диагонали, структура пешек и т. Д.
https://www.chessprogramming.org/Evaluation
источник
В дополнение к ответу @Eve Freeman, я бы посоветовал посмотреть, как лучший компьютер в мире, Stockfish, оценивает данную позицию. Поскольку исходный код открыт, вы можете сделать это бесплатно. Я думаю, что файл с оценочной функцией, которую вы ищете, является этим .
источник
У меня такое чувство, что я немного опаздываю с этим ответом, но - я также нахожусь в процессе создания двигателя. Исходный код в Python (который довольно легко читать, даже если вы не знаете) и доступен здесь , если вы хотите , чтобы прочитать его. Список активных в данный момент «эвристики» (на момент публикации):
В одном из этих моментов я упомянул «фазу» игры (например, открытие, middlegame, эндшпиль), и если вы захотите включить это в свой движок, вы, вероятно, столкнетесь с той же проблемой, что и я: нет четкая линия, разделяющая их. Моя функция, которая решает, в какой фазе находится игра, использует несколько вещей:
Этот ответ мог быть длинным, запоздалым и не по теме, но я надеюсь, что он был полезен в любом случае.
источник
Удивительно, но оказывается, что механизм Minimax будет играть достаточно хорошо, когда функция оценки является случайной ; это называется эффектом Била и вытекает из того принципа, что позиции, которые дают вам больше опций, а оппоненту меньше опций, как правило, благоприятны. Один разумный способ последовательно и эффективно генерировать случайные оценки - это генерировать хеш-код Зобриста для позиции (используя коэффициенты, выбранные случайным образом в начале игры) и получать случайную оценку непосредственно из хеш-кода.
В противоположном конце шкалы AlphaZero и Лила проводят чрезвычайно сложную оценку каждой искомой позиции, используя большую нейронную сеть . Невозможно описать с человеческой точки зрения, какие функции эффективно реализует эта сеть, но она, несомненно, более эффективна, чем функция оценки Stockfish. Исследовательская работа AlphaZero показывает, что этот подход лучше всего подходит для поиска по дереву Монте-Карло, а не для минимакса.
Если, с другой стороны, вы хотите разработать механизм анализа, чтобы помочь игрокам или комментаторам-людям понять нюансы позиции, возможно, стоит реализовать обычную функцию оценки с использованием установленных материальных ценностей и теории позиционирования . Хороший пример подает Эд Шредер « Inside Rebel» , документирующий основные конструктивные особенности уважаемого движка, используемого в нескольких шахматных компьютерах Mephisto. Возможно, вы захотите использовать определенную степень машинного обучения, чтобы определить относительную важность каждого элемента вашей функции оценки, а также выделить эти элементы по отдельности для представления в графическом интерфейсе.
источник
Я думаю, что шахматные программисты склонны не полагаться на знания сильных шахматистов при разработке своих функций оценки, а вместо этого пробовать разные элементы, а затем проверять их в играх против других движков и решать, что оставить. Ларри Кауфман рассказывает о своих взглядах на то, что понимает человек, но похоже, что и Раджлих, и Дейли были очень ориентированы на результат и не принимали идеи Кауфмана оптом.
Одна статья, которая мне показалась интересной, была Заком Вегнером, сравнивающим оценочные функции Рыбки и Фрукта. Одной из областей, где Рыбка могла бы стать шагом вперед, было включение таблиц материального дисбаланса, основанных на конкретных комбинациях частей. Кауфман также написал статью об этом.
http://www.top-5000.nl/ZW_Rybka_Fruit.pdf http://danheisman.home.comcast.net/~danheisman/Articles/evaluation_of_material_imbalance.htm
источник
Эта ссылка - лучшая отправная точка ИМХО. Я использую это в качестве отправной точки для своей шахматной программы и считаю ее простой для понимания и полезной.
https://chessprogramming.wikispaces.com/Simplified+evaluation+function
источник
Короче говоря, стандартный подход к настройке параметров шахматного движка заключается в следующем:
Затем повторяйте шаги 3 и 4, пока не достигнете своей цели в производительности.
Обычный подход к этому - создать лабораторию, в которой двигатели сталкиваются на турнирах по двигателям. Используются несколько игр, в которых движок воспроизводит оба цвета. Основные интересные турниры включают в себя запуск двигателя со значением параметра A против того же двигателя со значением параметра B.
Как вы, вероятно, можете догадаться, результаты этого подхода сильно зависят от:
Этот подход также занимает много времени.
Более свежий (и инновационный подход) был разработан в 2010 году исследователями, использующими методы Генетического алгоритма, чтобы а) задавать параметры и б) настраивать значения параметров. Исследователи сначала запустили движок со стартовым номинальным набором значений параметров в сравнении с набором игр гроссмейстера, чтобы посмотреть, сможет ли он эффективно выбрать «лучший ход». «Лучший ход» был определен как ход гроссмейстера *. Везде, где это не удалось сделать, это было записано. Затем был опробован другой набор значений параметров и определена относительная производительность по сравнению с предыдущим прогоном.
Затем был применен программный подход к объединению значений параметров с использованием принципа генетического алгоритма выживания наиболее приспособленных. Здесь «наиболее подходящий» означает тот, который генерирует продукцию, которая наиболее близко соответствует идеалу. (Также случается, что это каламбур на статистическом методе регрессии по методу наименьших квадратов, который используется для оценки качества аппроксимации.)
Только после того, как будут найдены параметры двигателя, которые могут достаточно хорошо имитировать GM, начинается настоящая фаза турнира. На этом этапе различные наборы значений параметров снова сопоставляются друг с другом, на этот раз напрямую . Методы улучшения генетического алгоритма применяются для генерации последовательно лучших поколений двигателя.
В этом исследовательском проекте было использовано 36 параметров, включая все материальные значения фигур и многие из наиболее распространенных критериев стратегической оценки, таких как обратные пешки, слабые квадраты, слон и т.д. Однако исследователи добавили некоторые новые параметры, такие как «давление короля», значения «подвижности» для каждого вида фигуры, ладья на файле рядом с королем, ладья на полуоткрытом файле, ладья, атакующая короля на - / b- / g- / h-file, разделение между пройденной пешкой и защищающимся королем и многое другое.
К сожалению, исследователи не уточняют, как они придумали этот набор параметров, и какие альтернативные параметры они могли проверить и отклонить. Было бы разумно предположить, что они начали с гораздо большего набора и определили (методом проб и ошибок), какие из них оказали наибольшее влияние на производительность, а какие были незначительными или производными, и поэтому их можно было бы отбросить.
Если это звучит , как это могло бы быть полезным, вы можете найти исследования здесь .
* Протест о фазе подхода, исследователи использовали в порядке. В своем введении к Понимание шахматной ход за ходом , Джон Нанн выбрал «... трудно бороться игры между сильными гроссмейстерами ...» , чтобы проиллюстрировать свои темы. Затем он добавляет:
Вопрос, который поднимает доктор Нанн, предполагает, что первоначальный подход исследователей к настройке параметров двигателя, требуя, чтобы они имитировали движения гроссмейстера, может быть ошибочным, потому что человеческая игра несовершенна . На самом деле хорошо известно, что двигатели уже играют лучше, чем люди .
Поэтому, возможно , лучший подход к установлению исходных параметров будет соответствовать новому двигателю от вышестоящего существующего двигателя .
источник
Есть хороший сайт по адресу:
Это дает вам представление о том, как работают функции Stockfish.
источник