Internal Iterative Deepening

в моем оригинальном способе я вытаскивал на вершину не 1 ход ,а все до достижения value >= beta
с присваиванием им приоритета , согласно полученным оценкам - глядишь что-то изобрел
может действительно вытаскивание неск. ходов будет лучше вытаск. одного , как с киллерами?!

 

Сейчас, мысли в порядок приведу

 

if (bestM=0) then // Если нет хода в хеше
Begin
if PV Then // PV ветвь
Begin
if (depth>2) then
Begin
// Вычислим новую глубину
// if depth<4 then newdepth:=depth-2 else
newdepth:=(depth div 2);
oc1:=perebor(a,b,true,false,newdepth);
// Третий параметр признак PV ветви, четвертый - запрет NullMove на входе
if (oc1<=a) Then oc1:=perebor(-inf,b,true,false,newdepth);
end;
end
Else // Не PV ветвь
Begin
if (depth>3) then
Begin
// Вычислим новую глубину
//if depth<4 then newdepth:=depth-3 else
newdepth:=(depth div 3);
oc1:=perebor(a,b,false,false,newdepth);
// Третий параметр признак НЕ PV ветви, четвертый - запрет NullMove на входе
// Запуск происходит с нулевым окном (в случае NegaScout)
if (oc1<=a)and(Depth>5) Then oc1:=perebor(-inf,b,true,false,newdepth);
// Третий параметр признак PV ветви, четвертый - запрет NullMove на входе
// возможно что в этом случае newDepth нужно посчитать по-другому
end;
end;
end;

 

Понятно, что генерация Ходов в рекурсивном вызове IID должна производится ТОЛЬКО один раз.
(например в стеке хранится признак того, что ходы сгенерированы, а если уже сгенерированы - то и отсортированный список ходов - соответственно генерация производится только при последнем рекурсивном вызове IID (с минимальным depth), а вышестоящие уровни рекурсии уже используют отсортированный список ходов, с возможно вытянутыми наверх опровергающими и лучшими ходами)
При этом ходы должны быть отсортированы (тоже один раз), и каждый раз когда оценка>Альфа ( и Оценка>BestValue)
Ход вытягивается наверх, а каждый раз когда оценка хода >=Бета (Таких ходов может быть несколько!!! На каждом рекурсивном вызове это могут быть разные ходы) Ходу дополнительно еще присваивается признак Опровергающего (например для LMR)

 

Как это экономить не имеет смысла, если при такой схеме (Вычитание вместо деления) НА ВСЕХ тестовых позициях получается больше узлов (при расчете на ту-же глубину)
При вычитании Только в PV ветвях - разница не очень велика, а в НЕ PV ветвях - уже достаточно серьезна.

Генерация ходов производится один раз - не для экономии времени на генерации, а для использования информации о сортировке ходов (в IID из-за рекурсивности метода, и возможного ненулевого окна - мы имеем более одного хорошего хода, подлежащего вытаскиванию наверх), и для сбора информации об опровергающих ходах (Для того чтоб в схеме LMR не делать на них сокращение)

 

Для вытаскивания хода наверх - в Search, в основном теле - вот такой код
if oc>a then
begin
a:=oc;
u:=r.hhod;
for k:=i downto 2 do
r.hhod[k]:=r.hhod[k-1];
r.hhod[1]:=u;
if oc>=b then // завершаем перебор, и производим манипуляции с хешем
end;

 

Дело в том, что сортировка по ФВ занимает время. И ход, лучший при сортировке по ФВ - не настолько хорош чем ход лучший при Depth=2 и лучший ход по ФВ - не тоже самое для LMR, что и опровергающий при depth=5,10,15...
И у меня - вообще нет трат времени по сравнению с обычной схемой IID
То есть абсолютно стандартный IID, только лучше усваиваем полученную информацию.

И используем IID не только в PV ветвях, а во всех - только не в PV ветвях используем более гибко - по другом считаем NewDepth, и первый проход при Depth>3, а второй с расширенным окном (в случае если первый проход не дал опровергающего хода) - только при Depth>5.

Я говорю же не о том, занимает ли сам IID время, а о размере полного дерева. Если мы выигрываем в размере - то причем тут траты времени от вызова IID?

Если IID совсем не увеличивает дерево (при холостом запуске) - то не значит ли это что IID нужно использовать еще более Агрессивно?

 

Тем более сравнить вычитание с делением занимает всего пять минут.
Поставили начальную позицию, очистили хеш, и запустили на 2 минуты расчет.

 

Я не знаю методики определения разницы в силе двух версий программы при контроле 2 минуты на ход...
1000 партий? Определяем разницу в 20 пунктов? Всего лишь 320 000 минут времени...
Но я знаю методику определения разницы количества узлов в дереве на 100-1000 тестовых позиций (при заданной глубине, и среднем времени обдумывания 2 минуты на ход)

А насчет разницы эффективности алгоритмов получения оценки для всех узлов, и последующей сортировки, и IID - получение одного лучшего/опровергающего хода, а если повезет, то и нескольких, отсортированных...
Всего лишь глубина Depth-3 Для одного хода... Либо равносильная трата времени при Depth-8 Для всех ходов... Я считаю что один лучший ход с глубиной depth-3 намного важнее, чем сортировка всех, но точность сортировки определяется глубиной depth-8///

 

Суть сортировки при альфаБетте не в том чтоб улучшить упорядоченность ходов (в узлах с окном нулевой ширины и отсутсвии опровергающего хода по Бетте - сортировка не дает ничего - всё равно все ходы будут рассмотренны), а именно в том, чтоб опровергающие ходы если они есть - были рассмотренны в первую очередь... Именно это уменьшает дерево перебора.
IID избирательно ищет именно такие ходы... А один ход будет вытянут. или повезет и два три - неважно.
Если 2-3 то будем считать что нам просто повезло, и используем полученную информацию (в отличии от стандартной схемы, которая эти два-три хода получает, но никак не использует, и оставляет их в конце списка, либо в том месте, где они и находились)

 

Кстати, насчет того что холостой, рекурсивный запуск в любой ветви (есно при остутствии отсечения пустым ходом и хода в Хеше) IID с Depth-3 При времени на ход 2 минуты практически не увеличивает количества узлов в дереве...
Я таких тестов не проводил, НО
Запуск Верификации пустого хода с Depth-5, по сравнению с Depth-7 (при этом есно ВСЕГДА НУЛЕВОЕ ОКНО на верификации) - уже Кардинально увеличивает размер дерева.
При этом такие Тесты проводил не только я!
Весьма странно

 

Всё, понял!!!
Игорь, у тебя ошибка в рассуждениях!!!!

Твой "холостой" запуск IID - на самом деле никакой не холостой!!!

Опровергающие ходы, полученные при помощи IID - используются!!!
Влияние холостого запуска на историю минимально, но этот "холостой" запуск явно влияет на киллеры.
Поэтому вполне возможно, что при более гибком подходе к вычислению newdepth - у тебя при холостом запуске IID будет уменьшение количества узлов в дереве!

 

Все современные методы сортировки ходов не связаны с оценками...
Например
Киллеры - опровергающие ходы (а не ходы с хорошими оценками)
Сортировка по истории (сортировка по истории опровергающих ходов)
SEE - вытягивание вверх перспективных взятий (с большой вероятностью опровергающих)
Ходы из Хеша (опровергающие ходы)
IID (c нулевым окном) чистый поиск одного опровергающего хода - если не нашли, то и не надо, по оценке не сортируем.

Сортируя ходы по оценке ты подменяешь цель. Если нет других методов сортировки, то сортировка всех ходов по оценке, по ФВ, по сокращенной глубине конечно будет работать. а иначе - нет.

Ежели у тебя вытаскивание ходов наверх абсолютно бесплатное (например у меня так сделано в IID - абсолютно не замедляет стандартную схему, и ходы по-максимуму вытягиваются наверх (причем опровергающие при большем depth - будут выше в списке, чем опровергающие при меньшем depth), или в Хеше - у меня хранятся два опровергающих хода отсортированных по глубине на которой они являются опровергающими) - то конечно от такой схемы могут быть только плюсы (по собранной мной статистике, если первый ход из хеша не был опровергающим, в хеше два хода, и в позиции есть хоть один опровергающий ход - он практически в 100% случаев будет именно этим вторым ходом из хеша),
а если у тебя сделана сортировка всех ходов по оценке, либо по оценке полученной запуском ФВ (что по сути одно и тоже, просто получаем более точную оценку) - то такой метод будет конфликтовать с остальными, и только ухудшать эффективность отсечений при Альфа-бете.

 

Опровергающий ход завершает только один из нескольких селективных вызовов IID в цепочке...


допустим хода в хеше нет...
Абсолютно стандартная схема IID newdepth=depth-3
Глубина 20 - в рамках IID - Вызов Search с глубиной 17, затем в любом случае перебор с глубиной 20, найденный (один) ход всего-лишь вытягивается наверх в списке...
17 - Вызов Search с глубиной 14, затем в любом случае перебор с глубиной 17, найденный (один) ход всего-лишь вытягивается наверх в списке...
14 - Вызов Search с глубиной 11, затем в любом случае перебор с глубиной 14, найденный ход всего-лишь вытягивается наверх в списке...

...
В рамках одного вызова IID - рекурсивно запускается 6 вызовов IID с разным Depth
С глубиной 2,5,8,11,14,17... И каждый вернет одинаковый опровергающий ход?
То есть первый-же опровергающий ход, найденный с глубиной 2 - всегда Будет опровергающим (при данном окне)? Независимо от Depth?
...

Второй вызов IID - с окном (-inf,beta) - каждый раз лучший ход будет рассмотрен именно первым, и именно он и будет опровергающим?
....
В том то и дело, что IID Селективный метод, и поэтому он находит даже с нулевым окном - абсолютно не обязательно только один опровергающий ход.

 

Вообще странный спор - я сейчас не могу запустить тесты (снес Делфи), но раннее результаты Тестов приводил.
Второй ход из Хеша (первый так-ой же как и во стальных схемах, второй - это тот ход, который в стандартных схемах стирается первым) - вероятность того что второй ход из хеша опровергающий, если первый ход из Хеша не опровергающий, но в позиции был опровергающий ход - близка к 100% (значительно больше чем вероятность того что поровергающим является лучший ход по SEE, и намного больше чем вероятность того что опровергающим является киллер)
Второй ход по силе (опровергающий с меньшим depth) полученный при помощи IID в таком же случае имеет такую-же вероятность быть опровергающим.

Оба хода (второй по IID,и второй ход в хеше) - мы получаем абсолютно бесплатно по времени...

 

Игорь, а кто тебе сказал что ни у кого нет второго хода в хеше?
Может его нет только в открытых исходниках?
Несколько лет назад я читал, уже не вспомню где - о двухуровневом Хеше (Это в хеш таблице про одному адресу две позиции - и вытесняемая, при записи нового хода выбирается исходя из формальных признаков - например с меньшим depth) Почему такого нет в открытых исходниках?
Даже на простейших, нешахматных тестах - такой Хеш получает намного лучшее заполнение.
Я читал о хранении ВСЕХ опровергающих ходов в хеше - если это позволяет быстродействие, и объемы оперативной памяти.
В шахматах на 1С - как раз ситуация с малым быстродействием и большим объемом памяти. И несмотря на небольшую глубину перебора (ввиду низкого быстродействия) - второй ход в хеше дает уменьшение размеров дерева.

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

И кстати - в открытых исходниках не было хранения больше чем одной оценки в хеше...
Но ведь появилась!!! И никто теперь не отрицает эффективность этого метода.

 

Да, больше...
А метод пустого хода сокращает вообще только 5% ветвей
Но при этом улучшает Бренчинг Фактор с семи до трех

И так-же можно сказать о ненужности сортировки ходов в случае наличия хода в хеше - ведь он и так дает вероятность опровержения больше 90%

 

Угу, а Фрукт/Тога получают Результат
Насчет двухуровнего Хеша - 99.9% что о нем писал Хьят, и применялся он не только в Крейблиц, но и в других программах. И я доверяю словам Хьтта о том что этот метод дает прибавку.
ЗЫ. Я дошел до этого метода сам, когда переходил с бинарных деревьев на страничный механизм, потом прочитал мнение Хьятта об этом методе.

 

В открытых исходниках и нет смысла бороться за 5-15 пунктов Эло, даже если методы дающую такую прибавку пишутся за пол-часа и занимают десять строк кода.
А в сильнейших - даже мучаются с продлением на движении проходной пешки, с откатом продления назад в некоторых случаях - это намного более трудоемко, дает всего 10 пунктов, и этого тоже нет в открытых исходниках.

А если взять пять методов по 10 пунктов, написать их и отладить за сутки - то получим прибавку уже 50 пунктов. Например для WildCat-а это очень существенно. И такие рюшечки могут позволить догнать по силе Смартсинк.