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

Если уж что просить так это чтобы Юрий описал основные алгоритмы и принципы Стрелки. Прокомментировал интересные с его точки зрения моменты.
Вот это действительно было бы интересно!
А то при просмотре исходников Стрелки лично мне становиться грустно
от осознания своей непроходимой тупости.

 

Почему я не хочу делать многопроцессорность (по пунктам):

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

 

Что здесь можно поделать?
Читабельность исходного текста такое качество, которое зависит не только от самого текста, но и от читателя.
Кого только не ругали за плохую читабельность! Тут как-то и Маркову доставалось за это. А я читал его Смарсинк - и ничего. Все очень понятно.

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

 

Код Смарфи не дал никаких идей для улучшения Стрелки?

 

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

 

Смарфи - кладезь мудрости по сравнению со Стрелкой. Идей просто вагон. Но вот уже почти год, а руки все никак не дойдут изучить его основательно.

 

Здравствуйте, Юрий, очень приятно с вами познакомиться На другой ветке, где у меня уже несколько постов до и после места ссылки, компьютерщики не смогли или не захотели , имхо, дать мне внятный и достаточно исчерпывающий ответ на просьбу о том как работают современные шахматные программы, основные приоритеты, главные эвристики поиска и оценки, цели (исчерпывающего) счета, существенные действия перед тем как определить следующий ход и т.д. Хотелось бы почувствовать балланс и компромисы множества факторов, которые взвешивает компьютер во время игры.

Заранее спасибо большое и дальнейших успехов Стрелке

 

Не очень понимаю, о чем идет речь? О том, как работают современные шахматные программы написано много, это можно найти в сети. Даже самые простые описания дают очень ясное представление об этом, например:
www.ocrai.narod.ru/chessalg.html

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

 

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

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

 

Речь немного не об этом. Не о том, можем ли мы что-то отсекать и сокращать В ГЛУБИНЕ дерева. В глубине, конечно, можем. Там, понятное дело, работает много таких эвристик.

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

 

Конечно таких программ нет, и это не имеет никакого смысла... На слабые ходы в корне время на обдумывание тратится очень мало. Зачем-же их тогда резать?

 

Совершенно верно.
Я просто хотел дать человеку (Хайдук его звать) "внятный и достаточно исчерпывающий ответ на просьбу о том как работают современные шахматные программы".
Надеюсь, удовлетворил.

 

Спасибо, Юрий, можете быть уверенным , что удовлетворили. Наверное у меня будут вопросы, но хочу основательно подготовиться, чтобы не вызывать улыбок или хуже того...

 

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

 

Ларри Кауфман разработал систему оценки материального дисбаланса (материальной составляющей позиции) - то есть он математик.
И Васику хватает и своей шахматной квалификации - я уже говорил что он также IM...

 

http://rybkachess.com/index.php?auswahl=Rybka+team
Вот тут указана шахматная квалификация команды Васика.

 

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

А вообще, там у них много народу работает.

 

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

 

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

 

Статическая оценка (ОФ) в конце счета - это должно быть то место, где шахматные знания и понимание программой позиции сказываются. Хотя мне кажется натуральным, что некоторые вроде мини-ОФ могут использоваться и во время поиска для сокращения того и сосредоточия на наиболее перспективные ветки дальнейшего поиска. По-видимому, это и есть эвристики поиска (счета). Представляется удивительным, что укороченные (для быстродействия) эвристики могут отобрать самые лучшие ходы (сколько, 2-3?), которые обычно совпадают с выбором гроссмейстеров. Или число перспективных ходов после поиска все-же немалое и ОФ приходится отсеивать самый-самый лучший?

 

Чтоб отобрать 2-3 лучших хода так-же не надо шахматных знаний.
В шахматных программах сортировка идет по
1. Ход из Хеша.
2. Хорошие взятия по SEE
3. Киллиры (их иногда делят на матовые и простые)
4. Остальные ходы отсортированные по истории (статистика того что ход был опровергающим).

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


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

 

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

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

 

А почему, неужели никаких надежд не видно? Давайте, присоединяйтесь к Юрию и NS, может асилите меня

 

Наверное не очень уместно в этой ветке, но уж до кучи :
Написал бы кто - нибудь из крутых шахм.прогеров нормальную книгу. Например на этом форуме тех, кто смог бы это сделать, я думаю, как минимум человек 5. Дело конечно очень сложное и денег не светит никаких, но зато сколько пользы бы было. Книга Е.Корнилова - единственная на русском языке и я думаю очень полезная, но она выпущена уже давно и пора бы уже появиться чему-нибудь поновее/получше.

 

А для начинающих ?

 

Ну, это еще посмотрим кому что Кустарям море до колени и обычно не видят леса из-зад деревьев, а вот профессионалы "алхимию" чувствуют и уважают... Недаром же Антони Коззи набросился недавно на Васика из-за якобы нехватки специфического шахматного знания у Рыбки, но ввиду деликатности и чувствительности ОФ к "улучшениям", о чём упомянул Юрий, вопрос далеко не простой :rolleyes:

 

Выпущена новая Стрелка 3
http://strelkachess.narod.ru/rybka3.html

Там же можно и скачать ее.

 

Я бы не стал говорить, что это "новая Стрелка". Это всего лишь эксперимент по пересадке органов. Я даже и выкладывать ее не собирался.

 

машинный перевод гуглом рулид безбожно - валяюсь пацталом - пытаюсь успокоиться и вылезти оттудого

 

Код:

Я лично имели пожизненный роман с наукой
и техники.

 

А правда, что Энтони Коззи написал какую-то софтину для декомпиляции, и назвал её Laika?
см. http://www.diggingfordatastructures.com/

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