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

Тема в разделе "Машинное отделение", создана пользователем Сергей Марков, 11 авг 2006.

  1. TopicStarter Overlay

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Здесь можно задавать вопросы и обсуждать алгоритмы/перспективы.
  2. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Главные вопросы: Есть ли какие-нибудь определённые планы на будущее? Когда можно ожидать новую версию?

    В настоящий момент Smarthink 1.0 занимает 13-ю позицию в нашем однопроцессорном рейтинг листе. Хотелось бы увидеть возвращение в первую десятку, лучше в пятёрку. :)

    Второй вопрос - как вы организуете тестирование и оценку улучшений. Блиц-матчи или наборы тестовых позиций? Тесты с предыдущей версией или с набором оппонентов? С какими движками, книжками и т.д. Спасибо! :)
  3. TopicStarter Overlay

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Я сейчас работаю над тестированием принципиально нового метода. У меня есть версия, которая немножко сильнее 1.0, пунктов на 15.
    По моим оценкам, новый метод мощет весьма существенно усилить программу. Проблема, конечно, как всегда в катастрофической нехватке времени :(

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

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    2.182
    Симпатии:
    38
    Репутация:
    3
    Оффлайн
    А что это даёт? Ведь, в партии всегда найдутся ошибки!
  5. TopicStarter Overlay

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Ну и что. Ведь используется множество партий. Причем рассматриваются ходы выигравшей стороны в партиях, выигранные игроками с ELO >2600. Если мы предположим, что ошибок в этих партиях меньше, чем не ошибочных ходов, то на множестве партий стремящемся к бесконечности наш метод будет работать. Посколько мы предполагаем, что количество ошибочных ходов существенно меньше, чем не ошибочных, то на сравнительно большом множестве партий этот подход должен работать.
  6. Fruit Александр

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    2.182
    Симпатии:
    38
    Репутация:
    3
    Оффлайн
    Таким образом, версия считается сильнее, если совпало большее число ходов. Ясно.

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

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

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Только "ручками". У меня написана специальная процедура, которая парсит pgn-файл и для каждого хода запускает процедуру сравнения. А лог пишется в файл.
  8. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Согласно этой статистики можно автоматом настраивать оценочную функцию...
    А не просто смотреть процент соответсвий :)
  9. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Я все-таки хотел бы получить ответы на свои вопросы:
    Что нового в SmarThink 1.0?
    Что есть специфического в SmarThink (чего нет у других)?

    Я сейчас работаю над тестированием принципиально нового метода.
    Это секретный метод?
  10. TopicStarter Overlay

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Так и делается. Методом спирально-покоординатного спуска.
  11. TopicStarter Overlay

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Пока что он насколько секретный, насколько и непроверенный. Когда появятся первые обнадеживающие результаты, я опубликую общее описание подхода.
  12. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    А каким образом минимизируется количество параметров в оценочной функции?
  13. TopicStarter Overlay

    Сергей Марков Учаcтник

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

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

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Я сам выбираю набор параметров. Каждый параметр сейчас подстраивается последовательно в цикле.
  15. TopicStarter Overlay

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Таких техник на самом деле в 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 (в свое время мы менялись с Ромстадом исходниками и он воспроизвел у себя многие мои методы).
  16. Fruit Александр

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    2.182
    Симпатии:
    38
    Репутация:
    3
    Оффлайн
    И где можно скачать эту замечательную процедуру? :)
  17. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Хотелось бы, чтобы ты остановился на некоторых моментах, с твоей точки зрения, заслуживающих внимания, . Интересно то, что может помочь другим улучшить свои программы.

    Например,
    - новая модель оценки атаки на короля;
    Ведь интересно, что это такое.
    И т.д.

    - усовершенствование в контроле траекторий атаки в середине игры;
    Это вообще непонятно что такое.
  18. Fruit Александр

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    2.182
    Симпатии:
    38
    Репутация:
    3
    Оффлайн
    А, ведь, и дебютную книгу можно подобрать с помощью этой статистики. Скажем, взять партии, игранные специалистами в каком-либо варианте, в другом, в третьем.....А затем, те варианты, где у проги наибольшее количество совпадений, включать в дебютную книгу....Правда, и сил многовато уйдёт :)
  19. TopicStarter Overlay

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Так по сути на этом же основано дебютное самообучение. Движок собирает статистику выигрышей/проигрышей/ничьих по сыгранным вариантам и эта статистика потом используется при выборе варианта.
  20. TopicStarter Overlay

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    В смысле? Каждый автор для своей программы сам ее пишет :)
    Вы имеете в виду, нельзя ли эту процедуру включить в релиз движка? Можно-то можно, только зачем? С движком производится "заводская" подстройка, улучшить ее в "домашних условиях" если и можно, то только на доли процента.
  21. TopicStarter Overlay

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Ну... Модель атаки на короля это набор алгоритмов при помощи которых движок оценивает атаку :) А что конкретно интересует в этих алгоритмах?

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

    Вы - Коршунов, или ник просто совпадение? :)
    Вы занимаетесь шахматным программированием?
  22. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Кошунов - это Игорь Коршунов. Автор Каллисто и WildCat. :)
    А что за стандартная схема с R=2/1?
    Мне казалось что Стандартная схема с R=3...
    (у меня R=3,2,1 - но обычно 3)
  23. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Про траектории... Ну вкратце тут идея такова, что для некоторых бесперспективных "тихих" ходов в дереве перебора глубина перебора уменьшается. Важно чтобы в число "сокращенных" ходов не попали те, которые относятся к перемещению фигур по траекториям атаки.

    Это в рамках LMR ?
  24. TopicStarter Overlay

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Я и говорю, что у меня нестандартная :)
    Просто в SmarThink есть другие агрессивные сокращения перебора и R=3 в нем не катит.
  25. atoku Модератор

    • Команда форума
    Рег.:
    04.02.2006
    Сообщения:
    2.949
    Симпатии:
    8
    Репутация:
    0
    Адрес:
    USA
    Оффлайн
    Сергей, а вы не могли бы сгенерировать версию для Линукс с march=amd64? Я бы с удовольствием потестировал.
  26. TopicStarter Overlay

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    В рамках OBP :) :) :)

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

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Постараюсь сделать на неделе.
  28. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    OBP, LMR, Forward, History...
    Как не называй, смысл примерно одинаков :)
  29. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Если Прунинг - полное отсечение ветви, а Редукшн - сокращенный перебор на ветви - то правильней этот метод называть Редукшн...
  30. atoku Модератор

    • Команда форума
    Рег.:
    04.02.2006
    Сообщения:
    2.949
    Симпатии:
    8
    Репутация:
    0
    Адрес:
    USA
    Оффлайн
    Я буду в отъезде до четверга. Мой e-mail anton на kulchitsky.org. Спасибо! Жду с нетерпением такой возможности! Могу и помочь скомпилировать тоже.
  31. TopicStarter Overlay

    Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Пожалуй.
    Смысл в том, что несколько первых "тихих" ходов в "тихих" узлах смотрятся на полную глубину. А остальные на усеченную. Если усеченный перебор возвращает >alpha, то перебираем этот ход на полную глубину.
  32. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Да я знаю. В Анечке Редукшн есть начиная с версии 0.06 (то есть версии Которой нет и трех месяцев с момента начала разработки), и в версии 0.07 дает прибавку... Более 100 пунктов!!! (нестандартная схема) Сила версии 0.07 меньше 2400 Только из-за слишком простой позиционной оценки.
  33. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Ну... Модель атаки на короля это набор алгоритмов при помощи которых движок оценивает атаку smile А что конкретно интересует в этих алгоритмах?

    Вот эти алгоритмы и интересуют. От того что ты сказал, что они новые понятнее не становится. Хотелось бы о них узнать побольше. У тебя еще много таких интересных пунктов было. Хотелось бы чтоб ты их иногда расписывал в порядке важности. И самому понятнее немного станет.

    Мой ник не не случайность. Я это и есть я.

    http://www.kasparovchess.crestbook.com/viewtopic.php?id=564 - Спец. топик для обсуждения и тестирования различных техник шахматного программирования. Я там выкладываю свои результаты по некоторым техникам (в данный момент тестирую важность бонуса ладьи на 7-ой линии). Было бы хорошо, если бы и ты свои результаты туда выкладывал.
  34. TopicStarter Overlay

    Сергей Марков Учаcтник

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

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

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    хинт на 10-15 пунктов
    У меня если всегда добавлять страшно падает сила (-144 после 128 игр).
    В нормальной версии у меня этот бонус только если есть вражеский король на 8-ой.
    Версия вообще без бонуса играет пока очень неплохо.

    Попробуй: ладья/ферзь на 8-ой.
    Помогает?

Поделиться этой страницей