Программирование на языке пролог (ЛП)

Для тех, кто не знаком с этой игрой, вкратце объясним ее правила. Два игрока по очереди заполняют клетки на доске размером 3x3. Один игрок использует для этого символ 0, а другой игрок — символ X. Цель игры — расположить три своих символа подряд по одной линии (вертикальной, горизонтальной или диагональной). Мы можем перенумеровать девять клеток на доске следующим образом:

Предполагается, что программа действует за игрока, делающего свои ходы ноликами. Предикат вынужденный_ход используется для ответа на вопрос: «Нужно ли делать вынужденный ход в конкретной позиции?» Такая ситуация имеет место, если игрок 0 (игрок, делающий ходы ноликами, т. е. программа) не может выиграть немедленно (мы не будем рассматривать этот слу- случай), но есть угроза того, что игрок Xможет выиграть следую- следующим ходом. Например, в позиции

Игрок вынужден поставить в 4-й квадрат, так как если он не сделает этого, то его противник будет иметь возможность на следующем ходу заполнить линию 1-4-7. Программа работает, пытаясь найти линию, две клетки которой заполнены крестиками, а третья – пустая. Если такая линия имеется, то игрок 0 вынужден сделать ход, поставив нолик в пустую клетку. В утверждении для предиката вынужденный_ходцель

линия(Клетки)

служит «генератором» возможных линий. Эта цель может быть согласована с базой данных несколькими способами, в частности, присваиванием в качестве значения переменной Клетки одного из возможных списков номеров клеток, находящихся на одной линии. Выбрав линию, необходимо проверить, существует ли угроза со стороны противника на этой линии. Это составляет задачу целевого утверждения, выполняющего функции «контролера»:

угроза(Клетки,Доска,К)

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

Основная идея программы очень проста – предикат линиявыдает линию, а затем предикат угрозапроверяет, имеется ли на этой линии угроза. Если это так, то доказательство согласованности исходного целевого утверждения вынужденный_ходзаканчивается успешно. Иначе инициируется возврат, и предикат линияпредполагает другую возможную линию. Эта линия также подвергается проверке, и, возможно, снова произойдет возврат. Если мы окажемся в ситуации, когда предикат линияне может более порождать линии, то доказательство согласованности целевого утверждения вынужденный_ходзакончится неудачей (вынужденных ходов нет).

Теперь рассмотрим, что происходит, если эта программа, являясь частью некоторой большей системы, успешно находит вынужденный ход. Переменная К получит в качестве значения номер клетки, в которой должен быть сделан ход, и эта информация будет использована где нибудь в другом месте в программе. Предположим, что в дальнейшем где-то в программе имеет место неудача при доказательстве согласованности некоторого утверждения и что Пролог в конце концов пытается вновь согласовать целевое утверждение вынужденный_ход.Тогда предикат линияначнет порождение новых возможных линий, которые должны быть проверены. Это бессмысленно, так как нет никакой пользы в том, чтобы искать альтернативный вынужденный ход. Если найден один из таких ходов, то мы не можем сделать ничего лучше, чем сделать этот ход – неудача при его осуществлении гарантировала бы проигрыш игры. В большинстве случаев, однако, альтернативных вынужденных ходов не будет, и при поиске сопоставления для цели вынужденный_ходбудут бесполезно просматриваться все неопробованные линии, прежде чем попытка доказать согласованность цели не закончится неудачей. Однако в случае альтернативных ходов известно, что даже если имеется другое решение, оно не может быть использовано без возникновения проблем с использованием первого решения Мы можем предотвратить потерю времени Прологом на поиск различных вынужденных ходов, поместив отсечение в конце соответствующего утверждения. Это приведет к замораживанию последнего успешного решения для предиката линия.Введение отсечения равносильно следующему заявлению: «если ищутся вынужденные ходы, то важно найти только первое решение».