Описание тега minimax
Minimax включает создание игрового дерева для рассмотрения всех возможных результатов игры с учетом ее текущей конфигурации. Затем минимаксный агент выбирает ветвь, которая приводит к максимальному выигрышу агента и, следовательно, к минимальному выигрышу оппонента ( игра с нулевой суммой).
Хотя создание всего игрового дерева может показаться сложной вычислительной задачей, было разработано несколько методов для сокращения времени вычислений. Один из самых известных методов - это альфа-бета-обрезка: при наличии ветки в дереве игры прекратите оценивать эту ветвь ("обрезать"), как только вы обнаружите, что результат в этой ветке хуже, чем в ранее исследованной ветке. Некоторые варианты (например, те, которые используются в шахматных программах) учитывают только определенное количество ходов и не всегда до конца игры.
Другой вариант минимакса, называемый expectiminimax, вводит в игру "случайные" элементы, такие как броски костей.
Наконец, обратите внимание, что хотя минимакс изначально предназначался для игр с двумя игроками, этот метод был расширен на игры с более сложными настройками.
Дальнейшее чтение: