Минимакс

редактировать

Правило принятия решения, используемое для минимизации возможных потерь при наихудшем сценарии

Минимакс (иногда МинМакс, MMили седловая точка ) - правило принятия решения, используемое в искусственном интеллекте, теории принятия решений, теории игр, статистике и философия для минимизации возможных потерь для наихудшего сценария (максимальные потери). Когда речь идет о приросте, его называют «максимальным» - максимизировать минимальный прирост. Первоначально сформулированная для n-игроков нулевая сумма теория игр, охватывающая как случаи, когда игроки делают альтернативные ходы, так и те, когда они делают одновременные ходы, она также была распространена на более сложные игры и к принятию общих решений в условиях неопределенности.

Содержание

1 Теория игр
- 1.1 Общие игры
- 1.2 В играх с нулевой суммой
- 1.3 Пример
- 1.4 Максимин
- 1.5 В повторяющихся играх
2 Комбинаторная теория игр
- 2.1 Минимаксный алгоритм с чередующимися ходами
- 2.2 Псевдокод
- 2.3 Пример
3 Минимакс для индивидуальных решений
- 3.1 Минимакс в условиях неопределенности
- 3.2 Критерий минимакса в теории статистических решений
- 3.3 Невероятностная теория принятия решений
4 Максимин в философии
5 См. Также
6 Примечания
7 Внешние ссылки

Теория игр

Общие игры

Максимальное значение - это наивысшее значение, которое игрок может быть уверен, не зная действий других игроков; эквивалентно, это наименьшее значение, которое другие игроки могут заставить игрока получить, когда они знают действия игрока. Его формальное определение:

vi _ = max ai min a - ivi (ai, a - i) {\ displaystyle {\ underline {v_ {i}}} = \ max _ {a_ {i}} \ min _ {a _ {- i}} {v_ {i} (a_ {i}, a _ {- i})}}

{\ underline {v_ {i}}} = \ max _ {a_ {i}} \ min _ {a _ {- i}} {v_ {i} (a_ {i}, a _ {- i})}

Где:

i - индекс интересующего игрока.
$- i { \ displaystyle -i}$ $-i$ обозначает всех других игроков, кроме игрока i.
$ai {\ displaystyle a_ {i}}$ $a_ {i}$ - действие, выполняемое игроком i.
$a - i {\ displaystyle a _ {- i}}$ $a _ {{- i}}$ обозначает действия, предпринятые всеми другими игроками.
$vi {\ displaystyle v_ {i}}$ $v_ {i}$ - функция значения игрока i

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

Например, рассмотрим следующую игру для двух игроков, в которой первый игрок («игрок в ряду») может выбрать любой из трех ходов, обозначенных T, M или B, а второй игрок («столбец» игрок) может выбрать один из двух ходов: L или R. Результат комбинации обоих ходов выражается в таблице выплат:

	L	R
T	3,1	2, -20
M	5,0	-10,1
B	-100,2	4,4

(где первое число в каждой ячейке - это выплата игрока ряда, а второе число выплата игрока столбца).

В качестве примера мы рассматриваем только чистые стратегии. Проверьте каждого игрока по очереди:

Игрок строки может сыграть T, что гарантирует ему выигрыш не менее 2 (игра B рискованна, поскольку может привести к выплате −100, а игра M может привести к выплате −10). Следовательно: $vrow _ = 2 {\ displaystyle {\ underline {v_ {row}}} = 2}$ ${\ underline {v_ {row}}} = 2$ .
Игрок столбца может сыграть L и получить выигрыш не менее 0 (игра R подвергает его риску получения $- 20 {\ displaystyle -20}$ ${\ displaystyle -20}$ ). Следовательно: $vcol _ = 0 {\ displaystyle {\ underline {v_ {col}}} = 0}$ ${\ underline {v_ {col}}} = 0$ .

Если оба игрока используют свои соответствующие максимальные стратегии, $(T, L) {\ displaystyle (T, L)}$ ${\ displaystyle (T, L)}$ , вектор выигрыша равен $(3, 1) {\ displaystyle (3,1)}$ $(3,1)$ .

минимаксное значение игрока - это наименьшее значение что другие игроки могут заставить игрока принимать, не зная действий игрока; эквивалентно, это наибольшая ценность, которую игрок может получить, зная действия других игроков. Его формальное определение:

vi ¯ = min a - i max aivi (ai, a - i) {\ displaystyle {\ overline {v_ {i}}} = \ min _ {a _ {- i}} \ max _ {a_ {i}} {v_ {i} (a_ {i}, a _ {- i})}}

{\ overline {v_ {i}}} = \ min _ {a _ {- i}} \ max _ {a_ {i}} {v_ {i} (a_ {i }, a _ {- i})}

Определение очень похоже на определение максимального значения - только порядок операторов максимума и минимума обратное. В приведенном выше примере:

игрок строки может получить максимальное значение 4 (если другой игрок играет R) или 5 (если другой игрок играет L), поэтому: $vrow ¯ = 4 {\ displaystyle { \ overline {v_ {row}}} = 4}$ $\ overline {v_ {row}} = 4$ .
Игрок столбца может получить максимальное значение 1 (если другой игрок играет T), 1 (если M) или 4 (если B). Следовательно: $vcol ¯ = 1 {\ displaystyle {\ overline {v_ {col}}} = 1}$ $\ overline {v_ {col}} = 1$ .

Для каждого игрока i максимин не превышает минимакс:

vi _ ≤ vi ¯ { \ displaystyle {\ underline {v_ {i}}} \ leq {\ overline {v_ {i}}}}

\ underline {v_i} \ leq \ overline {v_i}

Интуитивно понятно, что при максимизации максимизация происходит раньше минимизации, поэтому игрок i пытается максимизировать свою ценность, не зная, что другие подойдут; в минимаксе максимизация происходит после минимизации, поэтому игрок i находится в гораздо лучшем положении - он максимизирует свою ценность, зная, что сделали другие.

Другой способ понять обозначение - это читать справа налево: когда мы пишем

vi ¯ = min a - i max aivi (ai, a - i) = min a - i (max aivi (ai, a - i)) {\ displaystyle {\ overline {v_ {i}}} = \ min _ {a _ {- i}} \ max _ {a_ {i}} {v_ {i} (a_ {i }, a _ {- i})} = \ min _ {a _ {- i}} {\ Big (} \ max _ {a_ {i}} {v_ {i} (a_ {i}, a _ {- i})} {\ Big)}}

{\ displaystyle {\ overline {v_ {i}}} = \ min _ {a_ { -i}} \ max _ {a_ {i}} {v_ {i} (a_ {i}, a _ {- i})} = \ min _ {a _ {- i}} {\ Big (} \ max _ {a_ {i}} {v_ {i} (a_ {i}, a _ {- i})} {\ Big)}}

исходный набор результатов $vi (ai, a - i) {\ displaystyle v_ {i} (a_ {i}, a _ {- i})}$ ${\ displaystyle v_ {i} (a_ {i}, a _ {- i})}$ зависит как от $ai {\ displaystyle {a_ {i}}}$ ${\ displaystyle {a_ {i}}}$ , так и от $a - i {\ displaystyle {a _ {- i}}}$ ${\ displaystyle {a _ {- i}}}$ . Сначала мы убираем $ai {\ displaystyle {a_ {i}}}$ ${\ displaystyle {a_ {i}}}$ с $vi (ai, a - i) {\ displaystyle v_ {i} (a_ {i}, a_ {-i})}$ ${\ displaystyle v_ {i} (a_ {i}, a _ {- i})}$ , максимизируя более $ai {\ displaystyle {a_ {i}}}$ ${\ displaystyle {a_ {i}}}$ (для каждого возможного значения $a - i {\ displaystyle {a _ {- i}}}$ ${\ displaystyle {a _ {- i}}}$ ) для получения набора предельных результатов $vi '(a - i) {\ displaystyle v' _ {i} (a _ {- i})}$ $v'_{i}(a_{-i})$ , который зависит только от $a - i {\ displaystyle {a _ {- i}}}$ ${\ displaystyle {a _ {- i}}}$ . Затем мы минимизируем более $a - i {\ displaystyle {a _ {- i}}}$ ${\ displaystyle {a _ {- i}}}$ для этих результатов. (И наоборот для максимина.)

Хотя всегда бывает, что $vrow _ ≤ vrow ¯ {\ displaystyle {\ underline {v_ {row}}} \ leq {\ overline {v_ {row} }}}$ ${\ displaystyle {\ underline {v_ {row}}} \ leq {\ overline {v_ {row}}}}$ и $vcol _ ≤ vcol ¯ {\ displaystyle {\ underline {v_ {col}}} \ leq {\ overline {v_ {col}}}}$ ${\ displaystyle {\ underline {v_ {col}}} \ leq {\ overline {v_ {col}}}}$ , вектор выигрыша, полученный в результате применения обоими игроками своих минимаксных стратегий, $(2, - 20) {\ displaystyle (2, -20)}$ ${\ displaystyle (2, -20)}$ в случае $(T, R) {\ displaystyle (T, R)}$ ${\ displaystyle (T, R)}$ или $(- 10, 1) {\ displaystyle (-10,1)}$ ${\ displaystyle (-10,1)}$ в случае $(M, R) {\ displaystyle (M, R)}$ ${\ displaystyle (M, R)}$ , нельзя аналогичным образом ранжировать по вектору выигрыша $(3, 1) {\ displaystyle (3,1)}$ $(3,1)$ в результате того, что оба игрока играют свою максимальную стратегию.

В играх с нулевой суммой

В играх с двумя игроками с нулевой суммой минимаксное решение такое же, как равновесие по Нэшу.

В контексте игр с нулевой суммой теорема о минимаксе эквивалентна:

Для каждой игры с нулевой суммой для двух человек с конечным числом стратегий существует значение V и смешанная стратегия для каждого игрока, такая, что

(a) Учитывая стратегию игрока 2, наилучший возможный выигрыш для игрока 1 равен V, и

(b) Учитывая стратегию игрока 1, наилучший возможный выигрыш для игрок 2 равен −V.

Аналогично, стратегия игрока 1 гарантирует ему выигрыш в размере V независимо от стратегии игрока 2, и аналогично игрок 2 может гарантировать себе выигрыш в размере −V. Название «минимакс» возникает из-за того, что каждый игрок минимизирует максимально возможный выигрыш для другого - поскольку игра ведется с нулевой суммой, они также минимизируют свой собственный максимальный проигрыш (т.е. максимизируют свой минимальный выигрыш). См. Также пример игры без значения.

Пример

Матрица выплат для игрока A
	B выбирает B1	B выбирает B2	B выбирает B3
A выбирает A1	+3	−2	+2
A выбирает A2	−1	+0	+4
A выбирает A3	−4	−3	+1

Следующий пример игры с нулевой суммой, где A и B совершают одновременные ходы, иллюстрирует минимаксные решения. Предположим, у каждого игрока есть три варианта выбора, и он рассмотрит матрицу выплат для A, отображаемую справа. Предположим, что матрица выплат для B является той же самой матрицей с обратными знаками (т.е. если выбраны A1 и B1, тогда B платит от 3 до A ). Тогда выбор минимакса для A - это A2, так как в этом случае наихудший возможный результат - это выплата 1, в то время как простой минимаксный выбор для B - это B2, так как тогда худший возможный результат - нет оплата. Однако это решение нестабильно, поскольку, если B считает, что A выберет A2, тогда B выберет B1 для получения 1; тогда, если A считает, что B выберет B1, тогда A выберет A1, чтобы получить 3; а затем B выберет B2; и, в конце концов, оба игрока осознают сложность выбора. Так что нужна более стабильная стратегия.

Некоторые варианты выбора преобладают над другими, и их можно исключить: A не выберет A3, поскольку либо A1, либо A2 дадут лучший результат, независимо от того, что выберет B ; B не выберет B3, поскольку некоторые смеси B1 и B2 дадут лучший результат, независимо от того, что выберет A .

Aможет избежать внесения ожидаемого платежа на сумму более 1∕3, выбрав A1 с вероятностью 1 and6 и A2 с вероятностью 5∕6: ожидаемый выигрыш для A будет 3 × (1 ∕ 6) - 1 × (5∕6) = −2∕3 в случае, если B выбрал B1 и −2 × (1∕6) + 0 × (5∕6) = −1/3 дюйма case B выбрал B2. Точно так же B может гарантировать ожидаемый выигрыш не менее 1/3, независимо от того, что выбирает A, используя рандомизированную стратегию выбора B1 с вероятностью 1∕3 и B2 с вероятностью 2∕3. Эти смешанные минимаксные стратегии теперь стабильны и не могут быть улучшены.

Максимин

Часто в теории игр максимин отличается от минимакса. Минимакс используется в играх с нулевой суммой для обозначения минимизации максимального выигрыша оппонента. В игре с нулевой суммой это идентично минимизации собственного максимального проигрыша и максимизации собственного минимального выигрыша.

«Максимин» - это термин, обычно используемый для игр с ненулевой суммой для описания стратегии, которая максимизирует собственный минимальный выигрыш. В играх с ненулевой суммой это обычно не то же самое, что минимизация максимального выигрыша оппонента, ни то же самое, что и стратегия равновесия по Нэшу.

В повторяющихся играх

Минимаксные значения очень важны в теории повторяющихся игр. Одна из центральных теорем этой теории, народная теорема, опирается на минимаксные значения.

Комбинаторная теория игр

В комбинаторной теории игр существует минимаксный алгоритм для игровых решений.

A простая версия минимаксного алгоритма, изложенная ниже, имеет дело с такими играми, как крестики-нолики, где каждый игрок может выиграть, проиграть или нарисовать. Если игрок А может выиграть за один ход, его лучший ход - это выигрышный ход. Если игрок B знает, что один ход приведет к ситуации, когда игрок A может выиграть одним ходом, а другой ход приведет к ситуации, когда игрок A может, в лучшем случае, взять ничью, тогда лучший ход игрока B - тот, который ведет к привлечь. В конце игры легко увидеть, какой ход «лучший». Алгоритм Minimax помогает найти лучший ход, работая в обратном направлении с конца игры. На каждом этапе предполагается, что игрок A пытается максимизировать шансы на выигрыш A, в то время как на следующем ходу игрок B пытается минимизировать шансы на выигрыш A (т.е. максимизировать собственные шансы B на победу).

Минимаксный алгоритм с альтернативными ходами

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

Возможный метод распределения состоит в назначении определенного выигрыша для A как +1 и для B как -1. Это приводит к комбинаторной теории игр, разработанной Джоном Хортоном Конвеем. Альтернативой является использование правила, согласно которому, если результатом хода является немедленный выигрыш для A, ему присваивается положительная бесконечность, а если это немедленный выигрыш для B, отрицательная бесконечность. Значение для A любого другого перемещения - это максимум значений, полученных в результате каждого из возможных ответов B . По этой причине A называется максимизирующим игроком, а B называется минимизирующим игроком, отсюда и название минимаксный алгоритм. Вышеупомянутый алгоритм присваивает значение положительной или отрицательной бесконечности любой позиции, так как значение каждой позиции будет значением некоторой окончательной выигрышной или проигрышной позиции. Часто это обычно возможно только в самом конце сложных игр, таких как chess или go, поскольку с вычислительной точки зрения невозможно заглядывать в будущее до завершения игры, за исключением ближе к концу, и вместо этого позициям присваиваются конечные значения как оценки степени уверенности в том, что они приведут к победе того или иного игрока.

Это можно расширить, если мы можем предоставить эвристическую функцию оценки , которая дает значения неокончательным состояниям игры без учета всех возможных следующих полных последовательностей. Затем мы можем ограничить алгоритм минимакса, чтобы смотреть только на определенное количество ходов вперед. Это число называется «упреждающим» и измеряется в «слоях ». Например, шахматный компьютер Deep Blue (первый, кто победил действующего чемпиона мира, Гарри Каспаров на тот момент) смотрел вперед как минимум на 12 уровней, а затем применил функцию эвристической оценки.

Алгоритм можно рассматривать как исследование узлов дерева игрового дерева. Эффективный фактор ветвления дерева - это среднее количество дочерних элементов каждого узла (т.е. среднее количество разрешенных ходов в позиции). Количество исследуемых узлов обычно увеличивается экспоненциально с количеством слоев (оно меньше экспоненциального при оценке принудительных перемещений или повторяющихся положений). Таким образом, количество узлов, которые необходимо исследовать для анализа игры, приблизительно равно коэффициенту ветвления, возведенному в степень числа слоев. Таким образом, нецелесообразно полностью анализировать игры, такие как шахматы, с использованием алгоритма минимакса.

Производительность простого минимаксного алгоритма может быть значительно улучшена, не влияя на результат, путем использования альфа-бета-отсечения. Также можно использовать другие эвристические методы сокращения, но не все они гарантированно дают такой же результат, как поиск без сокращения.

Наивный минимаксный алгоритм может быть тривиально модифицирован для дополнительного возврата всего Основного варианта вместе с минимаксной оценкой.

Псевдокод

Псевдокод для минимаксного алгоритма с ограниченной глубиной приведен ниже.

function minimax (node, depth, maximizingPlayer) isifdepth = 0 or node is a terminal node thenreturn эвристическое значение узла если maximizingPlayer то значение: = −∞ для каждого дочернего узла do value: = max (value, minimax (child, depth - 1, FALSE)) вернуть значение else (* минимизация игрока *) value: = + ∞ для каждого потомка узла do value: = min (value, minimax (child, depth - 1, TRUE)) return value

(* Initial call *) minimax (origin, depth, TRUE)

Функция минимакса возвращает эвристическое значение для конечных узлов (конечных узлов и узлов на максимальной глубине поиска). Неконцевые узлы наследуют свое значение от конечного узла-потомка. Эвристическое значение - это оценка, измеряющая предпочтительность узла для максимизирующего игрока. Следовательно, узлы, приводящие к благоприятному исходу, например выигрышу, для максимизирующего игрока имеют более высокие баллы, чем узлы, более благоприятные для минимизирующего игрока. Эвристическое значение для конечных (окончание игры) конечных узлов - это баллы, соответствующие выигрышу, проигрышу или ничьей для максимизирующего игрока. Для нетерминальных конечных узлов на максимальной глубине поиска функция оценки оценивает эвристическое значение для узла. Качество этой оценки и глубина поиска определяют качество и точность окончательного минимаксного результата.

Minimax обрабатывает двух игроков (максимизирующего игрока и минимизирующего игрока) отдельно в своем коде. На основе наблюдения, что $max (a, b) = - min (- a, - b) {\ displaystyle \ max (a, b) = - \ min (-a, -b)}$ $\ max (a, b) = - \ min (-a, -b)$ , минимакс часто можно упростить до алгоритма negamax.

Пример

Пример минимаксного дерева

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

Предположим, что в игре есть не более двух возможных ходов для каждого игрока за каждый ход. Алгоритм генерирует дерево справа, где кружки представляют ходы игрока, выполняющего алгоритм (максимизирующего игрока), а квадраты представляют ходы противника (минимизирующего игрока). Из-за ограничений вычислительных ресурсов, как объяснено выше, дерево ограничено предварительным просмотром на 4 хода.

Алгоритм оценивает каждый листовой узел с помощью функции эвристической оценки, получая показанные значения. Ходам, в которых побеждает максимизирующий игрок, присваивается положительная бесконечность, а ходам, ведущим к победе минимизирующего игрока, присваивается отрицательная бесконечность. На уровне 3 алгоритм выберет для каждого узла наименьшее значений дочернего узла и назначит его этому же узлу (например, узел слева выберет минимум между «10» и «+ ∞», поэтому присваивает себе значение «10»). Следующий шаг на уровне 2 состоит в выборе для каждого узла наибольшего значений дочернего узла. И снова значения присваиваются каждому родительскому узлу . Алгоритм продолжает оценивать поочередно максимальное и минимальное значения дочерних узлов, пока не достигнет корневого узла, где он выбирает ход с наибольшим значением (представлен на рисунке синей стрелкой). Это ход, который должен сделать игрок, чтобы минимизировать максимально возможные потери.

Минимакс для индивидуальных решений

Минимакс в условиях неопределенности

Теория минимакса была расширена к решениям, в которых нет другого игрока, но последствия решений зависят от неизвестных фактов. Например, решение о разведке полезных ископаемых влечет за собой затраты, которые будут потрачены впустую, если минералы отсутствуют, но принесут большие выгоды, если они есть. Один из подходов состоит в том, чтобы рассматривать это как игру против природы (см. движение по своей природе ) и, используя мышление, подобное закону Мерфи или резистенциализму, принять подход который минимизирует максимальный ожидаемый убыток, используя те же методы, что и в играх с нулевой суммой для двух человек.

Кроме того, деревья expectiminimax были разработаны для игр с двумя игроками, в которых шанс (например, игра в кости) является фактором.

Минимаксный критерий в статистической теории принятия решений

В классической статистической теории принятия решений у нас есть оценщик $δ {\ displaystyle \ delta}$ $\ delta$ , который используется для оценки параметра $θ ∈ Θ {\ displaystyle \ theta \ in \ Theta}$ $\ theta \ in \ Theta$ . Мы также предполагаем, что функция риска $R (θ, δ) {\ displaystyle R (\ theta, \ delta)}$ $R (\ theta, \ delta)$ , обычно указывается как интеграл от функция потерь. В этой структуре $δ ~ {\ displaystyle {\ tilde {\ delta}}}$ $\tilde{\delta}$ называется минимаксом, если он удовлетворяет

sup θ R (θ, δ ~) = inf δ sup θ R (θ, δ). {\ Displaystyle \ sup _ {\ theta} R (\ theta, {\ tilde {\ delta}}) = \ inf _ {\ delta} \ sup _ {\ theta} R (\ theta, \ delta).}

\ sup_ \ theta R (\ theta, \ tilde {\ delta}) = \ inf_ \ delta \ sup_ \ theta R (\ theta, \ delta).

Альтернативным критерием в структуре теории принятия решений является байесовская оценка при наличии априорного распределения $Π {\ displaystyle \ Pi}$ $\ Pi$ . Оценка является байесовской, если она минимизирует средний риск

∫ Θ R (θ, δ) d Π (θ). {\ displaystyle \ int _ {\ Theta} R (\ theta, \ delta) \, d \ Pi (\ theta).}

\ int_ \ Theta R (\ theta, \ delta) \, d \ Pi (\ theta).

Невероятностная теория принятия решений

Ключевая особенность принятия минимаксных решений не является вероятностным: в отличие от решений с использованием ожидаемого значения или ожидаемой полезности, он не делает никаких предположений о вероятностях различных исходов, только анализ сценария каковы возможные результаты. Таким образом, устойчив к изменениям в допущениях, в отличие от других методов принятия решений. Существуют различные расширения этого маловероятного подхода, в частности минимаксное сожаление и теория принятия решений о пропуске информации.

Кроме того, минимакс требует только порядкового измерения (чтобы результаты сравнивались и ранжированные), а не интервальные измерения (результаты включают «насколько лучше или хуже»), и возвращает порядковые данные, используя только смоделированные результаты: вывод минимаксного анализа: «эта стратегия минимаксна, поскольку в худшем случае ( результат), что менее плохо, чем любая другая стратегия ". Сравните с анализом ожидаемого значения, вывод которого имеет форму: «эта стратегия дает E (X) = n». Таким образом, Minimax может использоваться для порядковых данных и может быть более прозрачным.

Максимин в философии

В философии термин «максимин» часто используется в контексте книги Джона Ролза Теория справедливости, где он ссылается на это (Rawls 1971, p. 152) в контексте Принцип различия. Ролз определил этот принцип как правило, согласно которому социальное и экономическое неравенство должно быть устроено так, чтобы «оно приносило наибольшую пользу наименее обеспеченным членам общества».

См. Также

Примечания

Внешние ссылки

Найдите minimax в Викисловаре, бесплатном словарь.

Викицитатник содержит цитаты, относящиеся к: Minimax

, Энциклопедия математики, EMS Press, 2001 [1994]
Аплет визуализации
Принцип Максимина в Словаре философских терминов и названий
Играйте в игру ставок и блефа против смешанной стратегии минимакса
Минимакс в Словарь алгоритмов и структур данных
Минимакс (с al Pha-beta pruning) визуализация алгоритма - решение дерева игры (Java-апплет) для сбалансированных или несбалансированных деревьев.
Учебное пособие по Minimax с платформой численного решения
реализация Java, используемая в игре в шашки