Проект SmarThink: вопросы, ответы, обсуждение

Здесь можно задавать вопросы и обсуждать алгоритмы/перспективы.

Я сейчас работаю над тестированием принципиально нового метода. У меня есть версия, которая немножко сильнее 1.0, пунктов на 15.
По моим оценкам, новый метод мощет весьма существенно усилить программу. Проблема, конечно, как всегда в катастрофической нехватке времени

Для тестирования используются разные способы: главным образом, матчи против наборов движков. Есть несколько таких наборов. Прежде всего, в них входят, конечно, сильнейшие движки: Rybka, Shredder, Fritz, Fruit, Hiarcs, Junior.
Тесты используются сравнительно редко.
Сейчас есть еще подстройка по БД: когда для большой БД партий для каждой позиции производится перебор с глубиной 4-5 полуходов и затем выбранный движком ход сравнивается с ходом в партии. Этот подход был в свое время предложен командой Deep Blue.

А что это даёт? Ведь, в партии всегда найдутся ошибки!

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

Таким образом, версия считается сильнее, если совпало большее число ходов. Ясно.

"когда для большой БД партий для каждой позиции производится перебор с глубиной 4-5 полуходов и затем выбранный движком ход сравнивается с ходом в партии"

А как это осуществить? Как потом быстро узнать сколько ходов сопало?

Только "ручками". У меня написана специальная процедура, которая парсит pgn-файл и для каждого хода запускает процедуру сравнения. А лог пишется в файл.

Согласно этой статистики можно автоматом настраивать оценочную функцию...
А не просто смотреть процент соответсвий

Так и делается. Методом спирально-покоординатного спуска.

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

А каким образом минимизируется количество параметров в оценочной функции?

- BM-extension;
- новая модель оценки атаки на короля;
- новые psq;
- использование SEE для оценки проходных;
- "скользящие" оценки в зависимости от стадии игры;
- новая оценка мобильности;
- полный ретьюнинг компонентов оценочной функции;
- усовершенствование в контроле траекторий атаки в середине игры;
- UCI-интерфейс;
- новый механизм распределения времени;
- использование данных о текущих угрозах для улучшения упорядочения ходов;
- незначительные изменения в расширениях поиска;
- добавлены шахи в ФВ;
- исправлен ряд ошибок и внесено мн-во мелких изменений;
- произведена оптимизация кода.

Вот. Может быть что-то и забыл...

Я сам выбираю набор параметров. Каждый параметр сейчас подстраивается последовательно в цикле.

Таких техник на самом деле в SmarThink очень много. Иногда новации незначительны, иногда существенны. Иногда я просто не знаю, что это новации. Из-за того, что авторы держат большую часть своих методов в секрете, многие из методов переоткрываются по 2-3 раза. Например, SmarThink имеет эвристику, определяющую может ли конь "перехватить" проходную пешку. Позже я узнал, что подобный метод используется, например, в Gandalf. Аналогично, например, SmarThink увеличивает время обдумывания не только в случае падения оценки, но и в случае ее роста. Наблюдая за игрой движков можно заметить, что так же делает Ruffian. SmarThink активно углубляет/сокращает перебор, и некоторые из таких продлений/сокращений более чем неклассические. SmarThink использует R=2/1 при переборе с пустым ходом. SmarThink использует неклассическую схему Pruning/razoring. SmarThink использует fail-hard клон PVS, тоже несколько неклассический. SmarThink имеет множество эндшпильных эвристик, касающихся как оценки, так и перебора. Многие из этих эвристик не реализованы в известных движках с открытыми исходниками. SmarThink основан на BITBOARDS, но не используется повернутые таблицы. Вместо этого используются битовые векторы и сложные неклассические BITBOARD-операции. В принципе, многие методы SmarThink оказали существенное влияние на Glaurung (в свое время мы менялись с Ромстадом исходниками и он воспроизвел у себя многие мои методы).

И где можно скачать эту замечательную процедуру?

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

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

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

Ну... Модель атаки на короля это набор алгоритмов при помощи которых движок оценивает атаку А что конкретно интересует в этих алгоритмах?

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

Вы - Коршунов, или ник просто совпадение?
Вы занимаетесь шахматным программированием?

Кошунов - это Игорь Коршунов. Автор Каллисто и WildCat.
А что за стандартная схема с R=2/1?
Мне казалось что Стандартная схема с R=3...
(у меня R=3,2,1 - но обычно 3)

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

Это в рамках LMR ?

Я и говорю, что у меня нестандартная
Просто в SmarThink есть другие агрессивные сокращения перебора и R=3 в нем не катит.

В рамках OBP

Ordering-based pruning. Специфическая разновидность Forward pruning. Во Fruit это History pruning.

Постараюсь сделать на неделе.

OBP, LMR, Forward, History...
Как не называй, смысл примерно одинаков

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

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

Да я знаю. В Анечке Редукшн есть начиная с версии 0.06 (то есть версии Которой нет и трех месяцев с момента начала разработки), и в версии 0.07 дает прибавку... Более 100 пунктов!!! (нестандартная схема) Сила версии 0.07 меньше 2400 Только из-за слишком простой позиционной оценки.

Раньше все было описано в терминах "тропизма". Теперь учитываются атаки фигур на поля соседние с королем и на пешечное прикрытие короля, причем в т.ч. и "сквозные" атаки. Отдельно есть бонус за атаку фигуры на "зону" короля противника + отдельно оцениваются сами поля (стоят ли на них фигуры, защищены ли они фигурами). Бонус за атаку масштабируется в соответствие с количеством дефектов в пешечном щите. Оценка дефектов практически изменений не претерпела по сравнению с 0.17.

Можно.
Кстати, хинт на 10-15 пунктов. Попробуй: ладья/ферзь на 8-ой