В теории игр минимакс - это метод, направленный на минимизацию ожидаемых потерь. Для этого игрок предполагает, что решение его оппонента будет неблагоприятным. То есть худший сценарий ожидается до движения противника.
Другими словами, метод минимакса состоит в том, как принять наилучшее решение, предполагая, что другой игрок выберет для вас наихудший сценарий.
Мы должны принять во внимание, что этот метод применим в игре двух человек (два игрока) и что это не кооперативная игра, а игра с нулевой суммой. Это означает, что то, что выигрывает один игрок, теряется другим, и наоборот. Следовательно, каждый агент будет заинтересован в максимальном увеличении своей полезности, даже если это вредит другому.
Здесь мы также должны помнить, что теория игр - это раздел математики и экономики, изучающий выбор, который оптимизирует ситуацию отдельного человека, когда затраты и выгоды не фиксируются заранее, а зависят от решений других.
Минимаксный алгоритм в дереве решений
Мы можем увидеть, как метод минимакса применяется в дереве решений с несколькими узлами. Игра начинается внизу и заканчивается результатом на верхнем уровне.
У основания дерева противник делает первый ход, поэтому ожидается худший результат. Затем, на втором уровне, игрок x будет стремиться максимизировать свою прибыль, принимая во внимание решение, ранее принятое противником.
На третьем уровне снова очередь соперника и так далее. Ниже мы покажем пример.
Пример минимаксного алгоритма
В следующем дереве решений мы показываем результаты, полученные игроком x в каждый момент игры. В основе, на первом уровне, противник принимает решение. По этой причине приведены сценарии, в которых игрок может проиграть -10 или выиграть 5.
На втором уровне это зависит от игрока x, поэтому он максимизирует свою прибыль. Между проигрышем 10 или выигрышем 1 вы выиграете 1. Точно так же между выигрышем 5 или 7 вы выиграете 7.
Затем снова наступает очередь противника, поэтому будут даны сценарии, в которых игрок x имеет худший результат, -3 и 4, в зависимости от случая. Наконец, между проигрышем 3 или выигрышем 4 игрок x примет решение, которое позволит последнее.
Мы должны учитывать, что значения каждого узла будут зависеть от функции полезности.
Чтобы лучше понять дерево, предположим, что в основе лежит решение о распределении продукта. Конкурент (противник) может передать распределение на аутсорсинг (см. Левую часть дерева). В этом случае он должен выбрать, например, между дилером A и B. Таким образом, он выбирает первого, в результате чего игрок x проигрывает 10 (если он выбрал B, игрок x выиграет 12).
Однако, возможно, противник предпочитает распространять свои товары сам, имея возможность арендовать моторизованные транспортные средства или купить грузовик. Из обоих сценариев выберите первый, который менее лестен для игрока x, потому что он выиграет 5, а не 10.