Главная » Игры, Теория » Единственный ответ

0

Я ни в коем случае не могу претендовать на полное изложение предмета, хотя сам и использую данный прием в своих программах. Если в позиции есть только одно легальное перемещение, то глубину просчета нужно увели­чить. Все вроде бы просто. Только что считать легальным перемещением? Если существует некоторая позиция, где все ходы не несут материального выигрыша, а один выигрывает пешку, то можно сказать, что ход, выигры­вающий пешку, является легальным, или правильным. Самое простое тол­кование легальности перемещения — это когда короля не бьют следующим ходом. Если есть только один ход, где король не под боем, то глубину нуж­но увеличить. В стандартных выборочных продлениях при шахе глубина остается неизменной, а если легальное перемещение единственное, то ее можно даже увеличить.

Существует и другое понятие легальности перемещений. Легальными назы­ваются те перемещения, где мы не теряем материал. Например, существует такой способ организации программы: сначала считается только материал (что намного быстрее) и формируется список легальных ходов с максималь­ной оценкой. Потом этот список подается на вход функции, просчитываю­щей стратегию. Она может использовать какие угодно критерии классифи­кации ходов по стратегическому принципу. Такой подход встречается во многих средних программах и даже некоторых коммерческих, чтобы доста­вить пользователю максимальное удовольствие от игры. Слишком сильную программу так не сделать. Дело в том, что все усилия брошены на то, чтобы сосчитать максимально глубоко, с трудом извлекается один лучший ход или главная строка изменения, а на то, чтобы извлечь целый список, просто не хватает времени. Это намного медленнее, чем получить один лучший ход. Тем не менее данная схема вполне работоспособна и годится для простой программы. Получаем список ходов, оценка которых (только материальная) равна максимальной. Если есть один ход, выигрывающий материал, значит, есть только один легальный ход, и думать дальше вообще не о чем. Если существует три хода, при которых мы не теряем материал, то стратегическая функция исследует только эти три хода.

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

Рассмотрим счетчик легальных ходов, равный нулю перед просчетом данно­го узла. Как только мы нашли легальный ход, мы увеличиваем счетчик. По­ка счетчик равен нулю, у нас одно легальное перемещение (предположи­тельно). Если счетчик равен единице, у нас два легальных перемещения, и т. д. Результат счета не может быть меньше alpha для нашего узла. Как же мы определим легальные ходы, если не можем получить точный результат счета? Если значение alpha уже достигло порога легальности для данного узла, можно предположить, что у нас есть, как минимум, одно легальное перемещение в этом узле, и глубину дальше увеличивать нет смысла. Мы еще не просчитали, а уже делаем вывод о количестве легальных ходов в уз­ле. Оценка данного узла не может быть менее alpha, и совершенно нет ни­какой разницы, получено ли значение alpha в этом узле или досталась от предыдущих узлов в строке. Мы все равно уменьшаем глубину счета. Мож­но даже подрезать статической оценкой и принять оценку хода как alpha. Статическая оценка после хода должна быть меньше или равна alpha. Если мы подрезаем статической оценкой, то текущая строка никак не попадет в главное изменение. Можно просто сократить глубину счета, когда alpha дос­тигнет некоторого уровня, а оценка после хода не улучшает alpha. И то и другое не соответствует полному перебору. Мы должны понимать, что мы только регулируем глубину счета, пока оценка узла не достигла некоторого уровня. Ошибка может получиться и при подрезании статической оценкой, т. к. данная строка не попадет в главное изменение. До какой величины нужно дотягивать alpha прежде, чем подрезать? Однозначного критерия нет. Обязательным может быть только статический критерий — оценка после хода не должна улучшать alpha. Можно дотягивать до корневой оценки де­рева перебора. При этом не надо забывать, что корневая оценка может быть не стабильной, а промежуточной в результате размена или другой комбина­ции. Я лично использовал следующий критерий. Если противник взял фи­гуру предыдущим ходом, нужно попытаться компенсировать это и не подре­зать, пока alpha не компенсирует потерю. Это хорошо работает на практике и в случае подрезания статической оценкой, и при сокращении глубины, если мы уточняем главное изменение. Программа комбинации просматри­вает намного глубже. Только результат счета нужно уточнять.

Есть и другие критерии для оценки. Например, ждут второй отсечки за beta. Если ее нет, то узел пересчитывается заново на большую глубину. Это очень медленно, и сразу возникает множество вопросов. Может, alpha-beta интер­вал мал, и мы портим стратегию? Нужно ли в таком случае из-за небольшо­го стратегического преимущества перебирать заново? Если мы используем NegaScout или другой алгоритм с нулевым окном, как это сочетается с ле­гальностью ходов? Самый простой способ заключается в следующем. Если результат оценочной функции для некоторого хода существенно больше, чем для других, то данный ход нужно рассмотреть на большую глубину. Иными словами, взятия нужно рассматривать глубже. Это очень хорошо работает, только выборочных продлений становится много, и дерево нужно подрезать чем-то вроде Futility pruning. Взятия пешек можно, например, продлевать первые 6 полуходов, потом — по возрастанию веса взятой фигу­ры. Данный алгоритм хорошо известен из теории игр и качественно улуч­шает тактический уровень, но разорителен по времени выполнения. Хотя работающую схему получить вполне возможно.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии