Конспект установочных лекций по комплексному курсу Информатика, Теория информации


Альфа»бета»поиск


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

Начнем с формализации проблемы. Пусть (x и р- игроки. Пусть у е {а, р} - один из игроков. Будем использовать следующие типы и функции для моделирования игры:

(1)        Рosition - тип позиции в игре, player - тип игрока, содержащий только элементы а и р.

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

(3)        Пусть t есть предикат на множестве игроков и позиций. Истинность t(s, р) определяет, является ли позиция р терминальной для игрока s, точнее: достигнут ли конец игры, когда в позиции р право хода имеет игрок s.

(4)        Пусть g - предикат на множестве игроков и позиций. Значение истинности g(s, р) устанавливает, является ли терминальная позиция р выигрышной для игрока s.

(5)        Для игрока s обозначим его партнера по игре через gegner (s). Всегда имеет место gegner (а) = ^ и gegner (?) = а.

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

fct sicher = (player

s, position р) bool:

       if  t(s, p)   then g(s, p)




- Начало -  - Назад -  - Вперед -



Книжный магазин