ПРИНЯТИЕ ОПТИМАЛЬНЫХ РЕШЕНИЙ В ИГРАХ

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







Материалы

Яндекс.Метрика