Минимакс
Минимакс (иногда MinMax , MM [1] или седловая точка [2] ) — правило принятия решений, используемое в искусственном интеллекте , теории принятия решений , теории игр , статистике и философии для минимизации возможных потерь для наихудшего случая ( максимальных потерь) . сценарий . Когда речь идет о прибыли, это называется «максимин» - максимизировать минимальную прибыль. Первоначально сформулировано для теории игр с нулевой суммой для n игроков ., охватывающий как случаи, когда игроки делают поочередные ходы, так и те, когда они делают одновременные ходы, он также был распространен на более сложные игры и на общее принятие решений в условиях неопределенности.
Максимальное значение - это наибольшее значение, которое игрок может получить, не зная действий других игроков; эквивалентно, это наименьшее значение, которое другие игроки могут заставить игрока получить, когда они знают действия игрока. Его формальное определение: [3]
Вычисление максиминного значения игрока выполняется в наихудшем случае: для каждого возможного действия игрока мы проверяем все возможные действия других игроков и определяем наихудшую возможную комбинацию действий — ту, которая дает игроку i наименьшую ценность. Затем мы определяем, какое действие игрок может предпринять, чтобы убедиться, что это наименьшее значение является максимально возможным.
Например, рассмотрим следующую игру для двух игроков, где первый игрок («игрок в ряд») может выбрать любой из трех ходов, обозначенных T , M или B , а второй игрок («игрок в столбце» ) может выбрать любой из трех ходов. два хода, L или R . Результат комбинации обоих ходов выражается в таблице выплат:
(где первое число в каждой ячейке — это выплата игрока строки, а вторая цифра — выплата игрока столбца).
Если оба игрока используют свои максиминные стратегии , вектор выигрыша равен .
