Cтраница 1
Альфа-бета алгоритм является эффективной, реализацией минимаксного принципа. Эффективность альфа-бета алгоритма зависит от порядка, в котором просматриваются варианты ходов. Применение альфа-бета алгоритма приводит, в лучшем случае, к уменьшению коэффициента ветвления дерева поиска, соответствующему извлечению из него квадратного корня. [1]
Альфа-бета алгоритм позволяет уменьшить пространство состояний путем удаления ветвей, неперспективных для успешного поиска. [2]
Альфа-бета переход происходит при 796 С. Pr ( III) окрашены в зеленый цвет. Оксид Рг2О3 входит в составы спец. [3]
Минимаксный, принцип и альфа-бета алгоритм лежат в основе многих удачных игровых программ, чаще всего шахматных. Для оценки терминальных поисковых позиций использовать подобранную специально для данной игры оценочную функцию. [4]
Так, на рис. ЗЛО вершины оцениваются в порядке, соответствующем порядку помечающих их букв в латинском алфавите. Альфа-бета метод работает в точности так же, как и метод минимаксной оценки, но одновременно собирает как можно больше сведений об оцениваемом дереве. [5]
Существует еще один прием, называемый последовательным углублением. Программа многократно выполняет альфа-бета поиск сначала до некоторой небольшой глубины, а затем, увеличивая предел по глубине при каждой итерации. Процесс завершается, когда истекает время, отведенное для вычисления очередного хода. Выполняется наилучший ход, найденный при наибольшей глубине, достигнутой программой. [6]
Благодаря эффекту отсечения альфа-бета алгоритм просматривает только некоторые из существующих ветвей и тем самым уменьшает коэффициент ветвления. В шахматных программах, использующих альфа-бета алгоритм, достигается коэффициент ветвления, равный 6, при наличии 30 различных вариантов хода в каждой позиции. [7]
Поскольку минимаксная оценка дерева может оказаться весьма длительной процедурой, было потрачено много усилий для повышения ее эффективности, увенчавшихся известным успехом. Одним из довольно эффективных методов является так называемое альфа-бета усечение. [8]
Существует в различных модификациях; при 575 С происходит альфа-бета переход с изменением точечной группы симметрии от 32 к 62, но без разрушения кристалла. Окраски связаны с наличием примесей, в т.ч. аморфных. [9]
Целью его является достижение большей предельной глубины поиска за счет отбрасывания менее перспективных продолжений. Этот метод позволяет отсекать ветви в дополнение к тем, которые отсекаются самим альфа-бета алгоритмом. В связи с этим возникает риск пропустить какое-нибудь хорошее продолжение и неправильно вычислить минимаксную оценку. [10]
В системах, база знаний которых насчитывает сотни правил, весьма желательно использование стратегии управления выводом, позволяющей минимизировать время поиска решения и тем самым повысить эффективность вывода. К числу наиболее известных стратегий относятся поиск в глубину, поиск в ширину, разбиение на подзадачи и альфа-бета алгоритм. [11]
Этот результат имеет один практический аспект, связанный с проведением турниров игровых программ. Шахматной программе, участвующей в турнире, обычно дается некоторое определенное время для вычисления очередного хода, и доступная программе глубина поиска зависит от этого времени. Альфа-бета алгоритм сможет пройти при поиске вдвое глубже по сравнению с минимаксным полным перебором, а опыт показывает, что применение той же оценочной функции, но на большей глубине приводит к более сильной игре. [12]
Иногда задача поиска сводится к уменьшению пространства состояний путем удаления в нем ветвей, неперспективных для поиска успешного решения. Поэтому просматриваются только те вершины, в которые можно попасть в результате следующего шага, после чего неперспективные направления исключаются из дальнейшего рассмотрения. Этот метод - альфа-бета алгоритм - нашел широкое применение в основном в системах, ориентированных на различные игры, однако он может использоваться и в продукционных системах для повышения эффективности поиска. [13]
Однако, если порядок просмотра окажется удачным, то экономия может быть значительной. Было доказано, что в лучшем случае, когда самые сильные ходы всегда рассматриваются первыми, альфа-бета алгоритм вычисляет статические оценки только для N позиций. [14]