Главная » Игры, Теория » Дробный Depth

0

Нужно просчитывать глубже многие ходы, но это может привести к взрыву дерева поиска, и только шахи являются стопроцентно корректными расши­рениями на любой глубине. Возникла следующая идея: делать Depth дроб­ным. В каждом узле Depth уменьшается не на 1, а на 4. Начальное значение Depth тоже равно глубине просчета, умноженной на 4. Таким образом, в за­висимости от нашего представления о правдоподобности данного хода, мы можем при одних ходах увеличивать Depth на 4 (при шахах), а при других — на меньшую величину. Приведем примерный список расширений:

D шах — 4;

?    размен — 3;

?    пешка на предпоследней горизонтали — 3.

Дробный показатель глубины является, в сущности, вероятностным мето­дом, и я отношусь к нему довольно скептически, но очень многие програм­мы используют его, и он является самым простым способом осуществить выборочные продления многих вариантов, не приводя к взрыву дерева по­иска. Мое личное мнение, что программа должна считать точно, а не нака­пливать вероятность правдоподобия в каждой строке, но есть другие взгля­ды на этот счет. Альтернативным является метод увеличения Depth всегда на 1, но, в зависимости от глубины просчета, дальше продлеваются все лучшие и лучшие ходы, а некоторые постепенно отсеиваются.

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

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

D Расширение, если шах. Обратите внимание на вскрытые шахи, когда фи­гура при ходе освобождает линию атаки на короля дальнобойной фигуре.

?    Расширение при размене. Можно до некоторой степени расширять взя­тия, можно проводить расширения в зависимости от захваченной части.

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

не бьют (обычно при шахе), то глубина увеличивается на 1. Получается, что шахи рассматриваются на глубину +1, а единственный ответ +2. Конкретная реализация может быть различной.

?    Расширение по угрозе. Для обнаружения угрозы может использоваться нулевой ход или детектор атаки.

?    Если пешка пошла на предпоследнюю горизонталь.

D Если резко падает безопасность короля. В самом простом случае, когда расстояние между ферзем противника и нашим королем опасно сокра­щается.

?    Если оценка изменяется резко без взятия.

?    Если результат некоторого хода существенно выделяется среди остальных.

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

Литература:

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

По теме:

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