Рисунок 14.4b. После взятия в плен камней из лунки 4 Мина. В калах Макса один камень попадает при раскладывании камней и еще три — при пленении.
Рисунок 14.5а. Многократный захват пленных Максом. Камни из лунок Мина 2, 3 и 4 берутся в плен одним ходом из лунки 6.
Рисунок 14.5b. Макс почти опустошил лунки Мина. Отметим, что Макс мог бы сделать ход с пленением из лунки 5 вместо лунки 6.
Программа для проверки правильности хода весьма проста. Выбор игрока ограничен максимум шестью возможностями для хода. После того как начальная лунка выбрана, легко находятся повторные ходы и взятия в плен. Для проверки окончания игры после хода надо лишь сравнить калах игрока, делавшего ход, с половиной общего числа камней. Конечно, отсюда никоим образом не следует, как находить наилучший в данной позиции ход.
Основная идея выбора хода состоит в построении дерева всех возможных продолжений из заданной позиции. Затем мы выбираем такую ветвь дерева, которая обеспечивает в конце концов победу. Для простоты изложения и еще по одной причине, которая вскоре станет понятной, мы будем называть компьютер Максом, а его противника — Мином. Предположим, что где-то в середине игры настала очередь хода компьютера. Макс может попытаться оценить положение, испробовав поочередно каждый из шести возможных ходов. Если один из них сразу же приводит к выигрышу, то Максу, очевидно, следует делать именно этот ход. Но что делать Максу, если ни один ход не ведет к немедленной победе? Как выбрать ход?
Максу следует проанализировать каждый ответ Мина на свои ходы. Допустим, один из этих ответов приводит к выигрышу Мина. Со стороны Макса было бы глупо делать ход, дающий Мину шанс на немедленную победу (хотя иногда Максу не избежать этого). В таком случае Макс узнает, какие ходы не делать. Однако, чтобы выбрать, какой ход делать, Максу придется построить еще один уровень ответов на ответы Мина к исходным ходам Макса. Если можно найти выигрышный ответ для некоторого множества ответов Мина, то Максу следует выбрать тот первоначальный ход, при котором Мину остаются только ответы, для которых есть выигрышный ответ Макса (помните дом, который построил Джек?). Если все это непонятно, попробуйте найти ходы, ответы и ответы на ответы для позиции с рис. 14.6.
Рисунок 14.6а. Ход Макса. Макс ходит из лунки 1.
Рисунок 14.6b. Результат хода Макса. Мин отвечает ходом из лунки 6.
Рисунок 14.6с. Позиция после ответа Мина. Макс отвечает ходом из лунки 2.
Рисунок 14.6d. Позиция после ответа Макса. Это всего лишь одна из примерно б3 подобных цепочек ходов.
Однако может оказаться недостаточным заглядывать вперед на два уровня. Несмотря на то что игра в калах обязательно кончается[18], предсказать, насколько далеко нужно заглянуть вперед, чтобы найти конец, оказывается весьма трудно. Каждый следующий уровень требует примерно в шесть раз больше времени и памяти, чем предыдущий. Надо что-то предпринять, чтобы остановить этот рост.
Этой цели служит статическая оценочная функция, дающая оценку позиции без построения дерева. В калахе мы воспользуемся разницей очков, получаемой как разность числа камней в калахах Макса и Мина. Если слегка изменить правила, потребовав, чтобы в калах победившего игрока сразу же перекладывались все камни, то разница очков всегда будет положительной, когда Макс имеет преимущество, а когда Макс выиграет, разница очков станет максимально возможной. Теперь Макс может выбирать тот из шести ходов, который максимизирует (не зря его зовут Макс) статическую оценочную функцию. Если два хода одинаковы с этой точки зрения, Макс может выбрать любой из них случайным образом.
Ну вот мы и ответили на вопрос о стратегии Макса. Так ли это? Если бы этим исчерпывалась стратегия калаха, то такая игра немногого бы стоила. Ведь Мин может ставить Максу ловушки, и, чтобы их избежать, Максу нужно смотреть вперед. Статическую опенку можно применять к позициям, лежащим глубоко в дереве и не являющимся заведомо выигрышными или проигрышными.
Пусть Макс хочет заглянуть вперед на d уровней. Будем считать, что начальная позиция лежит на уровне 0. Постройте все шесть мыслимых ходов, приводящих нас на уровень 1. Применяя в каждой позиции уровня 1 ходы Мина, получите все позиции уровня 2.
Продолжайте в том же духе, пока не построите все дерево вплоть до уровня d. Иногда может оказаться, что не все шесть ходов возможны, поскольку одна или несколько лунок пусты. Кроме того, некоторая ветвь может окончиться из-за хода, завершающего игру. Заметим, что все ходы на четных уровнях делает Макс, а на нечетных — Мин.
18
Попав в калах, камень уже никогда не покинет его: Кроме того, не существует циклических последовательностей ходов, приводящих к исходной позиции, поскольку любом ход либо помещает в калах хотя бы один камень, либо перемещает некоторые камни ближе к калаху. Если реализовать изменение, упомянутое в следующем абзаце, то любая игра должна заканчиваться в состоянии, когда все камни лежат в одном из двух калахов.