Наш новый движок Strelka!!!

Тема в разделе "Машинное отделение", создана пользователем SDChess, 4 май 2007.

  1. ChessTerminator75 Андрей

    • Участник
    Рег.:
    22.05.2007
    Сообщения:
    121
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Челябинск
    Оффлайн
    Если уж что просить так это чтобы Юрий описал основные алгоритмы и принципы Стрелки. Прокомментировал интересные с его точки зрения моменты.
    Вот это действительно было бы интересно!
    А то при просмотре исходников Стрелки лично мне становиться грустно
    от осознания своей непроходимой тупости. :) :)
  2. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    382
    Симпатии:
    357
    Репутация:
    10
    Оффлайн
    Почему я не хочу делать многопроцессорность (по пунктам):

    1. Нет у меня подходящего компьютера для этого. И покупать пока не собираюсь – жена не поймет.
    2. Не знаю хорошего алгоритма распараллеливания альфы-беты. То, что видел, не вдохновляет. Одна надежда на то, что Коззи когда-нибудь поделится своими секретами. Но думаю, что и он ничего особенного не придумал.
    3. Многопроцессорность не дает качественного улучшения игры движка, дает только количественное. Ну будет движок считать быстрее, ну добавит сколько-то пунктов ЕЛО – ну и что? Ни уму, ни сердцу.
  3. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    382
    Симпатии:
    357
    Репутация:
    10
    Оффлайн
    Что здесь можно поделать?
    Читабельность исходного текста такое качество, которое зависит не только от самого текста, но и от читателя.
    Кого только не ругали за плохую читабельность! Тут как-то и Маркову доставалось за это. А я читал его Смарсинк - и ничего. Все очень понятно.

    Меня вот пинали за константы в коде. Мол, гораздо лучше давать им имена, и выносить определения в заголовок.
    Но это тоже - кому как нравится. Мне, например, ужасно было неудобно из-за этого читать Фрукт. Встречаешь в тексте константу, смысл ее и так понятен (без "говорящего" имени), а ответ на главный вопрос - чему она равна - находится в заголовке. И пока лезешь в заголовок - теряешь нить.
  4. Fruit Александр

    • Заслуженный
    • Участник
    Рег.:
    11.02.2006
    Сообщения:
    2.181
    Симпатии:
    38
    Репутация:
    3
    Оффлайн
    Код Смарфи не дал никаких идей для улучшения Стрелки?
  5. Booot Учаcтник

    • Участник
    Рег.:
    05.06.2006
    Сообщения:
    140
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Смарфи, будем говорить, не прост для понимания :).Лично я только "разрезав" его основной файл на отдельные файлы смог в нем ориентироваться. Стрелка в этом отношении куда как читабельнее и проще.
  6. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    382
    Симпатии:
    357
    Репутация:
    10
    Оффлайн
    Смарфи - кладезь мудрости по сравнению со Стрелкой. Идей просто вагон. Но вот уже почти год, а руки все никак не дойдут изучить его основательно.
  7. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    8
    Репутация:
    0
    Оффлайн
    Здравствуйте, Юрий, очень приятно с вами познакомиться :) На другой ветке, где у меня уже несколько постов до и после места ссылки, компьютерщики не смогли или не захотели :( , имхо, дать мне внятный и достаточно исчерпывающий ответ на просьбу о том как работают современные шахматные программы, основные приоритеты, главные эвристики поиска и оценки, цели (исчерпывающего) счета, существенные действия перед тем как определить следующий ход и т.д. Хотелось бы почувствовать балланс и компромисы множества факторов, которые взвешивает компьютер во время игры.

    Заранее спасибо большое и дальнейших успехов Стрелке :)
  8. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    382
    Симпатии:
    357
    Репутация:
    10
    Оффлайн
    Не очень понимаю, о чем идет речь? О том, как работают современные шахматные программы написано много, это можно найти в сети. Даже самые простые описания дают очень ясное представление об этом, например:
    www.ocrai.narod.ru/chessalg.html

    Если по существу некоторых вопросов, то коротко:
    1. Шахматные программы не умеют составлять план игры и ставить перед собой цели. Они просто перебирают варианты на какую-то доступную (по времени) глубину, и из этих вариантов выбирают лучший.
    2. Мне не известны программы, которые способны отсекать какие-то ходы, не делая их. Рассматриваются все варианты, даже заведомо “бредовые”. Другое дело, что одни (“хорошие”) варианты считаются на большую глубину, а какие-то (“плохие”) – на меньшую. В этом и состоят “эвристики поиска” (очень грубо).
    3. Выбор между хорошим и плохим вариантом определяется оценкой в КОНЦЕ каждого варианта. Эта оценка чисто “статическая”, другими словами в ней обычно не учитываются динамические факторы (размены, угрозы, превращения и т.д.) – для этого дополнительно считаются форсированные варианты, чтобы посмотреть, можно ли эти угрозы реализовать.
    4. Статическая оценка позиций состоит из набора факторов, и каждый фактор имеет свой вес. Как правильно подбирать эти веса – никто не знает. Это из области искусства или лучше сказать – алхимии.
    5. Не всегда добавление нового фактора в оценку улучшает качество игры программы. Это зависит от двух вещей:
    - Насколько удачно мы подберем вес этого нового фактора, причем в сочетании с другими (уже имеющимися) факторами. Такое добавление может “испортить” действие других факторов.
    - Новый фактор нужно вычислять, а это может затормозить работу программы. Программа может лучше “понимать” позиции, но будет считать на меньшую глубину, и следовательно хуже играть. Где баланс между скоростью и “пониманием” – тоже никто не знает. Хотя история развития компьютерных шахмат говорит скорее о том, что быстрые программы с более простой оценочной функцией чаще оказывались посильнее своих более медленных конкурентов. Примерно как Каспаров против Карпова.
  9. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Хм... а я знаю уйму таких программ.
    И кучу таких отсечений - это как минимум
    1. Сам принцип альфа-беты.
    2. Отсечения по оценке в Хеше.
    3. Остечения по матовой оценке. (дистанция до мата)
    4. Хистори прунинг. (та-же Тога режет ходы по истории на малой глубине)
    5. Футилити, Разоринг и т.д. (схемы когда с плохой оценкой расмматриваем только агрессивные ходы).

    При большом Depth особого смысла сразу резать нет, поэтому обычно в случае плохой статистики (LMR), либо плохой оценки (Ребель редукшн, MultiCut), либо отсутсвии угроз (Null-Move) просто сокращают глубину перебора, а не режут. Хотя Null-Move без верификации это отсечение ходов без исполнения, и производится на любой глубине...
  10. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    382
    Симпатии:
    357
    Репутация:
    10
    Оффлайн
    Речь немного не об этом. Не о том, можем ли мы что-то отсекать и сокращать В ГЛУБИНЕ дерева. В глубине, конечно, можем. Там, понятное дело, работает много таких эвристик.

    Речь о том, можем ли мы В КОРНЕ дерева сразу отбросить какие-то ходы, не делая их. Просто посмотрели на позицию, оценили ее, и сразу определили два-три хода-кандидата, которые затем и перебираем.
    Таких программ я не знаю.
  11. NS Нефёдов Сергей

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

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    382
    Симпатии:
    357
    Репутация:
    10
    Оффлайн
    Совершенно верно.
    Я просто хотел дать человеку (Хайдук его звать) "внятный и достаточно исчерпывающий ответ на просьбу о том как работают современные шахматные программы".
    Надеюсь, удовлетворил.
  13. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    8
    Репутация:
    0
    Оффлайн
    Спасибо, Юрий, можете быть уверенным :) , что удовлетворили. Наверное у меня будут вопросы, но хочу основательно подготовиться, чтобы не вызывать улыбок или хуже того... :)
  14. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    8
    Репутация:
    0
    Оффлайн
    Почему-то мне показалось, что у Васика сам он числится программистом, а международный мастер (IM) Ларри Кауфман и есть шахматный эксперт в команде :rolleyes: Васик как-будто говорил, что щас Ларри берёт на себя существенные функции по улучшению Рыбки...
  15. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Ларри Кауфман разработал систему оценки материального дисбаланса (материальной составляющей позиции) - то есть он математик.
    И Васику хватает и своей шахматной квалификации - я уже говорил что он также IM...
  16. NS Нефёдов Сергей

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

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    382
    Симпатии:
    357
    Репутация:
    10
    Оффлайн
    Кто их знает, как Васик и Ларри делят работу между собой? Сам Ларри говорит, что он занимается оценочной функцией, а Васик - алгоритмами поиска. Функция оценки для Рыбки 3 уже готова, и Ларри отдыхает. Все теперь ждут, когда Васик добьет поиск.

    А вообще, там у них много народу работает.
  18. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    8
    Репутация:
    0
    Оффлайн
    А может резать кажущиеся слабыми ходы в корне опасно, ибо можно необратимо зевнуть что-нибудь. Их подвергают мало-мальской проверке, чтобы убедиться в отсутствии форсированных цепей, а поиск быстро прекращается, ибо уже первые оценки указывают на действительную слабость и малоперспективность получающихся позиций. В глубине как-бы можно отсекать не проверяя, ибо это пока не фатально, обратимо: игра еще не дошла до этих позиций, а если дойдёт, будет еще возможность перепроверить на более детальном уровне то, что отсекли, закрывая глаза :)
  19. NS Нефёдов Сергей

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

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    8
    Репутация:
    0
    Оффлайн
    Статическая оценка (ОФ) в конце счета - это должно быть то место, где шахматные знания и понимание программой позиции сказываются. Хотя мне кажется натуральным, что некоторые вроде мини-ОФ могут использоваться и во время поиска для сокращения того и сосредоточия на наиболее перспективные ветки дальнейшего поиска. По-видимому, это и есть эвристики поиска (счета). Представляется удивительным, что укороченные (для быстродействия) эвристики могут отобрать самые лучшие ходы (сколько, 2-3?), которые обычно совпадают с выбором гроссмейстеров. Или число перспективных ходов после поиска все-же немалое и ОФ приходится отсеивать самый-самый лучший?
  21. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Чтоб отобрать 2-3 лучших хода так-же не надо шахматных знаний.
    В шахматных программах сортировка идет по
    1. Ход из Хеша.
    2. Хорошие взятия по SEE
    3. Киллиры (их иногда делят на матовые и простые)
    4. Остальные ходы отсортированные по истории (статистика того что ход был опровергающим).

    Обычная схема LMR - не сокращается только на первых трех ходах, на остальных (если ход не тактический) идет сокращение на 1-2 полухода.


    Эвристики укорочены не для быстродействия, а потому что более мощных нет, и не факт что они нужны. Человек "хорошие" в данной позиции ходы так-же определяет по статистике.
    Но LMR это не основное отсечение. Самый мощный метод отсечений это Null-Move.
  22. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    8
    Репутация:
    0
    Оффлайн
    Несмотря на Ваш оптимизм, ув. NS, я усматриваю тут некоторое противоречие, значение которого, может быть, преувеличиваю :( . Ясно, что ОФ заключает в себе самое серьезное шахматное знание, которому можно научить компов. Но если я правильно понял Юрия, ОФ запускается после того как поиск окончен и у нас несколько (немного?) ходов-кандидатов. Наверное с этими немногими корневыми ходами-кандидатами ассоциировано довольно большое число конечных поисковых позиции, которые и призвана расставить по местам ОФ. Я понимаю, что если ОФ сложная, рассудить многие конечные позиции отнимает некоторое время и поэтому чересчур сложные ОФ не оплачиваются, ибо занимают время и глубину у поиска. Вдобавок к этому чем сложнее, тем ненадежнее ОФ и труднее становится отладить совместно все факторы ОФ и их веса. Что меня смущает, так это то, что вся мощь ОФ уходит, видимо, на оценку по существу малого числа корневых ходов (хотя число иных конечных позиций может быть велико). Остальные корневые ходы отсекаются поиском, которому в принципе тоже не помешала бы хорошая ОФ ;) для промежуточных позиций, но на которую, очевидно, не хватило бы времени во время поиска.

    Я понимаю, что лучше проще да глубже и быстрее, чтобы использовать огромные преимущества компов в незамысловатой производительности. Но тогда должны встречаться позиции, которых компы не "понимают" и выбирают очевидно (для гроссмейстеров :p ) не лучших 1-2-3 ходов, которые потом компенсируют (насколько удастся) сильнейшими выборами в уже разных по характеру следующих позициях :rolleyes:
  23. WildCat Коршунов Игорь

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

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    8
    Репутация:
    0
    Оффлайн
    А почему, неужели никаких надежд не видно? ;) Давайте, присоединяйтесь к Юрию и NS, может асилите меня :D
  25. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Нет уж, медицина, в данном случае, бессильна.
  26. дуп Учаcтник

    • Участник
    Рег.:
    11.09.2007
    Сообщения:
    113
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Великий Новгород
    Оффлайн
    Наверное не очень уместно в этой ветке, но уж до кучи :
    Написал бы кто - нибудь из крутых шахм.прогеров нормальную книгу. Например на этом форуме тех, кто смог бы это сделать, я думаю, как минимум человек 5. Дело конечно очень сложное и денег не светит никаких, но зато сколько пользы бы было. Книга Е.Корнилова - единственная на русском языке и я думаю очень полезная, но она выпущена уже давно и пора бы уже появиться чему-нибудь поновее/получше.
  27. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Для нас исходники Стрелки - это хорошая книга. :cool:
  28. дуп Учаcтник

    • Участник
    Рег.:
    11.09.2007
    Сообщения:
    113
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Великий Новгород
    Оффлайн
    А для начинающих ?
  29. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
  30. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    8
    Репутация:
    0
    Оффлайн
    Ну, это еще посмотрим кому что ;) Кустарям море до колени и обычно не видят леса из-зад деревьев, а вот профессионалы "алхимию" чувствуют и уважают... :( Недаром же Антони Коззи набросился недавно на Васика из-за якобы нехватки специфического шахматного знания у Рыбки, но ввиду деликатности и чувствительности ОФ к "улучшениям", о чём упомянул Юрий, вопрос далеко не простой :rolleyes:
  31. Renegat23 Заслуженный

    • Заслуженный
    Рег.:
    08.02.2007
    Сообщения:
    1.823
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
  32. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    382
    Симпатии:
    357
    Репутация:
    10
    Оффлайн
    Я бы не стал говорить, что это "новая Стрелка". Это всего лишь эксперимент по пересадке органов. Я даже и выкладывать ее не собирался.
  33. Chemer Максим

    • Участник
    Рег.:
    14.09.2006
    Сообщения:
    1.674
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Запорожье
    Оффлайн
    машинный перевод гуглом рулид безбожно - валяюсь пацталом - пытаюсь успокоиться и вылезти оттудого :lol:
  34. Алексей Н. Алексей

    • Участник
    Рег.:
    22.01.2008
    Сообщения:
    160
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Столица Сибири
    Оффлайн
    Код:
    Я лично имели пожизненный роман с наукой
    и техники.
    :):D
  35. Vertu Учаcтник

    • Участник
    Рег.:
    22.12.2006
    Сообщения:
    932
    Симпатии:
    14
    Репутация:
    0
    Оффлайн
    А правда, что Энтони Коззи написал какую-то софтину для декомпиляции, и назвал её Laika?
    см. http://www.diggingfordatastructures.com/

    зы домен на нем зареген

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