Блог

Я где-то читал, что минимаксный алгоритм может быть обобщен для более чем двух игроков. Представьте, что у нас есть 3 игрока, каждый из которых хочет максимизировать свой собственный ответ. Возможно ли использовать альфа-бета-обрезку в этом случае? или это бесполезно? почему?

Примечание: Игры с ненулевой суммой.

Да, но вы должны четко понимать игровую механику. В вашем данном дереве сначала отображаются синие ходы, затем зеленые, а у красного есть окончательный выбор.

Здесь есть два подхода, в зависимости от игровой механики. Если единственной целью каждого игрока является максимизация собственного результата, то вам нужно решать каждый уровень за активного игрока, учитывая только соответствующую награду.

В данном примере, предполагая, что награды перечислены в порядке (синий, зеленый, красный), тогда у красного четыре варианта выбора среди пар (2-4),(9-4),(0-6),(0-2) будет R, L,R,R; представление green со значениями (8-5),(9-3). Из них green выберет L, L; blue получит выбор (6-8) и сделает выбор R, остановившись на (8, 9, 6) для игрового значения.

Однако, если у игроков есть какие-либо другие мотивы, такие как максимизация общего выигрыша (чего мы случайно достигли выше) или придание значения чистой разнице, тогда вам нужно будет использовать несколько более сложный алгоритм принятия решений; применяется та же логика.

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