Минимаксный алгоритм Объяснение

Я смотрю на этот псевдокод для алгоритма Minimax:

Function Minimax-Decision(state) returns an action
  ;inputs: state (current game state)
  ;'E' means element of, 'a' is the action
  return a E Actions(state) maximizing Min-Value(Result(a, state))

Function Max-Value(state) returns a utility value
  if Terminal-Test(state) then return Utility(state)
  v <-- -infinity
  for a, s in Successors(state) do v <-- Max(v, Min-Value(s))
  return v

Function Min-Value(state) returns a utility value
  if Terminal-Test(state) then return Utility(state)
  v <-- infinity
  for a, s in Successors(state) do v <-- Min(v, Max-Values(s))
  return v

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

Итак, для: с порядком Max,Min,Max сверхувведите описание изображения здесь

1) Макс хочет сделать лучший ход для себя (максимальная полезность), поэтому C1=5,C2=11,C3=8 и т. д.

2) Макс предсказывает, что Мин захочет поставить Макса в наихудшее возможное положение (ограничить Макса наименьшей полезностью), поэтому B1=5,B2=2,B3=3

3) Макс хочет сделать лучший возможный ход, поэтому A=B1=5

Что меня смущает в псевдокоде, так это двойная рекурсия и цель v. Может ли кто-нибудь разобрать это для меня?

Спасибо всем за чтение!


search algorithm tree minimax
person user1846359    schedule 03.02.2014    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Я думаю, что вы можете понять этот код, пройдя неофициальное доказательство по индукции, что он работает для деревьев глубины d.

Для глубины 1 у вас есть только один узел, и как минимальное значение, так и максимальное значение возвращают полезность этого узла.

Для глубины d > 1 сначала рассмотрим минимальное значение. v начинается с бесконечности, поэтому при первом вызове Min(v, Max-Value(s)) v задается полезность дочернего узла, вычисленная Max, потому что это очередь Max после Min, и мы знаем это правильно по индукции, потому что оно имеет глубину d-1. (Этот вызов представляет собой присваивание, поскольку v ‹= бесконечность). Последующие вызовы Min(v, Max-Value(s)) в этой подпрограмме заканчиваются вычислением Min of Max-Value(s) для всех дочерних элементов переданного узла. in. Таким образом, Min-Value в конечном итоге вычисляет минимальную полезность для всех дочерних элементов переданного узла, что является значением этого узла для Min, когда наступает очередь Min делать ход.

Аргумент для Max-Value почти такой же, как и для Min-Value, поэтому индукция говорит вам, что для деревьев любой глубины как Min-Value, так и Max-Value возвращают вам значение переданного им узла, когда очередь Макса или Мина двигаться и делать выбор, связанный с этим узлом.

Вы также можете показать по индукции, что то, что делает этот код, эквивалентно тому, что вы описали.

Таким образом, двойная рекурсия возникает потому, что она позволяет Max и Min чередоваться, когда вы поднимаетесь по дереву от листьев, а v является временным, которое используется для определения минимального или максимального значения всех дочерних узлов дерева.

person mcdowella    schedule 03.02.2014