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

Предварительные результаты - добавление даже небольшой рандомности к оценке (аналог 0.01 пешки) резко бьет по эффективности PVSа...

 

В условиях нестабильного перебора вместо такого кода
Score1:=-search(-a-1,-a);
if Score1>a
then
Score:=-search(-b,-a)
else Score:=Score1;

...
Лучше делать такой
Score1:=-search(-a-1,-a);
if (Score1>a)and(Score<b)
then
Score:=-search(-b,-Score1)
else Score:=Score1;

 

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

 

Depth= 1 test= 19998
PVS Avg= -0.0 Min= -4.7
SNS Avg= -0.0 Min= -4.7

Depth= 2 test= 19983
PVS Avg= -0.1 Min= -21.3
SNS Avg= -0.1 Min= -4.0

Depth= 3 test= 19845
PVS Avg= 0.1 Min= 4.1
SNS Avg= 0.0 Min= -18.8

Depth= 4 test= 18894
PVS Avg= 0.7 Min= -6.0
SNS Avg= 0.3 Min= -5.4

Depth= 5 test= 13294
PVS Avg= 3.2 Min= 6.3
SNS Avg= 3.6 Min= -2.7

Depth= 6 test= 3807
PVS Avg= 8.8 Min= -0.2
SNS Avg= 8.9 Min= 33.8

Depth= 7 test= 503
PVS Avg= 16.1 Min= -10.6
SNS Avg= 21.3 Min= 1.1

Depth= 8 test= 61
PVS Avg= 21.3 Min= -47.6
SNS Avg= 4.2 Min= -6.3

Это результаты с нестабильностью перебора, с хешем и с предварительной упорядоченностью.
и PVS и SNS - защищенная от нестабильности схема.

 

Avg - Это разница между средней силой метода и средней силой Альфа-Беты.
Min - Это разница между наихудшим случаем метода и наихудшим случаем Альфа-Беты (Эти наихудшие случаи случаются на разных позициях при разных методах)
Avg<Min говорит о хорошей стабильности метода, Avg>Min - о плохой стабильности. (всё в сравнении с альфа-бетой)

Сила в реальной партии зависит от Avg.

 

Такой случай происходит например когда - при альфа-бете 100 позиций сила 1000, а на одной 900.
А при моем методе на 100 позициях сила та-же 1000, а на одной отдельной 950.
При этом при моем методе будет avg=0.5, min=50

 

Насчет узкого окна. Предварительные результаты - узкое окно ни моему методу ни PVSу практически ничего не дает. Осталось оттестировать прибавку от узкого окна в Альфа-бете.

 

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

 

NS я у себя пробовал вариант АБ + узкое окно, но в релизе убрал, хотя перебор заметно сокращался на многих позициях. но вот в некоторых позах он "зарывался", видимо повторные переборы часто вызывались.

 

Пока я получаю предварительные результаты. У меня берется окно +-Дельта от реальной оценки, где Дельта на копейку больше максимального разброса от рандомности (которой я эмулирую нестабильность перебора), поэтому повторных переборов нет.

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

 

* Сводное тестирование.

В условиях нестабильности перебора:

Код:

 ————————————————— 
Depth =  4   test=   40313

[-inf, +inf]
A-B Avg=   0.0 Min=   0.0
PVS Avg=   0.5 Min= -24.0
SNS Avg=   0.4 Min=   5.6

[Eval-Delta, Eval+Delta]
A-B Avg=   0.0 Min=  -1.2
PVS Avg=   0.4 Min=   4.8
SNS Avg=   0.4 Min=  -0.1
 ————————————————— 
Depth =  5   test=    5499

[-inf, +inf]
A-B Avg=   0.0 Min=   0.0
PVS Avg=   2.8 Min=  -9.7
SNS Avg=   3.7 Min=   8.2

[Eval-Delta, Eval+Delta]
A-B Avg=   2.2 Min=  -7.0
PVS Avg=   3.2 Min=   3.7
SNS Avg=   3.3 Min=   6.9
 ————————————————— 
Depth =  6   test=     655

[-inf, +inf]
A-B Avg=   0.0 Min=   0.0
PVS Avg=  11.4 Min= -18.1
SNS Avg=  11.6 Min= -12.0

[Eval-Delta, Eval+Delta]
A-B Avg=   8.3 Min=   9.9
PVS Avg=  11.5 Min= -37.3
SNS Avg=  12.8 Min=  -2.2
 ————————————————— 
Depth =  7   test=     627

[-inf, +inf]
A-B Avg=   0.0 Min=   0.0
PVS Avg=  15.9 Min= -24.8
SNS Avg=  22.9 Min=   4.8

[Eval-Delta, Eval+Delta]
A-B Avg=  12.3 Min=  10.4
PVS Avg=  15.8 Min=   2.6
SNS Avg=  25.1 Min=   6.0
 —————————————————

При стабильном переборе:

Код:

Depth =  4   test=   31654

[-inf, +inf]
A-B Avg=   0.0 Min=   0.0
PVS Avg=   0.6 Min=   0.3
SNS Avg=   0.6 Min=   0.3

[Eval-Delta, Eval+Delta]
A-B Avg=   0.0 Min=   0.0
PVS Avg=   0.6 Min=   0.3
SNS Avg=   0.6 Min=   0.3
 ————————————————— 
Depth =  5   test=    5393

[-inf, +inf]
A-B Avg=   0.0 Min=   0.0
PVS Avg=   5.0 Min=  14.4
SNS Avg=   5.0 Min=  14.4

[Eval-Delta, Eval+Delta]
A-B Avg=   3.5 Min=  12.2
PVS Avg=   5.1 Min=  14.4
SNS Avg=   5.1 Min=  14.4
 ————————————————— 
Depth =  6   test=     683

[-inf, +inf]
A-B Avg=   0.0 Min=   0.0
PVS Avg=  16.8 Min=  15.4
SNS Avg=  16.6 Min=  15.4

[Eval-Delta, Eval+Delta]
A-B Avg=   6.1 Min=   6.4
PVS Avg=  16.8 Min=  15.4
SNS Avg=  16.7 Min=  15.4
 ————————————————— 
Depth =  7   test=      80

[-inf, +inf]
A-B Avg=   0.0 Min=   0.0
PVS Avg=  41.6 Min=  37.0
SNS Avg=  41.5 Min=  37.0

[Eval-Delta, Eval+Delta]
A-B Avg=  31.1 Min=  23.4
PVS Avg=  41.7 Min=  37.0
SNS Avg=  41.5 Min=  37.0
 ————————————————— 
Depth =  8   test=      109

[-inf, +inf]
A-B Avg=   0.0 Min=   0.0
PVS Avg=  46.0 Min=  38.0
SNS Avg=  45.8 Min=  37.9

[Eval-Delta, Eval+Delta]
A-B Avg=  33.2 Min=  23.2
PVS Avg=  46.1 Min=  38.0
SNS Avg=  46.0 Min=  37.9
 —————————————————

Защиты от нестабильности в нулевом окне действительно ничего не дают (так-же как и возвращение оценки вне окна [a,b])

 

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

Может нужно его сочетать с окном в корне?

Depth = 7 test= 627

[-inf, +inf]
A-B Avg= 0.0 Min= 0.0
PVS Avg= 15.9 Min= -24.8
SNS Avg= 22.9 Min= 4.8

[Eval-Delta, Eval+Delta]
A-B Avg= 12.3 Min= 10.4
PVS Avg= 15.8 Min= 2.6
SNS Avg= 25.1 Min= 6.0


Сейчас попробую запустить тест на глубину 8 в условиях нестабильности перебора, посмотрю что получится (Как раз на этой глубине у меня Альфа-Бета с узким окном в корне начинала обгонять нулевые окна без узкого окна в корне)

 

Самое главное удалось отследить полохое поведение PVS-а.


И если нам не нужно отслеживать PV ветви (все узлы равноценны), то все дополнительные пустые окна в PVS ни в одном тесте ничего особенного не дают, а в условиях небольшой нестабильности оценки начинают мешать. Причем падение на 10 пунктов Эло на глубине 7, при 20 возможных ходах в каждой позиции - это уже достаточно много.

 

* Добавлю в тестирование mtd(f), посмотрю как он себя ведет.

 

Предварительныо расчитанные (на бумаге) Цифры возможного роста дерева на mtd(f)
Бренчинг-фактор=3, число возможных ходов в корне=40.
Время расчета на эту глубину (при Альфа-бете) 1
Тогда время получения точной оценки на первом ходе 1/3
Время опровержения всех ходов по альфе 2/3
Время опровержения одного хода по бете (при росте оценки) 2/9


При чистом Mtd(f) при падении оценки, допустим 150 проходов - рост дерева в 100 раз (при этом лучший ход не поменяется до самого конца перебора)

При росте оценки, так-же 150 проходов - рост дерева в 33 раза.

То есть например в случае, когда первый ход выигрывает Ладью (то есть получаем оценку +5), но на самом деле на некоторой глубине мы при этом ходе получаем мат, при этом остальные ходы дают оценку 0.

Мы при чистом mtd(f) этот мат практически гарантированно получим...

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

 

Ничего не понимаю. 2+1 ведь тысяча партий была сыграна.

 

Теперь понял

 

какие такие преборные алгоритмы?!

Тот путь, которым двигался М. М. Ботвинник, на сегодняшний день не имеет последователей. Создание шахматных программ пошло по пути полного перебора. Тот успех, которого добиваются нынешние программы ? результат фантастического быстродействия техники и к искусственному интеллекту имеет весьма отдаленное отношение. И хотя 5-кратный чемпион мира был в полушаге от создания подлинного искусственного интеллекта, ему не хватило как раз производительной техники и самой жизни для осуществления своей заветной мечты.
http://64.ru/?/ru/magazine/year=2007&no=1&part=386&article=1491

 

Чего ему не хватило? Пары столетий, техники в миллиард раз быстрее существующей, и хотя-бы одного программиста в команду?
И желательно было заменить руководителя проекта. Например с Ботвинника на Адельсона-Вельского.

Насчет полушага - у кого-то серьезные проблемы с измерением расстояний.

А насчет полного перебора - то что тогда называли Брут-Форс, автору статьи надо-бы хоть немного попытаться разобраться в современных переборных алгоритмах (О чем кстати Ботвиннику намекали больше 20-лет назад)