Наглядное представление NullMove с альфа-бета

Вопрос экспертам в написании шахматных движков - как NullMove может понизить бранчинг-фактор
с 6 (среднее для чистых альфа-бета) до 2 ??

Попытался сделать наиболее наглядную и упрощенную диаграмму с альфа-бета отсечениями.
Не стоит пугаться большого количества разных циферок на ней, на самом деле если внимательно
посмотреть, то все будет понятно. И эта диаграмма позволяет наиболее простым способом показать,
как работают альфа-бета отсечения. Есть позиция A, корень дерева, которую нам нужно проанализировать
в глубину на 3 полухода, и дать ей оценку. И выбрать лучший ход (как впоследствии окажется,
лучший здесь - ход AB). Красные стрелочки с красными циферками показывают порядок обхода дерева.
Для простоты возьмем, что в каждом узле у нас 2 возможных хода, и если бы здесь был полный перебор,
то мы получили бы бранчинг-фактор равный 2. Из 7 узлов мы спускаемся в глубину по 14 ребрам. Здесь
порядок обхода дерева самый оптимальный, есть 2 отсечения - EM и затем CG, с поддеревом. Почему
здесь сработали отсечения, напишу ниже, а пока видим, что мы вместо 14 опусканий, совершили только 10.
Значит из-за альфа-бета отсечений, бранчинг фактор у нас уменьшился с 2, примерно до 1,4.

Белые узлы - позиции с ходом белых, в них белые выбирают ход с максимальной оценкой, черные узлы -
с ходом черных, в них черные выбирают ход с минимальной оценкой. Листья - самые нижние узлы имеют
статическую оценку, глубже уже не опускаемся. Оценки узлов слева показаны при спускании
в узел сверху (и еще точно неизвестные), снизу - промежуточные, при попадании снизу 1-й раз, и
справа - уже точные, которые подаются на верхний узел. Итак, мы отправляемся из узла A в B, затем
в D, все еще имеем для D неопределенную оценку, точнее, см. слева - она может быть в самом широком
диапазоне [-1000 1000], условимся что это предельные значения. После опускания DH и поднятия наверх,
оценка узла D уже может быть в диапазоне [0,25 1000], т.к. в D - ход белых они могут выбрать уже ивестную
нам 0,25, либо если найдет больше - еще большую. Т.е. уже оценки для D меньше 0,25 быть не может.
После опускания-поднятия DK, видим что белые еще смогли улучшить оценку до 0,30 и точная оценка
узла D стала 0,30, это значение принимает узел вверху B. Но там ход черных, и черные выбирают
ход с наименьшей оценкой, потому там диапазон возможных оценок стал вместо бывших [-1000 1000]
[-1000 0,30]. После анализа BE эта 0,30 может быть только уменьшена. [-1000 0,30] передается и в E,
а далее после анализа EL мы видим, что белые могут получить 0,50. Это выходит из возможного диапазона
[-1000 0,30], т.е. понятно что черные не допустят ход BE, потому что ход левее принесет им 0,30,
а ход BE уже хуже. Потому мы можем не анализировать ветку EM, неважно что там, окончательная
оценка E >0,50, но в допустимый диапазон эта оценка не попадает. Белые могут получить >0,50
а черные могут не допустить этого и получить <0,30 не выбирая выше этот ход.

Так, узел B получает точную оценку 0,30, черные уменьшить ее уже не могут. Диапазон оценок узла
A сузился до [0,30 1000], белые уже не выберут меньше 0,30, а повышать могут вплоть до 1000.
Теперь спускаемся по линии AC. Аналогично BE, в ветке AC передается допустимый диапазон [0,30 1000].
Также, в CF. После анализа узла F, белые могут только увеличивать верхнее значение 0,30 вплоть до 1000,
но этого не происходит. Поскольку 1000 - предельное значение, приходится считать FN и FP.
А вот в узле C, черные наоборот, уменьшают значение нарисованное снизу (1000), и они не могут уменьшить
его чтобы оно стало <0,30. Точнее, если это происходит, то получается такое же противоречие, как в узле
E. С одной стороны, пришли данные что CF даст оценку 0,10, но тогда белые не выберут ход AC, ведь
по ветке AB у них 0,30 - а белые выбирают максимальное. Значит Ветку CG и все поддерево можно уже не
анализировать и отсечь. В узел A возвращается значение 0,10, но узел A остается с конечной оценкой 0,30.

Это на мой взгляд, самое простое и наглядное объяснение принципа альфа-бета отсечений.

Теперь насчет NullMove. Хотелось бы наиболее наглядное представление, как он понижает бранчинг-фактор,
причем настолько существенно (с 6 до 2 !!) и при этом результаты эквивалентны полному обходу дерева
с альфа-бета отсечениями. Давайте понизим его в моем простом примере, с 1,6 до более низких значений?

Для этого немного усложним пример. Будем перебирать на глубину 4 полухода. NullMove не может работать
на конечных листях, и предпоследних (смысл его в том чтобы сделать какой то стороной 2 хода подряд
и убедиться что при этом оценка все равно хуже). Также нет смысла его использовать в корне - там
по любому мы проверяем все ходы.

Рассмотрим картинку


Предположим, мы уже проверили ход AB, и его углубления, пришли к выводу, что линия ABDKJ - ЛУЧШАЯ.
При обычном переборе с альфа-бета отсечениями мы бы отсекли все что зачеркнуто жирными красными линиями,
Имеем 15 узлов в дереве, не считая листьев, 30 веток дали бы бренчинг-фактор 2, а у нас 18 веток,
и бренчинг-фактор равен 1,6.

Осипов Юрий пишет

Понятное дело, что уже при получении лучшей линии ABDKJ, в глубине мы не перебирали полностью только
с альфа-бета отсечениями, а использовали NullMove. Иначе мы бы не перебрали на нужную нам глубину 20,
ведь бренчинг-фактор был бы равен 6. Значит, мы занимались "поиском ответвлений" с помощью NullMove,
в глубине, т.е. на узлах K,D,B. Но рассмотрим поиск ответвлений в корневом узле A.

Итак, ход AB уже проанализирован, и получена оценка (в данном примере) +0,30. В этом примере ход
AC - плохой, он хуже чем AB. (реально в шахматах в каждом узле больше вариантов ходов, но у нас для
простоты понимания их 2). Задача - обвалить ветку AC и ниже нулевым ходом, чтобы получился не перебор
только с чистыми альфа-бета отсечениями, а менее трудоемкий перебор.

Значит, мы делаем ход AC, полагая что он плохой. Если сделаем перебор только с альфа-бета мы и убедимся в
этом. Вместо этого в узле C, где ход черных, пропускаем ход черными. Полагаем, что даже с учетом того
что белые ходили 2 раза, и все равно не получили лучше чем ход AB, можно чистый альфа-бета в AC и не считать.

Значит, черные вместо того чтобы делать ходы CF и CG пропускают ход, и попадаем сразу в зеленый узел
O. Но! Дальше приходится проводить уже стандартный перебор с альфа-бета отсечениями (не можем же мы
пропускать ходы черных еще несколько раз). И чего мы добились своим NullMove? Только того что ветка
AC анализируется не на глубину 20, а на глубину 19. Один полуход пропущен. При этом бренчинг-фактор
по прежнему равен 6, и на глубину 19 с таким фактором все равно мы считать не можем.

Обвалить эту ветку, считая не на глубину 20, а на глубину 10? А вдруг там жертва фигуры, комбинация,
которая не видна до глубины 10? Да и какой тогда смысл писать программам что они перебирают на
глубину 20, если абсолютное большинство ходов реально перебирается только на глубину 10, да еще и
с пропущенным ходом (NullMove)?

Потому я и начал эту тему. Или я что-то не до конца понимаю в NullMove...
В таком понимании NullMove никак не может снизить общий бренчинг-фактор всего дерева перебора
с 6 до 2 !

Осипов Юрий пишет

Что значит "считать" только свои ходы? Ну вот, на картинке, попали мы в первый раз в зеленый CO.
Как дальше можно считать только свои ходы? Ходят обе стороны. А сокращение глубины при NullMove, можно
было бы вообще без NullMove проводить, есть такие понятия, как "выборочные углубления" или "выборочные
сокращения". Кстати, там и большая вероятность того что этот вариант будет успешно отброшен.
А с NullMove больше вероятность, что его придется пересчитывать заново.

Напишите кто-нибудь подробно и понятно, как вы с помощью NullMove добиваетесь сокращения бренчинг-фактора
до 2.

Картинки напрямую на странице форума не отображаются?

Это как? NullMove означает что черные пропускают сразу 3 хода? Т.е. 4 подряд хода делают белые?
Как при этом они все равно остаются с плохой оценкой? Я понимаю, если 1 ход черных пропустить. Потому что ход белых до этого был неудачным.

Но сделать подряд 4 хода - это в большинстве случаев уже гарантированная победа.

Вот этого я пока не пойму, как ИМЕННО фактор ветвления сокращается то?? Я нарисовал картинки, там видно что мы добиваемся уменьшения перебора на глубину 1 полуход, но никак не сокращение ветвления в корневом узле. Какие еще секреты применения этого пресловутого нулевого хода?

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

Да и опровержений здесь очень много должно быть. Ну у меня есть возможность делать подряд ходы. Нацелился сначала одной фигурой на пешку, потом второй фигурой... Если надо третьей. Что дальше? Дальше позиция, которая вообще далека от того, что было бы при реальной игре если бы ходили оба соперника. Как получив такие результаты можно обваливать линии с нулевым ходом?