Главная > Интеллектуальные системы > Системы искусственного интеллекта
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.5.2. Второй недостаток: эффект горизонта

Необходимость иметь фиксированное значение максимальной глубины анализа в программах, работающих по принципу перебора допустимых ходов, как уже говорилось, приводит к двум основным недостаткам. Первый уже рассмотрен выше — программа может не “видеть” (и тем более оценить) последствия хода, которые проявляются на глубине, превышающей заранее установленную. На второй, менее очевидный недостаток обратил внимание Ганс Берлинер (в прошлом чемпион мира по шахматам по переписке) в своей диссертации в 1974 г. Он получил название эффекта горизонта и является неизбежным следствием первого недостатка. Оказывается, что программы, построенные по принципу систематического перебора допустимых ходов, по природе стремятся все сделать для того, чтобы все невыгодные события оказались за пределами максимальной глубины анализа, т. е. за пределами горизонта. Они не хотят видеть надвигающуюся катастрофу и располагают одним средством борьбы с ней — отодвигать неизбежный исход с помощью абсурдных ходов.

Рассмотрим пример, приведенный в диссертации Г. Берлинера (рис. 6.12). Слон белых, расположенный на поле окружен черными пешками, и его потеря неизбежна. Стратегия

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

В шахматах приняты следующие обозначения: К — конь, С — слон, Л — ладья, Ф — ферзь, — король, для пешек специальные символы не используются. Вертикали обозначаются буквами от а до Л, горизонтали — цифрами от 1 до 8, знак X означает взятие, + шах. Таким образом, означает, что пешка на вертикали продвигается первым ходом на один шаг (исходное поле не указывается), а 3 - КХ Се7 + означает, что на 3-м ходу конь берет слона, расположенного на поле е7 и объявляет при этом шах.

Рис. 6.12. Эффект горизонта (Н. Berliner, 1974). Ход белых.

Если же за белых играет программа рассмотренного выше типа, то она выбирает совсем другую стратегию. Ей достаточно построить ход игры таким образом, чтобы потерю слона вывести из поля своей видимости (со своего горизонта), а в этом случае все происходит так, как будто бы слон никогда не будет взят. Это находится в полном согласии с прямолинейной механической логикой альфа — бета-метода: достаточно найти последовательность из большого числа ходов с вынужденными ответными ходами черных, отодвигающую момент взятия слона противником. Так, в рассматриваемой позиции, если глубина анализа составляет 5 полуходов, лучшим ходом, найденным с помощю альфа — бета-процедуры окажется ход е5! С этого хода начинается реализация следующего плана “спасения”:

В случае (а) черные, очевидно, должны продолжать но угрожает Эту угрозу черные вполне могут отвести ходом но он уже лежит за пределами глубины анализа. В итоге программа, играющая за черных, выигрывает пешку вместо слона! В случае программа играет При этом оба коня защищены, а слон якобы спасен! На самом же деле он потерян, так как затем последует ход черных Наконец, в случае взятие черными слона является преждевременным и белые отыгрывают фигуру. Правильный ход на первом уровне программа сможет найти только в том случае, если максимальная глубина на анализе МАКСГЛ для нее равна 7. Для рассматриваемого случая это равносильно анализу 168 800 позиций!

Эффект горизонта может привести к очень большим потерям, и его устранение не представляется возможным, так как он порожден самим подходом к составлению программ. Именно с его последствиями связаны основные отличия игровых программ от игры человека. Он способен причинить много огорчений программисту, наблюдающему за игрой своей программы. Известен случай, когда в игре программы Chess 4.4 возникла позиция, в которой пешка достигла седьмой горизонтали. Для программы такая пешка стоит очень дорого, но более глубокий анализ показал бы, что защитить ее невозможно и она будет потеряна. Программа, естественно, играет так, чтобы не потерять эту пешку, максимально отдаляет момент потери и... после серии неудачных ходов теряет все накопленное преимущество. В конце концов ее противник берет пешку. (Правда, после этого Chess 4.4 обнаруживает все свои лучшие качества, начинает хорошо играть и выигрывает!)

<< Предыдущий параграф Следующий параграф >>
Оглавление