Перебирают ли движки все возможные позиции на заданную глубину?

Интересно.

 

Да, и такой вариант вполне допустим.

Да, это интересно.
Но ещё интересней для меня - понять почему, на каком основании программы позволяют себе так рисковать, не доводить до конца расчёт в теоретически небезнадёжных (небезнадёжных с точки зрения возможного всплытия оценки на первую строчку) ветках. Интересно, как в целом устроен алгоритм такого отсечения.
Я пока это не вполне ясно понимаю
Тут WinPooh о Null-move упоминал. Возможно, именно этот Null-move - важнейший инструмент подобных ранних, вероятностных (т.е., строго говоря, "на удачу") отсечений, нет?

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

 

если не отсекать, то даже на современных квадах такой движок в миттельшпильных позициях уже на глубине 12-14 уходил бы в полный ступор )))

 

Это так называемые эвристики. Т. е. нечто такое, что нельзя обосновать строго теоретически, но что дает хорошие практические результаты.

Сила программы зависит от скорости счета. Если программа считает глуже другой, то она играет сильнее другой. количество рассматриваемых вариантов тоже играет свою роль в силе игры: если программа отсекла важный вариант, то она может быть поймана на него. Самое большое искусство найти в этом баланс.

Яркий пример большого количества отсечений представляет собой человеческое мышление. Но это не мешает людям пристойно играть почему же человук так рискует?

В целом на любое отсечение, наверное, можно придумать контрпример, когда оно дает сбой. но если эти такие позиции крайне редко встречаются на практике (например в 1% всех партий), то сила увеличение силы игры в 99% других партий сильнее.

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

 

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

Меня скорей интересует, как технически, программно это реализовано. Как это формализовано - вот что меня интересует.

Null move - это главный способ избавиться от предположительно ненужных веток?

 

Чувствую кое кто на шару очень много хочет :d

 

Интересно еще на какую глубину считает движок без отчесений

 

Альфа-Бета отсечения работают на любой глубине, как я их понимаю.

 

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

 

Спасибо. Я лично думал, что пустой ход срабатывает чаще. А у вас он на какой глубине начинает работать?

Код:

if(depth >= ? ...)

 

Я решил снова переименовать тему Надеюсь, никто не против.
Переименовал в соответствии с первым предложением WildCat'a по этому поводу: "Перебирают ли движки все возможные позиции на заданную глубину?"

Дело в том, что тема оказалась более содержательной, чем мне поначалу представлялось.
В частности, я готовлю новые уточняющие вопросы, перевариваю пока информацию от WildCat'a...

 

Хотя это серезный офф-тор (все же пообещал не писать в теме о 7ЭБ) - почему этот чертовский 0-move (пустой ход), которые все авторы используют, не срабатывает в ЭБ (или каким другим способом передават ход соперника, дожидаясь свой ход в конкретной позиции) :/

 

А никак нельзя. Не подумал я.
Вот тут еще немного непонятно: "номинальная глубина 15" - это максимальная глубина, которую в корне задают как параметр альфв-беты? Откуда там тогда глубины больше 15, из-за продлений или у вас нулевой ход и в ФВ работает?
Может опять глупость спрашиваю, заранее извиняюсь, узнать-то надо. Спасибо.

 

Слушайте, WildCat, Вы пишете, что при анализе начальной позиции на глубине "1" у Вас уже отсечены три варианта.
Как такое может быть? :|

Единицей глубины мы ведь считаем полуход, правильно?
В начальной позиции имеем 20 возможных ходов белых.
И, что, три из них вообще не рассматриваются, что ли?
Если да, то почему, на каком основании?

 

Мы - люди с ИШФ-закалкой Что с нас взять?.. дети свободы...

Ой, да ладно

 

Это очень интересно, спасибо.
Попробую всё это понять. Извините за тугость мысли - материал новый для меня.
В частности, я только сейчас понял, что отсечение трёх ходов белых произошло, видимо, лишь на глубине 15... а не на глубине 1...

Дальше. Откуда взялось у Вас число 11?
Имеем два подряд (по null move) хода белых из начальной позиции. 2+11=13.
13 не равно 15. Ещё раз простите, если туплю.

Дальше.
Каким образом формализовано "не смогли поставить ему каких-то проблем"?
Я правильно понимаю, что это значит, что оценка наших трёх ходов-парий оказалась просто меньше, чем оценка некоего эталонного варианта, первой линии?

Кстати, а что такое ПВ? Эту аббреавитуру тут часто поминают. Первый вариант, что ли?

И ещё - если возможно, а какие именно три хода белых из начальной позиции оказались в столь унизительном положении? Просто интересно.

Боюсь, вопросы моим примитивны, не обессудьте.

 

Похоже, такие обяснения моему уровню понимания предмета - не соответствуют

 

т.к. НИ ОДИН движок не перебирает из-за альфа-бета отсечений ВСЕ позиции — я бы переименовал тему так... вместо "Перебирают ли движки все возможные позиции на заданную глубину?" —
"Перебирают ли движки все возможные позиции на заданную глубину из множества с учетом альфа-бета отсечений" (т.к. перебор с альфа-бета отсечениями - аналогичен перебору всех позиций)

Насколько я понимаю, запускать вспомогательный перебор с нулевым ходом который имеет такую же глубину после нулевого хода, как и имел бы глубину после сделанного хода - смысла не имеет. (так????) За то же время можно было бы перебрать — сделав первый попавшийся ход вместо нулевого - и получить альфа-бета отсечение с большей вероятностью, чем после нулевого. Какой тогда смысл терять время на расчет нулевого хода? Смысл имеется если мы уменьшаем глубину после нулевого хода черных и видим, что хотя у белых было 2 подряд хода и у них все равно осталось хуже, т.е. альфа-бета отсечение, БЕЛЫЕ не выберут этот вариант находясь ВЫШЕ. Тогда другие ходы черных из этого узла вместо нулевого только еще сильнее ухудшат положение белых и тоже будет альфа-бета отсечение.

Мы выиграли ИМЕННО потому что из данного узла перебирали на меньшую глубину после нулевого хода, а если бы после нулевого хода мы глубину не уменьшили бы, то ничего по времени мы не выиграли бы?

 

Нет, в полный ступор мы без нулевых ходов и отсечений в дереве впадаем уже на глубине 10 !

Предположим что у нас средняя позиция миттельшпиля в которой в среднем 35 ходов в позиции. При ОПТИМАЛЬНЕЙШЕЙ сортировке ходов, от которой наиболее эффективны альфа-бета отсечения, мы получим в каждом узле в среднем сколько ходов? корень квадратный из 35-ти, равно 6, но т.к. оптимальнейшая сортировка недостижима - получим где-то аналог дерева С ПОЛНЫМ ПЕРЕБОРОМ без альфа-бета отсечений и 7 ходами в среднем в каждом узле.

Я экспериментировал со своим движком а сортировка ходов у меня хорошая - (это я хорошо протестировал) и у меня дерево перебора разрастается так что оно аналогично 8 ходам в каждой позиции-узле!
Но пусть в нашем расчете будет 7 ходов в среднем.

Дерево до глубины 10 даст примерно 7 в степени 10 нижних узлов дерева на самом нижнем этаже.

Это около 300 миллионов позиций!!!! (Заметьте что я сюда не добавил еще количество позиций которое будет из-за дополнительного форсированного поиска в максимальной глубине и выборочных углублений! Просто посчитал полный широтный поиск на глубину 10 ! и получил ну самый что ни на есть МИНИМУМ и он оказался 300 миллионов позиций.

Скорость обработки у фритца 8 какая? Я смотрел - в миттельшпиле - 2 миллиона позиций в секунду на моем крутом процессоре-кваде. 300 миллионов разделим на 2 миллиона и получим 150 секунд — т.е. фритц должен думать по 2,5 минуты на глубину 10 ! А дальше умножаем в 7 раз при каждом следующем увеличении глубины.

Итак, если фритц перебирает на какую-то глубину полностью, не основываясь на всяких человеческих факторах отсечения веток дерева из-за нулевого хода и прочей причины - а действительно дает полный перебор на заданную глубину, с отсечениями только стандартными - альфа-бета, то ———

На глубину 11 фритц должен думать 17,5 минут и уже впасть в полный ступор! Продолжаем умножать на 7...
На глубину 12 фритц должен думать 122 минуты, т.е. 2 часа над одним ходом.
На глубину 13 — должен думать 14 часов,
На глубину 14 — должен думать 4 суток,
На глубину 15 — должен думать 1 месяц,
На глубину 16 — должен думать ПОЛГОДА.

А сколько он реально думает на глубину 16 ? Я не поленился, посмотрел. Он думает 2 минуты. Вот и сравните полгода и 2 минуты. Получается - в 125000 раз меньше, он перебирает позиций чем должен перебрать, на заданную глубину если бы была цель - полный перебор с отсечениями только альфа-бета и без всяких других человеческих отсечений типа нулевых ходов.

Так что то что он там пишет что перебирает на глубину 16 - чистой воды ФИКЦИЯ.

 

Если перебор все равно не-полный то смысл писать что он перебирает на глубину 16 ? Можно было бы вообще достигнутый максимум после форсированного поиска в самой глубине записать и отобразить что он якобы перебрал на глубину 30 !

У меня нет нулевого хода в движке, перебираю по честному на полный только с альфа-бета отсечениями и не достигаю глубины 10... Я бы достигал, но меня сильно тормозят еще форсированные выборочные углубления, а без них нельзя... Иначе программа не сможет находить даже неглубокие форсированные маты.

Надо бы пустой ход заюзать, только вот не знаю насколько он реально мне поможет... Еще раз... Кто опытный писатель движков? Правильно ли полагать, что при использовании нулевого хода мы ДОЛЖНЫ ВСЕГДА сокращать оставшуюся глубину?

 

Вообще то да, но вот некоторые сильно заблуждаются, полагая что в 21 веке программа реально способна жахнуть полный перебор только с отсечениями альфа-бета на глубину 16... за пару минут.

 

значит наверное нулевой ход - хорошо усиливает игру программы? Но в эндшпилях его по любому использовать нельзя.

 

Хотел переименовать
Да форумный движок не дал. Там ограничение на число символов в названии.

 

Skipper_NORTON

А как будет выглядить время полного перебора до глубины 10 для IBM Roadrunner?

http://ru.wikipedia.org/wiki/IBM_Roadrunner - тут его тех. характеристики