алгоритм SEE

в своей шахматной программе помимо обычной сортировки MVV/LVA
решил сделать SEE - шную ... вот только алгоритм ее не до конца понимаю ...

вроде как составляем массив атакованных полей для каждой из сторон и после каждого
хода обновляем... чуствую что не совсем так :/
может кто - нибудь мне объяснить поподробнее ...
исходничок ф-ции может у кого ...

Google please не предлагать
там я уже был

 

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

 

Хм... И уже не исправить Описка зафиксирована в истории

 

Так в Тоге/Фрукте же есть SEE!?!

 

http://www.uciengines.de/UCI-Engines/TogaII/togaii.html

 

это же MVV/LVA

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

 

Нет, это как раз SEE
MVV/LVA это метод сортировки ходов (Съесть побольше, фигурой поменьше )
А SEE - Это расчет результатов размена через формирование списков Боев (за обе стороны)
Чтоб узнать что пешка Атакована/Защищена - формируются списки Боев.
Да, перед генерацией взятий формируются списки Боев за обе стороны, а дальше возможны разные варианты
У WildCat есть отсечения в ФВ по SEE - ему возможно нужен более молее мощный вариант.
Если только сортировка (особенно в ФВ критично время потраченное на сортировку ходов) - то возможно возможен более урезанный вариант SEE.

 

А что такой ФВ вернет? Так возвращает статичную оценку (после разменов), а если мы его убираем, что возвращает? Текущую оценку + Результат SEE?

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

 

А если попробовать стандартный SEE вместо ФВ - То очень большое падение силы происходит?

 

скажите , что по вашему опыту дает программе наибольший прирост силы :
null move
SEE
transposition tables
улучшения альфа - беты
или может что- то еще?(ФВ и following PV уже добавил)

 

0. ФВ (без него программа вообще играть не может)
1. Хеш лучших (опровергающих) ходов + IID+ Киллеры + Сортировки (очень много)
2. Null Move (300 пунктов)
3. Хеш перекрестных позиций (оценки) - не замерял сколько. Сказывается в эндшпиле, и при большой глубине перебора, чтоб был толк - смотри сначала пункт 1.
4. LMR (до 100 пунктов, или немного больше)

SEE нужно в последнюю очередь. Crafty спокойно обходился без него.
Улучшения Альфа-Беты... Имеется в виду негаскаут? Не факт что он вообще лучше.

 

Еще продления на шахах +100 пунктов.
Оценка проходных (и вообще пешечной структуры)
Оценка защищенности короля

 

что такое IID - честоно говоря впервые услышал ?

по киллерам - я так понимаю это то же follow_pv только берем не 1 а несколько лучших ходов :
если так , то сколько их следет хапоминать из вашей практики?

хеш перекрестных позиций - те ли это позиции , где value >= beta ?

LMR - где - то видел , но забыл , что это

http://fuckelengine.mylivepage.ru/file/263 - моя программа , если кто интересуется

 

IID - Это запуск перебора с меньшей глубиной для определения лучшего хода (улучшаем упорядоченность ходов)
Киллеры - Это запоминием опровергающие ходы (в похожих позициях одни и те-же ходы являются опровергающими)
Хеш перекрестных позиций - независимо от оценки - сохраняем оценку в хеше (чтоб если позиция встретится в другом месте перебора (с другим порядком ходов) - не запускать перебор заново)
LMR - это метод сокращения глубины перебора на ходах, которые считаем достаточно плохими (точнее НЕ СОКРАЩАЕМ только на тактических, и ходах которые считаем хорошими)

 

IID наверное у меня уже есть тогда : я перебираю ходы от 1 до max_depth
это наз-ся Iterative Deepening
киллеры - это когда value >= beta ?

как определить , что ход действительно плохой ?
я так понимаю эту проблему так до конца и не решили

 

Что значит не решили? 100 пунктов прибавляет? Значит решили.

Да, Это опровергающие ходы. (не путай с хешем опровергающих/лучших ходов)

Так обычно перебирают только в корне дерева.
IID в таком режиме работает плохо.

 

правильно я понял :
в IID в каждом вызове ф-ции Search, если не в корне дерева, я считаю на depth - 1 или depth - 2 (кстати сколько? ...1 или 2 ) а затем уже снова считаю , но уже упорядоченные ходы ...
получается я считаю дважды ... правда упорядочение я думаю больше принесет пользы ,чем перебор на меньшую глубину

 

Перебираем взятия на входе в ФВ, оцениваем по SEE, при достижении (Бета-Статичная оценка на входе в ФВ) прерываем перебор, либо если гарантированно не превышаем достигнутую оценку по SEE прерываем расчет SEE для хода. Ну и возвращаем статичную оценку + Максимальную оценку по SEE.

 

У него бывает, что при глубине в 1 полуход дерево разрастается до 10000 Nodes.
Не похоже на быстрый ФВ... Похоже что он наоборот жуткое количество шахов смотрит в ФВ.

 

1. IID вызывается только если нет лучшего хода в Хеше.
2. Обычная схема - IID используется только в PV ветвях. (У некоторых, например у меня - не только в PV, так как IID еще вдобавок может улучшать работу LMR)
3. IID обычно вызывают в два прохода - сначала с окном (альфа,Бета), и если нет опровергающего хода, тогда уже (-inf,beta). Можно сделать три прохода (сначала с нулевым окном = beta)
4. Обычно для IID из Depth вычитают не меньше двух. Только если используют при Depth=2 тогда вычитают один полуход.

В Тоге для IID NewDepth=Depth div 2
У меня расчет глубины (и вообще применение IID) Зависит от типа прохода (размера окна для IID), и типа ветви (PV/ не PV)

 

2 NS - спасибо за ликбез

 

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

 

Скажите , какова очередность применения эвристик ( в каком порядке вызывать )
1. transpos. table
2. NULL MOVE
3. KILLER MOVES
4. PV move (лучший при предедущем поиске на глубину depth-1 в Iterative Deepening)
5. все остальные отсортированные по взятиям

правильно я написал очередность?

просто 1-2-3 вызывают у меня
подозрения на возможный другой их порядок

 

3. KILLER MOVES - используется для сортировки, так что очередность тут не причем

 

т.е. Киллеры - когда я не в PV , а PV move - когда в PV - правильно?

ну а TRANSP. TABLE vs NULL MOVE так и остаются 1 и 2 ?

 

Киллеры всегда
Примерный порядок в сортировке.
1. Ход из хеша, при его отсутствии IID, при его отсутствии - пропускаем этот пункт.
2. Отсортированные взятия.
3. Киллеры.

 

Порядок.
1. Проверяем повторение позиции, если повторилась - то возвращаем ничейную оценку.
2. Смотрим оценку в Хеше, если она удовлетворяет необходимым условиям, то возвращаем её.
3. Если в позиции применим Null Move, то применяем.
4. Если применили Null Nove, и используется Верификация - то используем.
5. Если нет хода в хеше, и применяется IID, то применяем.
6. Сортируем ходы, и начинаем перебор.