Переборные алгоритмы...

В Анечке верификация происходит меньше чем в пяти процентах узлов.
(то есть не в пяти процентах вызовов LMR, а именно в пяти процентах узлов)

Но у меня PVS, так что окно в LMR в любом случае нулевое.

Наверно нужна еще и стабильность - чем выше вероятность на верификации получить оценку больше Альфы - тем лучше.

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

LMR в общем случае ухудшает тактическую силу
Не надо проверять LMR на наборах тактических тестах - он увеличивает практическую силу игры, и проверять его нужно тестовыми матчами.
PVS - есть теорема, что при идеальном хеше, в условиях стабильного перебора PVS ВСЕГДА просматривает узлов не больше чем Альфа-Бета.

NS "просматривает узлов не больше чем Альфа-Бета" как то размыто хотелось бы видеть - "просматривает узлов меньше чем Альфа-Бета"

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

Нужно смотреть на силу игры вообще, а не только на тактике. Вот Рыбка, говорят, не так сильна в тактике, как например Фритц. Однако-же никто не сомневается в силе игры Рыбки

Это и означает что просматривает узлов меньше. Столько-же просматривает практически только когда ходы идеально отсортированы. Что на практике конечно-же нереально.

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

Сам алгоритм пока не сдавай - он конечно простой, но ни одного упоминания о нем я не слышал, и он не проще Альфа-Беты, Минимакса, PVS и mtd(f)
Можно назвать его двухпроходным упрощением PVS-а.
Я попробую провести мощные тесты, и узнать насколько алгоритм чуствителен к нестабильности перебора, к плохим сортировкам и к нехватке Хеша.

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

То есть я целеноправленно придумывал селективный двухпроходный алгоритм.

Да, я читал статьи на сайте Маркова.

у меня совсем не в ту тему - у меня развитие цепочки PVS/MtD(f) и т.д.
Тоже метод дерева нулевой ширины, но с небольшим отличием от остальных.

По сравнению с Альфа-Бетой:
При mtd(f) при выборе неправильной начальной оценки возможно просто катастрофичное падение Бренчинг-Фактора.
при PVS максимальное значение падение бренчинг-фактора пропорционально глубине перебора.
При моем алгоритме максимальное падение бренчинг-фактора равно двум.

MtD(f) из-за этого практически не применяется.
От PVS начнут отказываться при достаточно большой глубине перебора.
Мой алгоритм безопасен...

Алгоритм является промежуточным между чистой Альфа-Бетой и PVS-ом.

При достаточно хороших сортировках метод однопроходный, и перебор идет по дереву нулевой ширины...

В эту ветку буду выкладывать результаты тестов.
Первый тест - считаем сразу на требуемую глубину, ходы случайно перемешаны, Хеша нет.
Считаем Минимальную силу (результат падения бренчинг-фактора), и среднюю силу.
Сила обратно пропорциональна Логарифму от количества узлов в дереве.
Сравниваю Альфа-Бету, PVS и Новый Алгоритм.
Результаты будут готовы через пару часов.

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

Обе цифры - положительная - значит алгоритм лучше Альфа-Беты, отрицательная - хуже.
SNS - мой алгоритм.

Depth= 1 test= 99932
PVS Avg= -11.6 Min= -39.3
SNS Avg= -11.6 Min= -39.3

Depth= 2 test= 99318
PVS Avg= -15.8 Min= -30.7
SNS Avg= -14.1 Min= -27.4

Depth= 3 test= 93540
PVS Avg= 3.3 Min= -20.4
SNS Avg= 6.5 Min= -13.9

Depth= 4 test= 62585
PVS Avg= 3.0 Min= -14.7
SNS Avg= 6.9 Min= -4.9

Depth= 5 test= 15937
PVS Avg= 10.5 Min= -11.8
SNS Avg= 13.8 Min= -6.5

Depth= 6 test= 2196
PVS Avg= 10.8 Min= -4.5
SNS Avg= 14.3 Min= -1.8

Depth= 7 test= 262
PVS Avg= 13.2 Min= -8.6
SNS Avg= 16.3 Min= -2.7

Depth= 8 test= 36
PVS Avg= 18.0 Min= 4.5
SNS Avg= 20.9 Min= 6.4

Теперь с Хешем - пока только лучший ход.
Понятно что Альфа-Бете Хеш не даст ничего (так как однопроходный алгоритм, считаем сразу на требуемую глубину, и в тесте в разных узлах нет одинаковых позиций)

Предварительные результаты - PVS и новый метод в условиях стабильности перебора, при наличии хеша - практически одинаковы по быстродействию, и дают на моем тесте где-то в 1.5 раза меньшее количество узлов чем Альфа-бета.
При этом мой алгоритм (в отличии от PVS) защищен от нехватки хеша (неидельности) и от нестабильности перебора...

Первый запуск (в корне)
-Search(-b,-a,true)
Если с полным окном, то
а:=-inf;
b:=inf;
третий параметр - Аналог PV.
Истина означает что окно нулевой ширины разрешено.

Code:

Function Search(a,b,RP):Integer;
Var Score:Integer;
Begin
  For i:=1 to kolmove do
   Begin
     make_move(i);
      if (i>1) and (RP) then
         Begin
          Score:=-Search(-a-1,-a,false);
          if (Score>a)and(Score<b) Then Score:=-Search(-b,-a,false); 
         end
      else Score:=-Search(-b,-a,RP);

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

Вот результаты с хешем:

Code:

Depth=  1 test=   10000
PVS Avg= -11.6 Min= -36.0
SNS Avg= -11.6 Min= -36.0

Depth=  2 test=    9994
PVS Avg=  -3.7 Min=  -2.9
SNS Avg=  -3.7 Min=  -2.9

Depth=  3 test=    9938
PVS Avg=  18.4 Min=   4.9
SNS Avg=  18.9 Min=   6.1

Depth=  4 test=    9491
PVS Avg=  21.2 Min=  16.2
SNS Avg=  21.1 Min=  16.0

Depth=  5 test=    6815
PVS Avg=  31.2 Min=  28.7
SNS Avg=  31.0 Min=  28.3

Depth=  6 test=    2014
PVS Avg=  32.3 Min=  15.4
SNS Avg=  31.6 Min=  15.1

Depth=  7 test=     292
PVS Avg=  35.4 Min=  27.8
SNS Avg=  34.5 Min=  27.8

Depth=  8 test=      37
PVS Avg=  33.8 Min=  35.5
SNS Avg=  32.9 Min=  34.8

Depth=  9 test=       5
PVS Avg=  35.9 Min=  25.1
SNS Avg=  35.1 Min=  24.3

Остался самый главный тест - с предварительной сортировкой ходов....

Партий мало - результат в пределах доверительных интервалов.

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

Ну тогда нормально
Окно на коротких контролях помогает...

В лучшем случае - один И цепока позиций до этого конечно узла

Я просто отследил причины падения бренчинг-фактора (в PVS) при резком падении оценки на первом ходе - плюс к появлению новых варинтов, без лучших ходов и оценок в хеше - еще и многократные проходы одного и то-го же узла. В моем алгоритме это устранено.

В тестах без хеша (но со стабильным перебором) он показывает чуть лучший результат.
В случае нестабильного перебора - должен увеличивать отрыв от PVS.

Сейчас выведу статистику по ненулевым окнам в PVS.

Да нет так уж и редко, особенно при большой глубине...
От mtd(f) отказываются по той-же причине - периодическое резкое падение бренчинг-фактора...
Только в mtd(f) всё хуже...

Тесты показывают что эти лишние нулевые окна в PVS вообще ничего не дают - так зачем-же они нужны?
То есть конечно они нужны, но только в одном случае - если мы хотим для каких-то дополнительных целей отследить PV ветвь.

Еще одна странность. С предварительной сортировкой преимущество пустых окон над Альфа-бетой возрастает...

Depth= 1 test= 14999
PVS Avg= 0.0 Min= 0.0
SNS Avg= 0.0 Min= 0.0

Depth= 2 test= 14988
PVS Avg= -0.0 Min= 0.0
SNS Avg= -0.0 Min= 0.0

Depth= 3 test= 14886
PVS Avg= 0.0 Min= 14.2
SNS Avg= 0.0 Min= 14.2

Depth= 4 test= 14184
PVS Avg= 0.8 Min= 19.7
SNS Avg= 0.8 Min= 19.7

Depth= 5 test= 10014
PVS Avg= 4.1 Min= 17.0
SNS Avg= 4.1 Min= 17.0

Depth= 6 test= 2917
PVS Avg= 16.4 Min= 53.3
SNS Avg= 16.3 Min= 53.3

Depth= 7 test= 421
PVS Avg= 42.4 Min= 46.7
SNS Avg= 42.3 Min= 46.6

Depth= 8 test= 54
PVS Avg= 47.2 Min= 44.4
SNS Avg= 47.2 Min= 44.0

Depth= 9 test= 6
PVS Avg= 57.3 Min= 57.6
SNS Avg= 57.3 Min= 57.5


Это результат с хешированием и с предварительными сортировками.


Общий результат -
1. Альфа бета проигрывает при достаточной глубине и PVS и Предложенному методу даже в условиях отсутсвия Хеша. (при стабильном переборе)
2. Сортировка корня не уменьшает отрыв Нулевых окон от Альфа-беты, а наоборот увеличивает.
3. В условиях стабильного перебора и при наличии хеша предложенный метод показывает такие-же результаты как и PVS.
4. В условиях отсутсвия Хеша и стабильном переборе (а при нестабильном переборе отрыв будет еще больше) Предложенный метод начинает опережать PVS.

Придумал как протестировать в условиях абсолютно нестабильного перебора!!!
Сейчас проверю что получится...