Генератор - ход
Cтраница 2
Генератор ходов, связанный с данной целью, предлагает ходы, направленные на достижение этой цели. Эти генераторы должны находить положительные доводы в пользу предлагаемого хода. Например, в дебюте ход d2 - d4 предложит только тот генератор, который связан с контролем над центром; только генератор, связанный с материальным балансом, предложит убрать фигуру, находящуюся под ударом. Эти генераторы ходов соответствуют генераторам Бернстейна с той лишь разницей, что они предназначены исключительно для генерирования очередных ходов и не используются для генерирования продолжений, которые рассматриваются при анализе данного хода. В программе Бернстейна и тем более в Лос-Аламосской программе одни и те же генераторы используются как для отыскания возможных ходов, среди которых делается окончательный выбор, так и для получения продолжений, которые необходимо исследовать для оценки последствий того или иного хода. В нашей программе последнюю функцию выполняет отдельный набор генераторов. [16]
Например, все знают, что значит решить задачу, если шаша цель - одержать победу в шахматной партии. В мире фантазий мы просто порождаем страте-тию, которая ведет к мату при любых контрстратегиях противника. Вместо этого хорошие ходы в шахматной игре ищутся путем порождения различных вариантов и последующей мучительной процедуры их оценивания с использованием приближенных и часто ошибочных мер, которые предположительно указывают вероятность того, что та или иная последовательность ходов лежит на маршруте, приводящем к выигрышной позиции. Генераторы ходов существуют, не существует генераторов выигрыш-лых ходов. [17]
Так же, как и предыдущие программы, она укладывается в шенноновскую схему, однако в ней сделан чрезвычайно важный шаг в направлении усложнения алгоритма: программа рассматривает лишь небольшую часть возможных ходов и продолжений. Она содержит ряд подпрограмм, называемых генераторами правдоподобных ходов. Программа рассматривает не более семи возможных ходов в каждой позиции. Генераторы ходов включаются друг за другом в заданном порядке до тех пор, пока не накопится семь различных ходов. [18]
 |
Разветвляющееся дерево ходов и контрходов в начале игры в крестики и нолики. [19] |
Эта рекурсия может спуститься на несколько уровней - но рано или поздно она должна достичь дна. Для этого существуют несколько полезных критериев, таких как, например, количество фигур с обеих сторон, количество и тип фигур, находящихся под атакой, контроль над центром, и так далее. Оценивая позицию таким образом в начале, на дне, рекурсивный генератор ходов может вернуться наверх и оценить позицию с точки зрения каждого отдельного хода. Таким образом, один из параметров в этом самовызове должен определить, на сколько ходов вперед просчитывать. [20]
При описании структуры программы мы не рассматривали детально механизм исследования продолжений, а просто предполагали, что некоторые продолжения исследуются, после чего для них вычисляются статические оценки и минимаксным методом находятся рабочие оценки. Между тем важность самого этого механизма очевидна. В каждой позиции, появившейся в процессе анализа, они определяют подлежащие исследованию ветви, которые исходят из этой позиции, а следовательно, среднее число ветвей дерева и его среднюю глубину. Генераторы возможных ходов и правила окончательного выбора также влияют на количество рассматриваемых продолжений. [21]
Так же, как и предыдущие программы, она укладывается в шенноновскую схему, однако в ней сделан чрезвычайно важный шаг в направлении усложнения алгоритма: программа рассматривает лишь небольшую часть возможных ходов и продолжений. Она содержит ряд подпрограмм, называемых генераторами правдоподобных ходов. Программа рассматривает не более семи возможных ходов в каждой позиции. Генераторы ходов включаются друг за другом в заданном порядке до тех пор, пока не накопится семь различных ходов. [22]
После того как все предложенные ходы в процессе анализа получили оценки, необходимо выбрать из них какой-то один. Очевидность этого правила основана на предположении, что выбор производится из некоторого фиксированного множества возможных ходов. Если это не так ( например, ходы предлагаются последовательно), то возможны и другие правила. Простейшее правило, которое в настоящее время применяется в программе, состоит в том, что выбирается первый же приемлемый ход. Ход считается приемлемым, если его оценка выше установленного порога. Исполнительная программа просматривает сверху вниз список целей. При этом включаются генераторы ходов, причем ходы, порождаемые более важными целями, рассматриваются первыми. Программа помнит ход, получивший к данному моменту наивысшую оценку, и выполняет его, если не находится ни одного приемлемого хода. [23]
Страницы: 1 2