Что такое Null move?

Ещё вопрос к знатокам.
Корректно ли следующее примерное описание механизма null move?
Оно таково:

Играем белыми.
Имеем такую позицию с очередью хода за белыми:

Имеем её оценку по ОФ - предположим, "+0.15".
Имеем 21 возможный ход белых здесь.

Далее.
Перед тем, как начинать основной перебор, производим перебор по null-move.
То есть, рассматриваем все возможные "двух-ходовки" белых - их примерно 21^2 (на самом деле несколько больше). Получаем позиции (в количестве 21^2) и оцениваем их по ОФ.
Среди прочих первых ходов белых, мы рассмотрим ход 1.Ng1. Т.е. рассмотрим ход 1.Ng1 плюс ещё один ход белых. В "ветке" 1.Ng1 лучшую оценку мы получим, предположим, для сочетания 1.Ng1 2.Nf3. Это будет та же позиция, что и наша исходная, но уже при ходе чёрных. Её оценка, соответственно, будет, скажем, "-0.10".

Таким образом, мы выяснили, что при ходе 1.Ng1 любой второй подряд ход белых даст нам оценку меньшую, чем оценка исходной позиции (-0.10 < +0.15).
Именно на этом основании, приступая к основному перебору, мы исключаем ход 1.Ng1 из рассмотрения, перебираем лишь 20 возможных ходов белых здесь (а не 21).

В этой позиции ход белых... Перед тем, как начинать основной перебор, производим перебор по null-move. Значит белые не ходят - т.е. пропускают ход ("делают" нулевой). Значит в этом переборе вашем ходить должны ЧЕРНЫЕ 2-й раз. Поэтому, ваше —

Неверно, т.к. второй подряд ход будет У ЧЕРНЫХ а не у белых.

Edwards

Т.е. вы неправильную позицию выбрали для рассмотрения. Дело в том, что мы запускаем вспомогательный перебор по нулевому ходу, НЕ ДО двухходовки одной из сторон как вы сказали, а уже после сделанного одной из сторон 1-го хода из этих двух. И именно в этот момент если вторая сторона пропустит ход и дальше получим определенную оценку, именно из той позиции отработает альфа-бета отсечение. Это нужно рисовать дерево с узлами чтобы было нагляднее, так без картинки трудновато многим понять...

нулевой ход вызывается при глубине depth >= 2
на 1 ходе нулевой не вызывается

А во-вторых вы действительно выбрали неудачную позицию. WC же писал, что для применения нулевого хода "позиция должна быть достаточно хороша для нас". А у вас она практически равная. Здесь его применять нет никакого смысла.
IMHO А вообще то я не уверен. Сейчас глянул в Стрелку, а там этот null_move фигачит почти в каждом узле.

Ага.
Но смысл такого null move мне непонятен совершенно.
Зачем нам считать второй подряд ход чёрных? Что это даст?
Смысл null move ведь состоит в том, чтобы отсечь какие-то ветки?
Что мы сможем отсечь, делая второй ход подряд за чёрных?

Ну, предположим, что в моей позиции
(я пока всё же её использую, если не возражаете. По-моему, дальнейшие рассуждения будут справедливы для всякой позиции, в которой ход за белыми)
имеется за чёрных какой-то жутко неудачный ход. Ну, например, ход 1...h7-h5. Вот такая у нас ОФ, предположим, для которой это ослабление - 1...h5 - хуже смерти.

Ну, что? ну посчитали мы все "вторые подряд" ходы чёрных. Ну, допустим, выяснили, что при любых ходах оценка за чёрных растёт, а при ходе 1...h5 падает. Ну, и что?
Дальше-то ведь нам надо свой ход (белых) искать.
Мы, что, в ответ на любой наш ход не будем рассматривать ответ 1...h5 ?
Таким образом, что ли, отсекаем?
Выглядит сомнительно.
Понятно же, что теоретически при некоторых наших ходах как раз 1...h5 может вдруг оказаться уместным за чёрных.

Так что, что-то Вы меня совсем обескуражили, Skipper_NORTON...

А почему неправильную?
Ну, давайте возьмём любую другую позицию с очередью хода за белыми. Чем моя хуже?
Ну, вот в моей есть "уже сделанный ход одной из сторон" - ход d7-d5.
Т.е. я не спорю, конечно, неправильную значит неправильную - Вам, наверное, виднее. Я не спорю, я просто пока не понимаю, к сожалению.

Эх, жаль, что Вы не делаете картинок, Skipper_NORTON!
Чувствуется, что у Вас имеется вкус к объяснению всего этого - наверняка Вы смогли бы пояснить всё внятно...

А я вот умею картинки делать... Но я - ни черта не понимаю! Такая вот ирония судьбы...

Ну, пусть так.

А это какой-то принципиальный момент - или просто такова практика?
Т.е. возможно ли использование алгоритма null move на глубине один или оно там принципиально невозможно?

Очень интересно, спасибо.

Т.е. получается в null move речь идёт вовсе не о "двухходовках" никаких, а о пропуске хода, о передаче очереди хода?

Дальше.
Из Вашего примера, WinPooh, не совсем ясно, почему в отношении 1.e4 мы честно произвели полный перебор, а в отношении 1.Na3 - null move.
Видимо, нужно уточнить так, что в отношении всех ходов мы сначала делаем null move (в том числе и в отношении 1.e4).
Т.е. мы фактически осуществляем полный перебор, но в каждой ветке (например, в ветке 1.е4) начинаем его с оценки нулевого ответа чёрных.
Воот.
И если нам так повезло, что ветка 1.е4 стояла у нас в очереди на перебор раньше, чем ветка 1.Na3... То мы имеем наш навар. Оценив один пустой ответ чёрных на 1.Na3 - мы уже можем диагносцировать, что 1.Na3 хуже, чем 1.е4.
Я правильно интерпретирую Ваш пример, WinPooh?

Думаете, мне стоит открыть ещё одну тему - "Что такое бета-отсечения?"
А что, я могу!

Edwards, похоже Вы не понимаете самых азов минимакса. Дело в том, что в корневых узлах дерева вариантов (т.е. тех узлах, где мы еще не достигли заданной глубины, и будем делать ходы) нас совершенно не интересует оценка узла как такового. Оценка узла определяется как МАКСИМУМ из оценок всех дочерних узлов, т.е. ПОСЛЕ выполненных ходов. А оценка дочерних узлов определяется как МИНИМУМ из оценок всех следующих дочерних узлов. И так до тех пор, пока мы не дойдем до терминальных узлов, из которых мы уже не делаем никаких ходов (просто потому, что достигли заданной глубины). В этих терминальных узлах мы и вычисляем оценку как таковую. А потом поднимаем эту оценку от терминальных узлов к своим предкам. И только после этого у нас возникают те самые альфа и бета условия, которые позволяют не рассматривать ненужные варианты. И только тогда начинает работать эвристика нулевого хода и все остальные эвристики.

Вполне возможно.
Для меня вопрос состоит в том, как это сделать вашей проблемой. А не только моей

В нашем совковом обществе, к сожалению, иногда трудно объяснить смысл сказанного мной сейчас. Но я пытаюсь... иногда...

Сорри за оффтоп.

Ну, а если по существу...

...то чисто теоретически, я не вполне понимаю, да, почему эвристика обязана начинать работать лишь после минимакса.
Я вот в первом посте привёл пример, мне кажется, осмысленной эвристики, работающей до минимакса.
Возможно, это пример неудачен, слаб и хил. Но я пока не вижу почему...

Впрочем, это мы уже отвлекаемся.

В общем-то я готов удовлетвориться ознакомлением с существующим порядком вещей. Без углубления в дебри возможного.

А почему? Почему "бета в этот момент для них будет равна плюс бесконечности"?
Наверное, я действительно не понимаю основ минимакса И зря тут выпендриваюсь

Можете навскидку дать определение понятия "бета"?

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

Получаем примерно следующее:

1. В начальном продолжении перебираем все хода и оцениваем позицию. Получили грубо говоря
1. Nf3 (+0.10) 1. d4 (+0.09) ... 1. Na3 (+0.01)

2. Рассматриваем все ответы на 1. Ng1-f3. Null move не используется. Получили оценку +0.05

3. Рассматриваем 1. d2-d4. Null move даст оценку +0.12. Надо перебирать дальше. Допустим, оценка будет +0.06

...

N. Рассматриваем 1. Nb1-a3. Null move дает оценку +0.04. Бросаем это гиблое дело.

А если после 1.Na3 черные в цуцванге?

Значит не судьба Вообще, многие программы плохо видят цугцванги (Корчной - Свидлер, например)