Главная » Алгоритмы, Игры » Перебор с нулевым окном

0

В этом разделе мы рассмотрим несколько отвлеченную тему. Она будет не­обходима для понимания особенностей работы некоторых алгоритмов. Это — перебор с нулевым окном. Используется вариант alpha-beta алгорит­ма с амортизацией отказов. Что такое нулевое окно? Мы вызывали alpha- beta поиск с окном от -infinity до infinity. Результат получается такой же точности, что и при полном переборе. Если мы присвоим alpha некоторое значение, например 0, то beta при нулевом окне будет alpha+1. Поиск при нулевом окне намного быстрее, чем при полном окне. Это связано с тем, что больше будет отсечек. Допустим, мы вызвали alpha-beta функцию поис­ка с нулевым окном и получили некоторый результат:

score = AlphaBeta(alpha,alpha+1); Что он означает?

?     Если score меньше или равно alpha, то результат просчета при полном окне, т. е. истинный, будет от -infinity до score, включительно. Говоря другими словами, score — это наш возможный максимум.

?     Если score больше alpha, то истинный результат будет от score, включи­тельно, до infinity, score — это наш минимум.

Эти вещи несколько трудны для понимания, но их необходимо усвоить. Они используются в NegaScout и других алгоритмах.

Почему, если функция при нулевом окне вернула результат, меньший или равный alpha, это наш максимум? Я затрудняюсь объяснить. Нужно раз­мышлять, чтобы понять. Она, может, и могла вернуть результат еще мень­ше, но произошла отсечка, и если мы произведем перебор даже с полным окном, результат не будет более score.

Литература:

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

По теме:

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