Определяем веса шахматных фигур регрессионным анализом

    Здравствуй, Хабр!

    В этой статье речь пойдёт о небольшом программистском этюде на тему машинного обучения. Замысел его возник у меня при прохождении известного здесь многим курса «Machine Learning», читаемого Andrew Ng на Курсере. После знакомства с методами, о которых рассказывалось на лекциях, захотелось применить их к какой-нибудь реальной задаче. Долго искать тему не пришлось — в качестве предметной области просто напрашивалась оптимизация собственного шахматного движка.

    Вступление: о шахматных программах



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

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

    Строго говоря, настоящая оценка может принимать только три значения: выигрыш, проигрыш или ничья — 1, 0 или ½. По теореме Цермело для любой заданной позиции она определяется однозначно. На практике же из-за комбинаторного взрыва ни один компьютер не в состоянии просчитать варианты до листьев полного дерева игры (исчерпывающий анализ в эндшпильных базах данных — это отдельный случай; 32-фигурных таблиц в обозримом будущем не появится… и в необозримом, скорее всего, тоже). Поэтому программы работают в так называемой модели Шеннона — пользуются усечённым деревом игры и приближённой оценкой, основанной на различных эвристиках.

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

    Первые такие усовершенствования поиска появились ещё на заре шахматного программирования, в 60-х годах XX в. Можно упомянуть, например, технику форсированного варианта (ФВ) — продление отдельных ветвей поиска до тех пор, пока позиция не «успокоится» (закончатся шахи и взаимные взятия фигур). Продления существенно увеличивают тактическую зоркость компьютера, а также приводят к тому, что дерево поиска становится очень неоднородным — длина отдельных ветвей может в несколько раз превышать длину соседних, менее перпективных. Другие улучшения поиска, наоборот, представляют собой отсечения или сокращения поиска — и здесь критерием отбрасывания плохих вариантов может, в числе прочего, служить всё та же статическая оценка.

    Параметризация и улучшение поиска методами машинного обучения — отдельная интересная тема, но сейчас мы оставим её в стороне. Займёмся пока только оценочной функцией.

    Как компьютер оценивает позицию


    Статическая оценка представляет собой линейную комбинацию различных признаков позиции, взятых с некоторыми весовыми коэффициентами. Какие это признаки? В первую очередь, количество фигур и пешек у той и другой стороны. Следующий важный признак — положение этих фигур, централизация, занятие дальнобойными фигурами открытых линий и диагоналей. Опыт показывает, что учёт только этих двух факторов — суммы материала и относительной ценности полей (зафиксированной в виде таблиц для каждого типа фигур) — при наличии качественного поиска уже может обеспечивать силу игры в диапазоне до 2000-2200 пунктов Эло. Это уровень хорошего первого разряда или кандидата в мастера.

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


    Одна из самых «навороченных» оценочных функций была у машины Deep Blue, прославившейся своими матчами с Каспаровым в 1996-97 гг. (подробную историю этих матчей можно прочитать в недавней серии статей на Geektimes.)

    Широко распространено мнение, что сила Deep Blue основывалась исключительно на колоссальной скорости перебора вариантов. 200 миллионов позиций в секунду, полный (без отсечений) перебор на 12 полуходов — к таким параметрам шахматные программы на современном железе только-только приближаются. Однако, дело было не только в быстродействии. По объёму «шахматных знаний» в оценочной функции эта машина также намного превосходила всех. Оценка Deep Blue была реализована аппаратно и включала до 8000 различных признаков. Для настройки её коэффициентов привлекались сильные гроссмейстеры (достоверно известно о работе с Джоэлем Бенджамином, тестовые партии с разными версиями машины играл Давид Бронштейн).

    Не располагая такими ресурсами, как создатели Deep Blue, ограничим задачу. Из всех признаков позиции, учитываемых для подсчёта оценки, возьмём самый значимый — соотношение материала на доске.

    Стоимость фигур: простейшие модели


    Если взять любую шахматную книгу для начинающих, сразу за главой с объяснением шахматных ходов обычно приводится табличка сравнительной ценности фигур, примерно такая:
    Тип Стоимость
    Пешка 1
    Конь 3
    Слон 3
    Ладья 5
    Ферзь 9
    Король
    Королю иногда приписывается конечная стоимость, заведомо бóльшая, чем сумма всего материала на доске — например, 200 единиц. В данном исследовании мы оставим Его Величество в покое, и рассматривать королей не будем вообще. Почему? Ответ простой: они всегда присутствуют на доске, поэтому их материальная оценки взаимно вычитаются, и на общий баланс сил не влияют.

    Приведённые стоимости фигур должны рассматриваться только как некоторые базовые ориентиры. В реальности фигуры могут «дорожать» и «дешеветь» в зависимости от ситуации на доске, а также от стадии партии. В качестве поправки первого порядка обычно рассматривают комбинации из двух-трёх фигур — своих и противника.

    Вот как оценивал различные сочетания материала в своём классическом «Учебнике шахматной игры» третий чемпион мира Хосе-Рауль Капабланка:

    Хосе-Рауль КапабланкаС точки зрения общей теории слона и коня следует считать одинаково ценными, хотя, по моему убеждению, слон в большинстве случаев оказывается более сильной фигурой. Между тем считается вполне установленным, что два слона почти всегда сильнее двух коней.

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

    Ладья по силе равна коню и двум пешкам или же слону и двум пешкам, но, как сказано выше, слон в борьбе против ладьи сильнее коня. Две ладьи несколько сильнее ферзя. Они немного слабее двух коней и слона и еще слабее двух слонов и коня. Сила коней падает по мере размена фигур на доске, сила же ладьи, напротив, возрастает.

    Наконец, как правило, три легкие фигуры сильнее ферзя.


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

    B > N > 3P
    B + N = R + 1.5P
    Q + P = 2R

    И значения, им удовлетворяющие:

    P = 100
    N = 320
    B = 330
    R = 500
    Q = 900
    K = 20000


    Имена переменных соответствуют обозначениям фигур в английской нотации: P — пешка, N — конь, B — слон, R — ладья, Q — ферзь, K — король. Стоимости здесь и далее указаны в сотых долях пешки.

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

    В качестве эксперимента я провёл небольшой матч-турнир четырёх версий своего движка GreKo с разными весами фигур против трёх других программ — каждая из версий сыграла 3 матча по 200 партий со сверхмалым контролем времени (1 секунда + 0.1 сек. на ход). Результаты приведены в таблице:

    Версия Пешка Конь Слон Ладья Ферзь vs. Fruit 2.1 vs. Crafty 23.4 vs. Delfi 5.4 Рейтинг
    GreKo 12.5 100 400 400 600 1200 61.0 76.0 71.0 2567
    GreKo A 100 300 300 500 900 55.0 69.0 73.0 2552
    GreKo B 100 320 330 500 900 57.0 71.0 64.0 2548
    GreKo C 100 325 325 550 1100 72.5 74.5 69.0 2575
    Мы видим, что некоторые вариации в весах фигур приводят к колебаниям силы игры в диапазоне 20-30 пунктов Эло. Более того, одна из тестовых версий показала даже лучший результат, чем основная версия программы. Впрочем, однозначно утверждать об усилении игры на таком малом количестве партий преждевременно — доверительный интервал вычисления рейтинга составляет сравнимую величину в несколько десятков пунктов Эло.

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

    Материальный перевес и логистическая кривая


    Для статистического анализа был взят PGN-файл, содержащий почти 3000 шахматных партий в блиц между 32 разными шахматными движками, в диапазоне от 1800 до 3000 пунктов Эло. С помощью специально написанной утилиты для каждой партии был составлен список материальных соотношений, возникших на доске. Каждое соотношение материала попадало в статистику не сразу после взятия фигуры или превращения пешки — сначала должны были произойти ответные взятия или несколько «тихих» ходов. Таким образом отфильтровывались краткосрочные «скачки материала» на 1-2 хода при разменах.

    Затем по уже известной нам шкале «1-3-3-5-9» рассчитывался материальный баланс позиции, и для каждого его значения (от -24 до 24) накапливалось количество очков, набранных белыми. Полученная статистика представлена на следующем графике:



    По оси x — материальный баланс позиции ΔM с точки зрения белых, в пешках. Он вычисляется как разность суммарной стоимости всех белых фигур и пешек и такой же величины для чёрных. По оси y — выборочное математическое ожидание результата партии (0 — победа чёрных, 0.5 — ничья, 1 — победа белых). Мы видим, что экспериментальные данные очень хорошо описываются логистической кривой:

    p(\Delta M)=\frac{1}{1+e^{-\alpha \Delta M}}

    Простой визуальный подбор позволяет определить параметр кривой: α=0.7, размерность его — обратные пешки.
    Для сравнения на графике приведены ещё две логистические кривые с другими значениями параметра α.

    Что это означает на практике? Пусть мы видим случайно выбранную позицию, в которой у белых перевес в 2 пешки (ΔM = 2). С вероятностью, близкой к 80%, мы можем утверждать: партия закончится победой белых. Аналогично, если у белых не хватает слона или коня (ΔM = -3), их шансы не проиграть всего лишь около 12%. Позиции с материальным равенством (ΔM = 0), как и можно было ожидать, чаще всего заканчиваются вничью.

    Постановка задачи


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

    x_j=(\Delta_P,\Delta_N,\Delta_B,\Delta_R,\Delta_Q)_j

    где Δi, i = P...Q — разность количества белых и чёрных фигур типа i (от пешки до ферзя, короля не считаем). Эти вектора представляют собой материальные соотношения, встретившиеся в партиях (одной партии обычно соответствует несколько векторов).

    Пусть дан также вектор yj, компоненты которого принимают значения 0, 1 и 2. Эти значения соответствуют исходам партий: 0 — победа чёрных, 1 — ничья, 2 — победа белых.

    Требуется найти вектор θ стоимостей фигур:

    \theta=(\theta_P, \theta_N, \theta_B, \theta_R, \theta_Q)

    минимизирующий функцию стоимости для логистической регрессии:

    J(\theta)=\frac{1}{m}[\sum_{i=1}^{m}y^{(i)}log(h_\theta(x^{(i)}))+(1-y^{(i)})log(1-h_\theta(x^{(i)}))],
    где
    h_\theta(x)=\frac{1}{1+e^{-\theta^Tx}} — логистическая функция для векторного аргумента.

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

    J_{reg}(\theta)=J(\theta)+\frac{\lambda}{2m}\sum_{j=1}^{5}{\theta_j^2}

    Величина коэффициента при параметре регуляризации выбирается небольшая, в данном случае использовалось значение λ=10-6.

    Для решения задачи минимизации применим простейший метод градиентного спуска с постоянным шагом:

    \theta_{n+1}\leftarrow \theta_n - \alpha \nabla J_{reg}(\theta_n)

    где компоненты градиента функции Jreg имеют вид:

    (\nabla J_{reg})_0=\frac{1}{m}\sum_{i=1}^{m}{(h_{\theta}(x^{(i)})-y^{(i)})x_0^{(i)}}

    (\nabla J_{reg})_j=\frac{1}{m}\sum_{i=1}^{m}{(h_{\theta}(x^{(i)})-y^{(i)})x_j^{(i)}} - \frac{\lambda}{m}{\theta_j}

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

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

    Программа и результаты


    Так как первая часть задачи — разбор PGN-файлов и выделение для каждой позиции набора признаков — уже была практически реализована в коде шахматного движка, оставшуюся часть было решено также написать на C++. Исходный код программы и тестовые наборы партий в PGN-файлах доступны на github. Программа может быть собрана и запущена под Windows (MSVC) или Linux (gcc).

    Возможность использовать в дальнейшем специализированные средства вроде Octave, MATLAB, R и т.п. также предусмотрена — в процессе работы программа генерирует промежуточный текстовый файл с наборами признаков и исходами партий, который легко может быть импортирован в эти среды.

    Файл содержит текстовое представление набора векторов xj — матрицы размерности m x (n + 1), в первых 5 столбцах которой содержатся компоненты материального баланса (от пешки до ферзя), а в 6-м — результат партии.

    Рассмотрим простой пример. Ниже приводится PGN-запись одной из тестовых партий.

    [Event "OpenRating 31"]
    [Site "BEAR-HOME"]
    [Date "2013.05.09"]
    [Round "1"]
    [White "Simplex 0.9.7"]
    [Black "IvanHoe 999946f"]
    [Result "0-1"]
    [TimeControl "60+1"]
    [PlyCount "96"]
    
    1. d4 d5 2. c4 e6 3. e3 c6 4. Nf3 Nd7 5. Nbd2 Nh6 6. e4 Bb4 7. a3 Ba5 8.
    cxd5 exd5 9. exd5 cxd5 10. Qe2+ Kf8 11. Qb5 Nf6 12. Bd3 Qe7+ 13. Kd1 Bb6
    14. Re1 Bd7 15. Qb3 Be6 16. Re2 Qc7 17. Qb4+ Kg8 18. Nb3 Bf5 19. Bb1 Bxb1
    20. Rxb1 Nf5 21. Bd2 a5 22. Qa4 h6 23. Rc1 Qb8 24. Bxa5 Qf4 25. Qb4 Bxa5
    26. Nxa5 Kh7 27. Nxb7 Rab8 28. a4 Ne4 29. h3 Rhc8 30. Ra1 Rc7 31. Qa3 Rcxb7
    32. g3 Qc7 33. Rc1 Qa5 34. Rxe4 dxe4 35. Rc5 Qa6 36. Nd2 Nxd4 37. Rc4 Nb3
    38. Nxb3 Qxc4 39. Nd2 Rd8 40. Qc3 Qf1+ 41. Kc2 Qe2 42. f4 e3 43. b4 Rc7 44.
    Kb3 Qd1+ 45. Ka2 Rxc3 46. Nb1 Qxa4+ 47. Na3 Rc2+ 48. Ka1 Rd1# 0-1

    Соответствующий фрагмент промежуточного файла имеет вид:

     0  0  0  0  0  0
     1  0  0  0  0  0
     2  0  0  0  0  0
     2 -1  0  0  0  0
     2  0  0 -1  0  0
     1  0  0 -1  0  0
     1  1  0 -2  0  0

    В 6-м столбце везде 0 — это результат партии, победа чёрных. В остальных столбцах — баланс числа фигур на доске. В первой строке полное материальное равенство, все компоненты равны 0. Вторая строка — лишняя пешка у белых, это позиция после 24-го хода. Обратим внимание, что предшествующие размены никак не отражены, они происходили слишком быстро. После 27-го хода у белых уже 2 лишних пешки — это строка 3. И т.д. Перед заключительной атакой чёрных у белых пешка и конь за две ладьи:

    3r4/2r2ppk/7p/8/PP3P2/1KQ1p1PP/3Nq3/8

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

    Такие же записи создаются для всех анализируемых партий, в среднем получается по 5-10 строк на игру. После разбора PGN-базы с партиями этот файл поступает на вход второй части программы, занимающейся собственно решением задачи минимизации.

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



    График сходимости функции стоимости

    Текстовый вывод программы
    C:\CHESS>pgnlearn.exe OpenRating.pgn
    Reading file: OpenRating.pgn
    Games: 2997
    Created file: OpenRating.mat
    Loading dataset...
    [ 20196 x 5 ]
    Solving (gradient method)...
    Iter 0: [ 0 0 0 0 0 ] -> 0.693147
    Iter 1000: [ 0.703733 1.89849 2.31532 3.16993 6.9148 ] -> 0.470379
    Iter 2000: [ 0.735853 2.08733 2.51039 3.47418 7.7387 ] -> 0.469398
    Iter 3000: [ 0.74429 2.13676 2.56152 3.55386 7.95879 ] -> 0.46933
    Iter 4000: [ 0.746738 2.15108 2.57635 3.57697 8.02296 ] -> 0.469324
    Iter 5000: [ 0.747467 2.15535 2.58077 3.58385 8.0421 ] -> 0.469324
    Iter 6000: [ 0.747685 2.15663 2.58209 3.58591 8.04785 ] -> 0.469324
    Iter 7000: [ 0.747751 2.15702 2.58249 3.58653 8.04958 ] -> 0.469324
    Iter 8000: [ 0.747771 2.15713 2.58261 3.58672 8.0501 ] -> 0.469324
    Iter 9000: [ 0.747777 2.15717 2.58265 3.58678 8.05026 ] -> 0.469324
    Iter 10000: [ 0.747779 2.15718 2.58266 3.58679 8.0503 ] -> 0.469324
    
    PIECE VALUES:
    
    Pawn:   100
    Knight: 288.478
    Bishop: 345.377
    Rook:   479.66
    Queen:  1076.56
    Press ENTER to finish

    После нормировки и округления получаем следующий набор величин:
    Тип Стоимость
    Пешка 100
    Конь 288
    Слон 345
    Ладья 480
    Ферзь 1077
    Король
    Проверим, выполняются ли «правила Капабланки»?
    Соотношение Численные значения Выполняется?
    B > N 345 > 288 да
    B > 3P 345 > 3 * 100 да
    N > 3P 288 < 3 * 100 нет
    B + N = R + 1.5P 345 + 288 ~= 480 + 1.5 * 100 да (с погрешностью < 0.5%)
    Q + P = 2R 1077 + 100 > 2 * 480 нет
    Результат вполне обнадёживающий. Не зная ничего о реально происходящих на доске событиях, рассматривая только исходы партий и снятый с доски материал наш алгоритм сумел вывести стоимости фигур, достаточно близкие к их традиционным значениям.

    Можно ли полученные значения использовать для усиления игры программы? Увы, на данном этапе ответ отрицательный. Тестовые блиц-матчи показывают, что сила игры GreKo от использования найденных параметров практически не изменилась, а в ряде случаев даже снизилась. Почему так произошло? Одна из очевидных причин — уже упоминавшаяся тесная связь поиска и оценки позиции. В поиске движка заложен целый ряд эвристик для отсечения неперспективных ветвей, и критерии этих отсечений (пороговые значения) тесно завязаны на статическую оценку. Меняя стоимости фигур, мы резко сдвигаем масштаб величин — форма дерева поиска меняется, требуется новая балансировка констант для всех эвристик. Это достаточно трудоёмкая задача.

    Эксперимент с партиями людей


    Попробуем расширить наш эксперимент, рассмотрев игры не только компьютеров, но и людей. В качестве массива данных для обучения возьмём партии двух выдающихся современных гроссмейстеров — чемпиона мира Магнуса Карлсена и экс-чемпиона Ананда Вишванатана, а также представителя романтических шахмат XIX столетия Адольфа Андерсена.

    Ананд и Карлсен
    Ананд и Карлсен соперничают за мировую корону

    В таблице ниже представлены результаты решения регрессионной задачи для партий этих шахматистов.
    Ананд Карлсен Андерсен
    Пешка 100 100 100
    Конь 216 213 286
    Слон 230 243 289
    Ладья 355 352 531
    Ферзь 762 786 1013
    Король
    Легко заметить, что «человеческие» значения стоимости фигур оказались вовсе не такими, каким учат начинающих в учебниках. В случае Карлсена и Ананда бросается в глаза меньший масштаб шкалы — ферзь стоит чуть больше 7.5 пешек, соответственно сжался весь диапазон для других фигур. Слон по-прежнему чуть дороже коня, но и тот, и другой не дотягивают до традиционных трёх пешек. Две ладьи оказываются слабее ферзя, и т.д.

    Надо сказать, что похожая картина наблюдается не только у Виши и Магнуса, но и для большинства гроссмейстеров, партии которых удалось протестировать. Причём какой-то зависимости от стиля не выяснилось. Значения смещены от классических в одну и ту же сторону и у позиционных мастеров вроде Михаила Ботвинника и Анатолия Карпова, и у атакующих шахматистов — Михаила Таля, Юдит Полгар…

    Одним из немногих исключений стал Адольф Андерсен — лучший европейский игрок середины XIX века, автор знаменитой «вечнозелёной партии». Вот для него значения стоимости фигур оказались очень близки к тем, которые используют компьютерные программы. Напрашиваются самые разнообразные фантастические гипотезы, вроде тайного читерства немецкого маэстро через портал во времени… (Шутка, конечно. Адольф Андерсен был крайне порядочным человеком, и никогда бы себе такого не позволил.)

    Адольф Андерсен
    Адольф Андерсен (1818-1879),
    человек-компьютер


    Почему наблюдается такой эффект со сжатием диапазона стоимости фигур? Конечно, не стоит забывать о крайней ограниченности нашей модели — учёт дополнительных позиционных факторов мог бы внести существенные коррективы. Но, возможно, дело в слабой технике реализации человеком материального перевеса — относительно современных шахматных программ, конечно. Проще говоря, человеку тяжело безошибочно играть ферзём, потому что у того слишком много возможностей. Вспоминается хрестоматийный анекдот о Ласкере (в других вариантах — Капабланке / Алехине / Тале), якобы игравшем с форой со случайным попутчиком в поезде. Кульминационной фразой было: «Ферзь только мешает!»

    Заключение


    Мы рассмотрели один из аспектов оценочной функции шахматных программ — стоимость материала. Убедились, что эта часть статической оценки в модели Шеннона имеет вполне «физический» смысл — она гладким образом (через логистическую функцию) связана с вероятностью исхода партии. Затем рассмотрели несколько распространённых комбинаций весов фигур, и оценили порядок их влияния на силу игры программы.

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

    Куда двигаться дальше? Для более точной оценки позиции можно добавлять в модель новые шахматные знания — то есть увеличивать размерность векторов x и θ. Даже оставаясь в области только материальных критериев (без учёта полей, занимаемых фигурами на доске), можно добавить целый ряд релевантных признаков: два слона, пара из ферзя и коня, пара из ладьи и слона, разноцвет, последняя пешка в эндшпиле… Шахматистам хорошо известно, как ценность фигур может зависеть от их сочетания или стадии партии. В шахматных программах соответствующие веса (бонусы или штрафы) могут достигать десятых долей пешки и более.

    Один из возможных путей (наряду с увеличением размера выборки) — использовать для обучения партии, сыгранные предыдущей версией той же самой программы. В таком случае есть надежда на бóльшую согласованность одних признаков оценки с другими. Можно также в качестве функции стоимости использовать не успех предсказания исхода партии (которая может закончиться через несколько десятков ходов после рассматриваемой позиции), а корреляцию статической оценки с динамической — т.е. с результатом альфа-бета поиска на определённую глубину.

    Однако, как уже было отмечено выше, для непосредственного усиления игры программы полученные результаты могут оказаться непригодными. Часто случается так: после обучения на сериях тестов программа начинает лучше решать тесты (в нашем случае — предсказывать результаты партий), но не лучше играть! В настоящее время в шахматном программировании мейнстримом стало интенсивное тестирование исключительно в практической игре. Новые версии топ-движков перед выпуском тестируются на десятках и сотнях тысяч партий со сверхкороткими контролями времени…

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

    В ходе исследований ни одна шахматная фигура не пострадала.

    Библиография


    Адельсон-Вельский, Г.М.; Арлазаров, В.Л.; Битман, А.Р. и др. — Машина играет в шахматы. М.: Наука, 1983
    Книга авторов советской программы «Каисса», подробно описывающая как общие алгоритмические основы шахматных программ, так и конкретные детали реализации оценочной функции и поиска «Каиссы».

    Корнилов Е. — Программирование шахмат и других логических игр. СПб.: БХВ-Петербург, 2005
    Более современная и «практическая» книга, содержит большое количество примеров кода.

    Feng-hsiung Hsu — Behind Deep Blue. Princeton University Press, 2002
    Книга одного из создателей шахматной машины Deep Blue, в подробностях рассказывающая об истории её создания и внутреннем устройстве. В приложении приведены тексты всех шахматных партий, сыгранных Deep Blue в официальных соревнованиях.

    Ссылки


    Chessprogramming Wiki — обширная коллекция материалов по всем теоретическим и практическим аспектам шахматного программирования.

    Machine Learning in Games — сайт, посвящённый машинному обучению в играх. Содержит большое количество научных статей по исследованиям в области шахмат, шашек, го, реверси, нардов и т.д.

    Kaissa — страница, посвящённая «Каиссе». Детально представлены коэффициенты её оценочной функции.

    Stockfish — сильнейшая на сегодня программа, с открытым исходным кодом.

    A comparison of Rybka 1.0 beta and Fruit 2.1
    Детальное сравнение внутреннего устройства двух популярных шахматных программ.

    GreKo — шахматная программа автора статьи.
    Была использована в качестве одного из источников тестовых компьютерных партий. Также на основе её генератора ходов и парсера PGN-нотации была изготовлена утилита для анализа экспериментальных данных.

    pgnlearn — код утилиты и примеры файлов с партиями на github.
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 45
    • +1
      По теореме Цермело…

      Не надо так пугать. Этот факт легко доказывается без аксиомы выбора, поскольку количество возможных позиций конечно.
    • +7
      По-моему, эксперимент в значительной степени некорректен. Одна и та же партия делает кумулятивный вклад в результат: после того, как равновесие было существенно нарушено (скажем, на полторы-две пешки), в подавляющем большинстве случаев процесс развивается дальше лавинообразно — разрыв увеличивается, а в данном эксперименте после этого еще несколько раз снимаются результаты, даже тогда, когда ежу понятно, что партия проиграна. Это объясняет завышенную оценку ферзя для компьютерных партий и заниженную для гроссмейстеров. Действительно, если играть до мата, как это делают компьютеры, то лишь небольшая часть выигранных эндшпилей завершается без того чтобы превращать пешки в ферзей(*), в то время как гроссмейстеры обычно сдают такие партии до превращений.

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

      * NB: эта фраза показывает, что в русском языке «ферзь» — одушевленное существительное, «пешка» — почему-то нет.
      • +1
        Спасибо, идея с одним измерением за партию интересная. Можно ещё выбирать то сочетание фигур, которое дольше всего за партию находилось на доске. Попробую поэкспериментировать с разными вариантами отбора позиций…
        • 0
          А используемый софт легко будет переиспользовать? Хочу проверить одну идею насчет оценки позиций (примерно тот же эксперимент поставить), но критерий оценки нестандартный, сейчас даже сходу затрудняюсь описать его.
          • 0
            В принципе, код достаточно простой, написан в стиле «C++ как улучшенный C». Попробуйте скачать и поразбираться — начать лучше всего с класса Position. Если возникнут вопросы, всегда готов ответить, пишите тогда в личную переписку…
            • 0
              Я осознал, что нужно что-то другое. Я хочу странного, а именно — найти простой признак, отличающий «ясные» позиции от «неясных». Формально говоря, ясность позиции — это дисперсия результата партии, если много раз сыграть эту позицию сильными движками. То есть, если результат почти всегда один и тот же, то позиция объявляется ясной. Я хочу найти простой, то есть вычислительно дешевый, способ оценки ясности. Например, кажется верным следующее утверждение: если материальная оценка сильно смещена от нуля (скажем, на 2 пешки и более), то позиция скорее всего ясная.
        • +2
          «Пешка» — тоже одушевлённое. Ср. винительный падеж для одушевлённых и неодушевлённых.
          • 0
            Разница есть только для мужского рода. В множественном числе изредка употребимы и неодушевлённые: «Я пожертвовал два коня / двух коней».
        • +3
          Обалденная статья! Огромная работа проделана и очень наглядно и интересно представлена. Спасибо большое!
          • +1
            Мне кажется, что в ваше исследование вносят искажение «личности игроков».
            Я бы предложил провести серию партий какого-либо движка самого с собой с измененными начальными условиями. Т.е., например, у одной стороны в самом начале забираем слона, у другой три пешки играем 100 партий с переменой черное-белое и смотрим на статистику.

            • 0
              Интересное предложение, но тут маленькая техническая трудность: надо где-то взять 100 (а лучше 1000, можно и больше) стартовых позиций с таким соотношением материала. Потому что движок у меня детерминированный, он будет одни и те же ходы повторять. Впрочем, это всё решаемо, конечно же.
              • +1
                Хммм. А если стартовые позиции выбирать из вашей базы, а выигрышность оценивать не по актуальному результату исторической партии, а дать доиграть партию программе за обе стороны. Потом повторить с инверсией цветов.

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

            • –1
              Очевидный недостаток такого подхода в том, что полностью игнорируется позиционная составляющая оценки. Чтобы понять это, достаточно рассмотреть два тривиальных случая:

              1. Король + Пешка против Короля
              2. Король + 2 Коня против Короля

              В первом случае, исход партии практически полностью определяется тем, успеет ли пешка добежать до поля превращения, то есть позицией. Во втором — вероятность выигрыша вроде бы должна быть больше 2 * N > P! Но всем известно, что мат двумя конями одинокому королю поставить нельзя.
              • 0
                Естественно, материальная оценка не претендует на абсолютную точность. Я об этом упомянул в статье — это всего лишь первое приближение, и оно работает только в вероятностном смысле:

                «Пусть мы видим случайно выбранную позицию, в которой у белых перевес в 2 пешки (ΔM = 2). С вероятностью, близкой к 80%, мы можем утверждать: партия закончится победой белых.»

                Более того, никакая статическая оценка в шахматах не будет правильно оценивать все позиции — без процедуры поиска никак не обойтись.
                • +1
                  Это все понятно, просто перевес в одну пешку очень сильно зависит от того сколько всего пешек на доске. Гораздо больше чем просто её вес. А это как раз и не учитывается.
                  • 0
                    Да, общее количество пешек — это хороший кандидат на добавление новых элементов в оценку, о котором я пишу в конце статьи. Причём именно пешек, а не фигур.
                • 0
                  > Во втором — вероятность выигрыша вроде бы должна быть больше 2 * N > P! Но всем известно, что мат двумя конями одинокому королю поставить нельзя.

                  Если усреднять не по позициям типа «король и два коня против короля», а по всем позициям, где у белых два лишних коня, вероятность победы будет близка к 100%. Например, «король, два коня и три пешки против короля и трёх пешек», или «король, два коня и ладья против короля и ладьи». Смысл подсчёта баланса — именно в этом.
                  • 0
                    Средняя температура по больнице, включая морг? В общем то подход имеет смысл, при условии, что не будет применяться в эндшпиле (а там он применяться конечно не будет).
                    • 0
                      Да, эндшпиль и дебют — это граничные случаи, там очень важна конкретика. В современных программах обычно различают несколько стадий партии, и для каждой пишется своя оценочная функция. Совсем малофигурные окончания, естественно, играются по готовым таблицам.
                • 0
                  Не пробовали ли вы квадратичную модель, как в StockFish? Будет ли она заметно лучше?
                  • 0
                    Пока не пробовал. Теоретически, конечно, она может быть лучше, но потребуется большее количество данных для обучения, и количество коэффициентов сразу резко возрастает — вместо пяти весов фигур надо будет рассматривать 10x10 = 100 коэффициентов (включая линейные и перекрёстные члены в квадратичной форме).
                    Мне кажется более интересным подход, который был реализован в Рыбке — большая таблица со статистикой для всех возможных соотношений материала. Она занимает несколько мегабайтов, и даёт усиление игры до 50 пунктов Эло, если я правильно помню.
                    • +1
                      Высокая стоимость фигур у Андерсена объясняется тем, что они у него сугубо атакующе-жертвенный материал, позволяющий эффектно выигрывать у соперников 19 века (не разбирающихся в современных позиционных методах игры, с помощью которых гусарские наскоки убиваются в зародыше). Поиграй бы Андерсен в своём стиле против нынешних топовых гроссов, не факт чтобы ему удалось выиграть против них хотя бы одну партию (ну, разве что, изредка в блиц).

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

                      Думаю, если бы Вы протестировали партии другого гения эффектных комбинаций позапрошлого столетия — Пола Морфи — то у него бы показатели были такие же, как и у современных шахматистов. Потому что картинным жертвам предшествовал позиционный перевес, которого не достичь без помощи пешек.
                      • 0
                        Пол Морфи — мой любимый шахматист, с его партий я начал. Увы, алгоритм сошелся к абсурдным значениям — с отрицательной стоимостью коня. Думаю, причина в том, что в базе для Морфи было слишком мало партий, он всё-таки недолго играл. Другой причиной может быть большое число партий, где он давал фору.
                      • +2
                        Здорово. Спасибо за труд, было очень интересно почитать.
                        У меня вопрос.
                        По поводу «дисперсии результатов партии» и в целом методик компьютерного анализа с опорой на результаты сыгранных партий — существуют многоходовые задачи, которые на данный момент (насколько я знаю) не могут быть решены компьютером. Например, вот задача, где предлагается поставить мат за 21 ход: chessfield.ru/chess-puzzles/filter/131072
                        Конкретно в данной задаче материальное соотношение равно, но есть и другие, где машина, имея преимущество проиграет человеку, но выиграет у другой машины.
                        Как быть с подобными позициями (партиями) при анализе и можно ли быть уверенным, что их количество не так велико, чтобы можно было ими пренебречь?
                        • +1
                          Уже не в первом комментарии встречаются рассуждения вида «а вот в такой-то позиции оценка материала будет давать сбой, потому что на самом деле там выигрыш/ничья за белых/чёрных...».

                          Конечно, всё это так! Шахматы — игра очень конкретная, никакого магического рецепта для оценки позиции нет и быть не может. Только счёт, счёт и счёт. Плюс разумная оценка на листьях :)

                          СТАТЬЯ — О ДРУГОМ.

                          Нам известно, что в оценку компьютера всегда входит материал — фигурам присваиваются определённые веса. Присваиваются чаще всего по интуиции или по традиционным меркам. Цель статьи — найти эти веса каким-то более определённым методом, чем «с потолка», дать им некоторое математическое обоснование. НЕ ОТКАЗЫВАЯСЬ ОТ ДРУГИХ ЧЛЕНОВ В ОЦЕНКЕ. А дополняя их.
                          • +2
                            Экспериментальный анализ сам по себе штука неоднозначная, поэтому подобные комментарии и встречаются — просто предпосылки и методы вызывают некоторую настороженность и неоднозначность что ли.
                            Говорить о полной математической обоснованности конечно же не приходится — на безрыбье и конь слон.
                            Посыл мне понятен — занятно, интересно. И «потолок» теперь немного ниже, но другой :)
                            Шахматы тем и прекрасны, что к математике их так просто не приручишь (по крайней мере в обозримом будущем).
                            Был бы рад почитать о ваших дальнейших ходах!
                          • 0
                            А какой там план выигрыша в этой задаче? :)
                            1. g3-g4 (обеспечиваем тропинку для белого короля)
                            Затем белый король съедает пешку на a5, потом по тропинке a5-a4-a3-a2-b1-c1-d1-e1-f1-g1-h2-g3:f3-e4-d5 вторгается на половину поля чёрных — и что делать дальше? Я там пробовал разные варианты и везде облом…
                            • 0


                              Я так понимаю, нужно поставить ферзя (e6-e7-e8Ф, что касается пешки f7, то она жертвуется) и довести чёрных до цуцванга, вынудив королём пойти на h6. Тогда ферзь матует с поля h8. При этом нужен точный порядок ходов — иначе или не укладываемся в 21 ход или даже пат. Как-то так, наверное (у меня пока решить не получилось).
                              • +1
                                Начало рассуждений верное )
                                Показать решение?
                                • 0
                                  Да, покажите. :)
                                  • 0
                                    Чтоб крепче спалось:
                                    Решение задачи
                                    • 1. g4! Ke7
                                    • 2. Ka5 Kf8
                                    • 3-16. Ka4-a3-a2-b1-c1-d1-e1-f1-g1-h2-g3-f3-e4-d5 Kf8
                                    • 17. Kd6 Kg7
                                    • 18. Ke7
                                    • 18...Kh6 19.Kf6 Kh7 20.f8=R Kh6 21.Rh8#
                                    • 18...Kh7 19.Kf6 Kh6 20.f8Q+ Kh7 21.Dg7#

                                    • +1
                                      Да, спасибо. Я сбился с верного пути на 18 ходу. По позиции чувствуется, что мат даётся с поля h8, но не та пешка у меня превращалась в ферзя для этого…
                                • +1
                                  Бывает и такое: задача — мат в 64 хода.
                                  Иллюстрация на тему неоднозначности оценки позиции по материальному перевесу.
                                  Ход белых:

                                  Задача — мат в 64 хода
                                  image

                                  Решение задачи
                                  • 1. Kxc3+ Kb1
                                  • 2. Dxf5+ Ka2
                                  • 3. Df7+ Kb1
                                  • 4. Dh7+ Ka2
                                  • 5. Dxg8+ Kb1
                                  • 6. Dh7+ Ka2
                                  • 7. Df7+ Kb1
                                  • 8. Df5+ Ka2
                                  • 9. Dd5+ Kb1
                                  • 10. Dd3+ Ka2
                                  • 11. Dc4+ Kb1
                                  • 12. Dxf1+ Ka2
                                  • 13. Dc4+ Kb1
                                  • 14. De4+ Ka2
                                  • 15. Dd5+ Kb1
                                  • 16. Dxh1+ Ka2
                                  • 17. Dd5+ Kb1
                                  • 18. Dd3+ Ka2
                                  • 19. Dc4+ Kb1
                                  • 20. Dxa6 Ka2
                                  • 21. De6+ Kb1
                                  • 22. Dc4 c6
                                  • 23. De4+ Ka2
                                  • 24. De6+ Kb1
                                  • 25. Dc4 g2
                                  • 26. De4+ Ka2
                                  • 27. De6+ Kb1
                                  • 28. Dg6+ Ka2
                                  • 29. Dg8+ Kb1
                                  • 30. Dxg2 Ka2
                                  • 31. Dg8+ Kb1
                                  • 32. Dc4 h4
                                  • 33. De4+ Ka2
                                  • 34. De6+ Kb1
                                  • 35. Dc4 h5
                                  • 36. De4+ Ka2
                                  • 37. De6+ Kb1
                                  • 38. Dc4 h3
                                  • 39. De4+ Ka2
                                  • 40. De6+ Kb1
                                  • 41. Dxh3 Ka2
                                  • 42. De6+ Kb1
                                  • 43. Dc4 h4
                                  • 44. De4+ Ka2
                                  • 45. De6+ Kb1
                                  • 46. Dc4 h3
                                  • 47. De4+ Ka2
                                  • 48. De6+ Kb1
                                  • 49. Dxh3 Ka2
                                  • 50. De6+ Kb1
                                  • 51. Dc4 c5
                                  • 52. De4+ Ka2
                                  • 53. De6+ c4
                                  • 54. Dxc4+ Kb1
                                  • 55. De4+ Ka2
                                  • 56. De6+ Kb1
                                  • 57. Dc4 f1=D
                                  • 58. Dxf1+ Ka2
                                  • 59. Df7+ Kb1
                                  • 60. Dc4 e2
                                  • 61. Dxe2 Ka2
                                  • 62. De6+ Kb1
                                  • 63. Dc4 ~
                                  • 64. Df1#

                                  • 0
                                    По моему на 20 ходу черные ставят ферзя вместо отступления и будет ничья.
                                    • 0
                                      Полагаю, что нарушение последовательности, наоборот, может лишь приблизить мат.
                                      Суть — используя характерный прием с последовательностью шахов и ключевое поле с4, вынуждать черных отдавать одну за другой фигуры в цикле до возникновения цугцванга, после которого и следует неизбежный мат. Если черные проведут ферзя, то белые его съедят и мясорубка продолжит работать дальше по тому же принципу.
                                      • 0
                                        Нет, принцип будет нарушен. После постановки ферзя на 20-м ходу его нельзя съесть этим же принципом, и уже нельзя получить цунгцванг для мата. Поставте позицию к 20му ходу, и вместо хода королем поставте ферзя и попробуйте его забрать после этого на любом ходу.
                                        • 0
                                          Давайте разберем, я не против. На 20-ом ходу после взятия черной ладьи получаем данную позицию.
                                          В случае хода черных на f1 с проведением пешки в ферзи, белые тут же съедают оного на 21-ом ходу с шахом, вынуждая черного короля пойти на a2, после чего продолжается та же самая свистопляска с шахами и постановкой белого ферзя на c4 при черном короле на b1, вынуждая черных точно так же продолжать отдавать фигуры (ходить пешками) вплоть до последнего цугцванга, когда фигур для «отсрочки мата» уже не останется.

                                          superposition
                              • 0
                                Отличная статья, респект.
                                Можно немного отвлеченный вопрос?

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

                                Или это слишком сложно?
                                • 0
                                  Думаю, что компьютерам уже поздно учиться у людей, так как они обогнали их в шахматах навсегда — на 600 пунктов Эло и больше. Поэтому вопрос индивидуального стиля в сравнении с людьми не стоит — как не стоит он в игре гроссмейстера с разрядником (более сильный шахматист может выиграть как угодно — хоть в стиле Морфи с лихой атакой, хоть в стиле Карпова с позиционным зажимом).

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

                                  Вот интересная статья про стили, оценку и поиск, хотя и старинная: http://www.thorstenczub.de/complcss2.html
                                  • 0
                                    Программа Deep Thought (предшественница Deep Blue) училась именно на партиях людей. Это был конец 80-х — компьютеры как раз приближались по рейтингу к людям, но ещё им уступали.
                                    Вот статья о том, как настраивали её оценку: www.tim-mann.org/DT_eval_tune.txt
                                  • 0
                                    Хорошая статья. В SmarThink в своё время я пошёл примерно по тому же пути, только модель материала у меня имеет существенно больше параметров. Во-первых, для каждой фигуры есть отдельно миттельшпильная и эндшпильная оценки, а во-вторых добавлены ещё оценки отдельных подмножеств. Хотя, конечно, сейчас уже нужно эту часть переделывать, т.к. решая коммерческие задачи я вместе с коллегами написал большой фреймворк для автоматического построения предиктивных моделей по большим массивам…
                                    • 0
                                      Интересно, насколько можно усилить программу исключительно подстройкой параметров? Недавно много обсуждали программу Жираф, там автор использовал машинное обучение не только для оценки, но и для настройки эвристик поиска и сортировки ходов. Правда, программа не очень сильная пока что, где-то 2300-2400.

                                      arxiv.org/pdf/1509.01549v2.pdf
                                      • 0
                                        Это вопрос, который, наверное, не имеет однозначного ответа, т.к. всё зависит от того, насколько хороша текущая оценочная функция :)
                                        Я веду исследования как раз в этом направлении: тюнинг как оценки, так и некоторых параметров поиска. Думаю, что за этим будущее, но там есть ряд серьёзных сложностей, конечно. Например, я много экспериментировал в попытках сделать более точную модель отсечений — пунктов 30, наверное, я на этом собрал, но там трудно правильно сформулировать целевую функцию, т.к. нужно правильно мерить негативный эффект от ошибки, а это весьма нетривиальная задача.

                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                    Самое читаемое