К главе 4

Задача 4.1

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

Рис. 17.4.1

Задача 4.2

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

Задача 4.3

Предположим, что вы сговариваетесь с противником относительно проведения данной игры. Вы договариваетесь об использовании некоторых секретных сигналов, которые позволяют вам подсказать ему, какой именно ход надлежит сделать. Цель же состоит в том, чтобы обыграть его возможно сильнее. Насколько при таких обстоятельствах эффективной оказывается методика альфа-бета? Приведите подробные доводы в пользу своего ответа. Является ли подход с точки зрения наискорейшего подъема хорошим описанием того, что происходит? Почему?

Задача 4.4

Дайте критику следующих утверждений: (а) Альфа-бета-теорема показывает, что в среднем не больше чем 2b^n/2-1 терминалов необходимо исследовать для деревьев четной глубины, (б) Располагая генератором приемлемых ходов, который всегда совершенным образом упорядочивает ходы, методика альфа-бета всегда дает оптимальное усечение дерева, и только недалекий человек ею не воспользуется, (в) Методика альфа-бета может удержать от ярких ходов, таких, как жертва ферзя, приводящая к мату.