Владимир Медведев WinPooh73

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

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

К сожалению, непосредственная подстановка скорректированных значений для фигур не усилила программу автора — во всяком случае, больше, чем в рамках статистической погрешности. Применение же исходного метода «в лоб» к другим параметрам оценочной функции давало несколько абсурдные результаты, алгоритм оптимизации явно нуждался в некоторой доработке. Тем временем, автор решил, что очередной релиз его движка станет заключительным в длинной серии версий, берущих своё начало в коде десятилетней давности. Была выпущена версия GreKo 2015, и дальнейшие изменения в ближайшем будущем не планировались.



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

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

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

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

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

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

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