УДК 004.021

Алгоритм предварительной оценки сложности шахматных позиций

Ларин Александр Дмитриевич – студент Института информационных технологий МИРЭА – Российского технологического университета

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

Ключевые слова: Шахматы, Алгоритмизация, Искусственный интеллект, Шахматные программы, Компьютерные технологии в шахматах.

Введение

При обучении игре в шахматы в современных условиях большую роль играют шахматные задачи и анализ позиций из реальных партий. Высокий уровень игры достигается за счёт изучения различных принципов и рекомендаций и их применения (либо, в редких случаях, нарушения). Чем выше уровень знаний игрока, тем более сложные принципы и критерии он применяет при оценке позиций и выборе оптимальных решений. Различные онлайн-платформы, предоставляющие пользователям возможность решать шахматные задачи, используют для их оценки ресурсозатратные системы глубокого обучения, основывающиеся на исследовании больших баз данных шахматных задач. Целью данной работы является создание алгоритма, учитывающего заранее выбранные шахматные принципы и их веса для предварительной оценки позиций. Оценка проводится по международной системе рейтинга шахматистов ELO[1] и определяет требуемый уровень мастерства для успешного поиска оптимального решения. Правила исследуемых шахматных партий соответствуют правилам, утверждённым приказом №988 Министерства Спорта Российской Федерации [2].

Выбор критериев оценки

Первой задачей при разработке подобного алгоритма является выбор критериев оценки шахматной позиции. В качестве критериев будут выступать выбранные шахматные принципы, которые получат веса в соответствии с их сложностью для понимания. Разработка будет вестись на языке С++ из-за наличия прямого доступа к памяти и, соответственно, широких возможностей для оптимизации. Стоит отметить, что алгоритмов с подобными целями крайне мало. Предполагается существование похожих алгоритмов в системах крупнейших шахматных порталов, расположенных в интернете, но информация о них конфиденциальна. Существует единственный аналог, выполняющий задачу предварительной оценки, код которого находится в открытом доступе. Это программный продукт, лицензия на который принадлежит владельцам интернет-ресурса aimchess.com.

Код данного программного продукта находится в открытом репозитории GitHub, его автором является программист Антон Гора [3]. Алгоритм написан на языке python, использует базу данных шахматных задач, написанную на JSON.

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

Электронные ресурсы Chess.com и Lichess.org используют для оценки сложности задач инструменты больших данных, такие, как краудсорсинг. Шахматная задача получает рейтинг в соответствии со средним рейтингом участников партии, позиция из которой представляется как задача, после чего рейтинг меняется динамически в зависимости от среднего рейтинга пользователей ресурса, успешно решивших задачу. Этот способ решения является статистически надёжным только при наличии большой выборки пользователей, на которую могут рассчитывать только крупнейшие шахматные ресурсы с доступом к большим базам данных.

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

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

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

  • Количество возможных ходов пользователя;
  • Количество возможных ходов оппонента;
  • Количество пешек на доске;
  • Количество открытых вертикалей и горизонталей;
  • Количество фигур на доске;
  • Наличие ферзей у обеих сторон;
  • Контроль четырёх центральных клеток игроками.

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

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

Формула сложности и тестирование алгоритма

Первым параметром в оценке сложности позиции является базовое значение: это число, которому будет равна оценка в случае, если все критерии окажутся равны нулю. Поскольку отсчёт по системе ELO начинается со 100 пунктов, а новому игроку присваивается рейтинг 1000, базовым значением для задачи была выбрана отметка в 400 пунктов, чтобы предоставить алгоритму возможность оценить задачу как очень простую.

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

  • P1. Количество возможных ходов пользователя: от 1 до 218 [4].
  • P2. Количество возможных ходов оппонента: от 1 до 218 (Технически максимальное количество ходов в одной позиции с обеих сторон не может быть одновременно равно 218. Максимальное суммарное количество – 324).
  • P3. Количество пешек на доске: от 0 до 16.
  • P4. Количество открытых вертикалей и горизонталей: от 0 до 16.
  • P5. Количество фигур на доске: от 3 до 32.
  • P6. Наличие ферзей с обеих сторон: логический параметр, принимающий значения от 0 до 3, где 0 – полное отсутствие, 1 – ферзь только у решающего, 2 – ферзь только у противника, 3 – оба ферзя на доске.
  • P7. Контроль центральных клеток: от 0 до 218. Контроль учитывает, сколько раз центральные клетки атакованы фигурами пользователя. 

После определения возможных значений требуется определить коэффициент, на который будет умножено значение параметра. Эмпирическим путём были вычислены следующие коэффициенты (k):

  • K = 10 для количества возможных ходов пользователя и оппонента, а так же для количества фигур, количества пешек и контроля центральных клеток.
  • К = 10 для количества открытых вертикалей и горизонталей.
  • Для параметра P6 «наличие ферзей» коэффициент заменяет значение, т.к. параметр логический. Для p = 0: k = 100, для p = 1: k = 50, для p = 2: k = 50 и для p = 3: k = 100.

Таким образом итоговая формула расчёта сложности принимает вид:

ELO = 400 + 10(P1 + P2 + P3–P4 + P5 + P7) + K6

(1)

Определим также степени ошибки (отличие от оригинальной оценки в пунктах ELO):

  1. +100 пунктов: точная оценка;
  2. +200 пунктов: небольшое отклонение;
  3. +500 пунктов: среднее отклонение;
  4. +750 пунктов: высокое отклонение;
  5. +1000 пунктов: абсолютно неверная оценка.

Рассмотрим позицию, заданную следующей строкой в нотации FEN:

3rk2B/pp3p1p/2p1b3/2q5/R3Q1n1/8/1P3P

PP/1N2KBNR w K - 4 17

 (2)

Рис.1 – Оцениваемая позиция

Для изучения была выбрана задача с веб-ресурса для обучения и игры в шахматы chess.com под номером #1250671 [5]. Рейтинг сложности на момент обращения составляет 2058 пунктов по системе ELO.

По формуле (1) рассчитаем рейтинг данной задачи, учитывая, что: P1 = 52, P2 = 54, P3 = 9, P4 =7, P5 = 22, P6 = 3 (т.е. K6 = 100), P7 = 1.

Получим:

Оценка алгоритма, использовавшего формулу (1), отличается от оценки с помощью краудсорсинга, использующуюся веб-ресурсом chess.com на 198 пунктов, что является приемлемым результатом для намного менее ресурсозатратного алгоритма.

Заключение

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

Списоклитературы

  1. ЭлоА. The Proposed USCF Rating System Its Development, Theory, and Applications // Chess Live. 1967. Vol. XXII, № 8. P. 242–247.
  2. Правила вида спорта «шахматы»: 988 // Приказ. Министерство спорта Российской Федерации, 2020. с. 1–84.
  3. АнтонГора. Aimchess puzzle rating prediction: v. 1.0. aimchess.com, 2020.
  4. Гик Е.Я. Математика на шахматной доске - Москва: Наука, 1976. - 178 с. - (Научно-популярная серия).
  5. Шахматная задача #2227464 [Электронный ресурс]. URL: https://www.chess.com/puzzles/problem/2227464 (дата обращения: 29.11.2023).

Интересная статья? Поделись ей с другими: