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

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

 

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

Свое мнение основываю на прочтении книги Корнилов Е.Н. Программирование шахмат и других логических игр
http://www.sprinter.ru/books/1850816.html

 

Используется альфа-бета отсечения. Общий смысл примерно такое:

белые ходят 1. Bxh7+ им выигрывают ладью (оценка +5)
белые ходят 1. h3 черные отвечают 1... g6 и получается оценка (+0.5).

В этом случае происходит отсечение ненужных веток, и остальные ответы черных на ход 1. h3 не рассматриваются. Да, допустим что черные в варианте 1. h3 Qxg2# матуют (т. е. оценка может быть насколько угодно меньше +0.5). Но все равно это лишняя работа, потому что оценку исходной позиции (минимум +5) это не изменит.

 

Ну, теоретически как минимум разница в оценочных функциях может влечь за собой разницу в силе игры.
Если программа А на каждом ходу оценивает позицию на 0,01 пешки точнее, правильнее, чем программа Б, то в итоге у А, вероятно, неплохие шансы выиграть партию.

 

Ага, различие было бы в оценке позиции. Замечание верно.
Хотя, имхо, предел 0,01 ничего бы не решил 0,1 еще куда ни шло

 

Как раз Рыба, как я понимаю, выдаёт неправильные значения глубины и собственной скорости - она в этом плане уникум. Считает она гораздо быстрее и больше, чем пишет.

 

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

 

Просчитать всё на 12 полуходов - это значит, без учёта перестановок, перебрать ~30^12 позиций - если считать, что в каждый момент есть выбор из 30 ходов. Многовато будет. Но отдельные варианты при глубине 12 Рыбка наверняка при этом смотрит не то что на 12 или 15 полуходов - гораздо глубже. Особенно если там взятия, шахи и т.п.

 

слабо сказано
у меня как-то при глубине в 12, рыбина выдала ПВ-линию с глубиной под 40!

 

Mustitz, спасибо!

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

Я не уверен, что мой вопрос понятен
Попробую переформулировать так.
Может ли "Рыбка" "бросить" расчёт какого-то разветвления на "пол-дороге"?
Допустим, изначально у неё есть равная позиция, она уже посчитала какой-то солидный ход-кандидат на глубину 12, получила оценку +0,20; и вот считает следующий, получает на глубине, условно, 9 в нём оценку -5.00 и обрывает расчёт. Может такое быть?

 

Ага, спасибо.

 

Что не так?
Правильно "чайниковский"?
Может быть.
Но не факт.
Наш критик пока не озаботился никакими обоснованиями своей корявой претензии

 

А когда, в какой момент прога делает ход в игровом режиме? Что служит формальным признаком того, что анализ пора закончить и надо ходить? И всегда ли она выбирает "первую линию"?

 

Тогда вопрос - а что такое одна итерация?

Т.е. если две проги запустить несколько раз играть одну и ту же позицию - они по идее должны будут повторять одну и ту же партию? Но реально по-моему этого не происходит...

 

Не знаю тонкостей, но на вид - слово "чайниковский" возникает по всем правилам языка, как только "чайник" становится одушевлённым. И это одушевление давно уж произошло, сколько бы консерваторы не возражали. Ну турнире: вижу кого? Вижу чайников. А не "вижу чайники".

 

Сорри, но нельзя ли с чайниками не пойти в тему по русскому языку? Здесь эта дискуссия - оффтоп.

 

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

Всё-таки полной ясности у меня пока не возникло

Эх, хорошо б по-Мустицевски, "на пальцах" пояснили, что значит "отсечение может произойти и на глубине 9"...

 

Хм.. в каком смысле и на каком основании? То ли чего-то я не догоняю, то ли формулировка не та :/ Вы имеете в виду, что прога проверяет единовременно только одну линию, чтобы память не забивалась?

 

А чайнику (да и не чайнику тоже) то зачем всё это надо знать? Хотит докопаться до истины: Что появилось раньше курица или яйцо? :|

 

Вот как Таль реализует "нулевой ход" в Широве.

 

У меня был реализован другой алгоритм называния темы, WildCat

Я исходил из того, что получив ответ на первый вопрос, я (и не только я) смогу тут продолжать задавать чайнические вопросы

 

Насколько я понял, в случае альфа-бета отсечений забракованный ход бракуется всё же лишь тогда, когда хотя бы одна вариантная цепочка в этой, бракуемой ветке досчитана на глубину 12 (не на 9).
Если я не прав - поправьте.

А вот про
"есть просто достаточно серьезные основания считать вероятность линии стать первой незначительной"
- вот это очень интересно. Собственно, по сути об этом и был мой первоначальный вопрос.
И о том, готова ли программа доверять этому шаманству уже на глубине 9, неужели она не станет проверять его на глубине 12?