Лекция: Игры с полной информацией и двумя участниками.
В данном разделе речь идет об играх с двумя игроками, которые будут именоваться МАХ и MINпо причинам, которые вскоре станут очевидными. Игрок МАХходит первым, после чего игроки делают ходы по очереди до тех пор, пока игра не закончится. В конце игры игроку-победителю присваиваются очки, а на побежденного налагается штраф. Игра может быть формально определена как своего рода задача поиска с описанными ниже компонентами.
· Начальное состояние, которое включает позицию на доске и определяет игрока, который должен ходить.
· Функцияопределения преемника, возвращающая список пар, каждая из которых указывает допустимый ход и результирующее состояние.
· Проверка терминального состояния, которая определяет, что игра закончена.
Состояния, в которых игра закончена, называются терминальными состояниями.
· Функция полезности (называемая также целевой функцией, или функцией вознаграждения), которая сообщает числовое значение терминальных состояний. В шахматах результатом является победа, поражение или ничья, со значениями + 1, -1 или 0. Некоторые игры имеют более широкий диапазон возможных результатов; например, количество очков в нардах может составлять от +192 до -192.
Начальное состояние и допустимые ходы каждой стороны определяют дерево игры для данной игры. На рис. 10.22 показана часть дерева игры в крестики-нолики. Из начального состояния игрок МАХ имеет девять возможных ходов. Ходы чередуются так, что МАХ ставит значок Х, а MIN значок О, до тех пор пока не будут достигнуты листовые узлы (вершины), соответствующие терминальным состояниям, таким, что один игрок поставил три своих значка в один ряд или заполнены все клетки. Число под каждым листовым узлом указывает значение полезности соответствующего терминального состояния с точки зрения игрока МАХ; предполагается, что высокие значения являются благоприятными для игрока МАХи неблагоприятными для игрока MIN (именно поэтому в теории этим игрокам присвоены такие имена). Задача игрока МАХ состоит в использовании дерева поиска (особенно данных о полезности терминальных состояний) для определения наилучшего хода.